Consider a skyscraper problem on a 9x9 board. When a number is visible on the edge there will be some number of possible arrangements of buildings that could achieve this.

Find the number of possible arrangements of building if the edge number is each of {1,2,3,4,5,6,7,8,9}

For example on a 3x3 board there are three possibilities if a 2 is visible on the end (viewing from the left): (1,3,2), (2,3,1), (2,1,3)

(1,3,2), (2,3,1), (2,1,3)
What you would see:

DECLARE SUB permute (a$)
CLS

a$ = "123456789": h$ = a$

DO
  max$ = "0": ct = 0
  FOR i = 1 TO 9
    IF MID$(a$, i, 1) > max$ THEN ct = ct + 1: max$ = MID$(a$, i, 1)
  NEXT
  numb(ct) = numb(ct) + 1
  permute a$
LOOP UNTIL a$ = h$
FOR i = 1 TO 9
  PRINT numb(i); ",";
NEXT
PRINT

produces:

40320 , 109584 , 118124 , 67284 , 22449 , 4536 , 546 , 36 , 1 ,

for the number of arrangements that result in the visibility of 1 through 9 buildings respectively.

This can be entered as-is, or with the spaces before the commas deleted so the commas come immediately after each number, into Sloane's on-line encyclopedia of integer sequences. These two methods yield different results, but in each case, more than one. All are fundamentally a linearization of a triangle like this:

1;
1, 1;
2, 3, 1;
6, 11, 6, 1;
24, 50, 35, 10, 1;
120, 274, 225, 85, 15, 1;
720, 1764, 1624, 735, 175, 21, 1;
5040, 13068, 13132, 6769, 1960, 322, 28, 1;
40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1;
362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1 ;...

where, in the current context, the first line, 1, refers to the case of only one building. Note that in the third line, 2, 3, 1, the 3 refers to the three arrangements of three buildings that give rise to two of them being visible, as in the example shown in the puzzle.

The ninth line is the case under consideration, for 9 buildings.

Of course there's always only 1 way of seeing all the buildings: all the buildings are in size order, the largest farthest.

Some of the sequences in Sloane do not include the 1's. Others include zeros as well. Some alternate positive and negative values (the Stirling numbers).

One fairly simple way is:
A130534   Triangle T(n,k), 0<=k<=n, read by rows, giving coefficients of the polynomial (x+1)(x+2)...(x+n), expanded in increasing powers of x.

So for example three buildings would require n=2 and the polynomial would be (x+1)(x+2) = 2 + 3x + x^2, showing the coefficients 2,3,1. Note that the 40,320 is the 8! expected as the constant term in (x+1)(x+2)(x+3)(x+4)(x+5)(x+6)(x+7)(x+8), and of course represents the ways that 8 buildings can be arranged hiding behind the tallest of the nine.

The recursive formula given is:

T(0,0)=1, T(k,n)=0 if k>n or if n<0, T(n,k)=T(n-1,k-1)+n*T(n-1,k). T(n,0)=n!

again remembering that n is 1 less than the number of buildings, and k is 1 less than the number of visible buildings. So the triangle can be reproduced with:

DECLARE FUNCTION fact# (x#)
DEFDBL A-Z
FOR n = 0 TO 10
FOR k = 0 TO n
 IF k = 0 THEN
  t(n, k) = fact(n)
 ELSE
  t(n, k) = t(n - 1, k - 1) + n * t(n - 1, k)
 END IF
 PRINT t(n, k);
NEXT
PRINT
NEXT

FUNCTION fact (x)
 f = 1
 FOR i = 1 TO x
   f = f * i
 NEXT
 fact = f
END FUNCTION

giving

1
1  1
2  3  1
6  11  6  1
24  50  35  10  1
120  274  225  85  15  1
720  1764  1624  735  175  21  1
5040  13068  13132  6769  1960  322  28  1
40320  109584  118124  67284  22449  4536  546  36  1
362880  1026576  1172700  723680  269325  63273  9450  870  45  1
3628800  10628640  12753576  8409500  3416930  902055  157773  18150  1320  55 1

the last line being for 11 buildings in a row.

For more than 3 buildings, the most likely number of visible buildings is 3, until there are 24 buildings at which point 4 buildings being visible is the most common, until 72 buildings, when 5 visible buildings becomes the most common, etc.

Posted by Charlie on 2009-03-16 13:31:56