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 asis, or with the spaces before the commas deleted so the commas come immediately after each number, into Sloane's online 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(n1,k1)+n*T(n1,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 AZ
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 20090316 13:31:56 