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:
(In reply to
solution by Charlie)
The formula:
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
is defined such that the n is 1 less than the number of buildings and k is 1 less than the number of visible buildings. Define a new function where n is the number of buildings and k is the number of visible buildings by substituting n1 for n and k1 for k, so that the formula is:
For k=1, W(n,k) = (n1)!
otherwise W(n,k) = W(n1,k1) + (n1)*W(n1,k)
(note when a previous recursion is referenced, the n and k stay the same, as that definition has changed already)
Here's a derivation:
If only 1 building is to be visible, the tallest is in front and the remaining buildings can be arranged in (n1)! ways.
If more than 1 building is visible, either the newly added (tallest) building is at the back or some other building is at the back.
If the tallest building is at the back, then each arrangement of n1 buildings with k1 visible becomes an arrangement with k visible, accounting for the first term in the formula for W(n,k).
If the tallest building is not at the back, then some other building is, and there are (n1) such other buildings. Whichever that building is, it will not be visible as the tallest building comes before it. And the remaining buildings (including the tallest), become a set of n1 buildings with k needed to be visible and the number of arrangements of that is W(n1,k). Thus the remaining term is found.
The new recursion checks out:
DECLARE FUNCTION fact# (x#)
DEFDBL AZ
FOR n = 1 TO 10
FOR k = 1 TO n
IF k = 1 THEN
W(n, k) = fact(n  1)
ELSE
W(n, k) = W(n  1, k  1) + (n  1) * W(n  1, k)
END IF
PRINT W(n, k);
NEXT
PRINT
NEXT
FUNCTION fact (x)
f = 1
FOR i = 1 TO x
f = f * i
NEXT
fact = f
END FUNCTION
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
Edited on March 16, 2009, 4:06 pm

Posted by Charlie
on 20090316 16:04:41 