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 n-1 for n and k-1 for k, so that the formula is:

For k=1, W(n,k) = (n-1)!
otherwise W(n,k) = W(n-1,k-1) + (n-1)*W(n-1,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 (n-1)! 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 n-1 buildings with k-1 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 (n-1) 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 n-1 buildings with k needed to be visible and the number of arrangements of that is W(n-1,k). Thus the remaining term is found.

The new recursion checks out:

DECLARE FUNCTION fact# (x#)
DEFDBL A-Z
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 2009-03-16 16:04:41