Tanya Khovanova and Joel Brewster Lewis
In skyscraper puzzles you have to put an integer from 1 to n in each cell of a square grid. Integers represent heights of buildings. Every row and column needs to be filled with buildings of different heights and the numbers outside the grid indicate how many buildings you can see from this direction. For example, in the sequence 213645 you can see 3 buildings from the left (2,3,6) and 2 from the right (5,6).
In mathematical terminology we are asked to build a Latin square such that each row is a permutation of length n with a given number of lefttoright and righttoleftmaxima. The following 7 by 7 puzzle is from the Eighth World Puzzle Championship.
Latin squares are notoriously complicated and difficult to understand, so instead of asking about the entire puzzle we discuss the mathematics of a single row. What can you say about a row if you ignore all other info? First of all, let us tell you that the numbers outside have to be between 1 and n. The sum of the left and the right numbers needs to be between 3 and n+1. We leave the proof as an exercise.
Let’s continue with the simplest case. Suppose the two numbers are n and 1. In this case, the row is completely defined. There is only one possibility: the buildings should be arranged in the increasing order from the side where we see all of them.
Now we come to the question we are interested in. Given the two outside numbers, how many permutations of the buildings are possible? Suppose the grid size is n and the outside numbers are a and b. Let’s denote the total number of permutations by f_{n}(a, b). We will assume that a is on the left and b is on the right.
In a previous example, we showed that f_{n}(n, 1) = 1. And of course we have f_{n}(a, b) = f_{n}(b, a).
Let’s discuss a couple of other examples.
First we want to discuss the case when the sum of the border numbers is the smallest — 3. In this case, f_{n}(1, 2) is (n−2)!. Indeed, we need to put the tallest building on the left and the second tallest on the right. After that we can permute the leftover buildings anyway we want.
Secondly we want to discuss the case when the sum of the border numbers is the largest — n+1. In this case f_{n}(a,n+1a) is (n1) choose (a1). Indeed, the position of the tallest building is uniquely defined — it has to take the ath spot from the left. After that we can pick a set of a1 buildings that go to the left from the tallest building and the position is uniquely defined by this set.
Before going further let us see what happens if only one of the maxima is given. Let us denote by g_{n}(a) the number of permutations of n buildings so that you can see a buildings from the left. If we put the shortest building on the left then the leftover buildings need to be arrange so that you can see a1 of them. If the shortest building is not on the left, then it can be in any of the n1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function g_{n}(a) satisfies the recurrence:
Actually g_{n}(a) is a wellknown function. The numbers g_{n}(a) are called unsigned Stirling numbers of the first kind (see http://oeis.org/A132393); not only do they count permutations with a given number of lefttoright (or righttoleft) maxima, but they also count permutations with a given number of cycles, and they appear as the coefficients in the product (x + 1)(x + 2)(x + 3)…(x + n), among other places. (Another pair of exercises.)
We are now equipped to calculate f_{n}(1, b). The tallest building must be on the left, and the rest could be arranged so that, in addition to the tallest building, b1 more buildings are seen from the right. That is f_{n}(1, b) = g_{n1}(b1).
Here is the table of nonzero values of f_{n}(1, b).

b=2 
b=3 
b=4 
b=5 
b=6 
b=7 
n=2 
1 





n=3 
1 
1 




n=4 
2 
3 
1 



n=5 
6 
11 
6 
1 


n=6 
24 
50 
35 
10 
1 

n=7 
120 
274 
225 
85 
15 
1 
Now we have everything we need to consider the general case. In any permutation of length n, the lefttoright maxima consist of n and all lefttoright maxima that lie to its left; similarly, the righttoleft maxima consist of n and all the righttoleft maxima to its right. We can take any permutation counted by f_{n}(a, b) and split it into two parts: if the value n is in position k + 1 for some 0 ≤ k ≤ n1, the first k values form a permutation with a – 1 lefttoright maxima and the last n – k – 1 values form a permutation with b – 1 righttoleft maxima, and there are no other restrictions. Thus:
Let’s have a table for f_{7}(a,b), of which we already calculated the first row:

b=1 
b=2 
b=3 
b=4 
b=5 
b=6 
b=7 
a=1 
0 
120 
274 
225 
85 
15 
1 
a=2 
120 
548 
675 
340 
75 
6 
0 
a=3 
274 
675 
510 
150 
15 
0 
0 
a=4 
225 
340 
150 
20 
0 
0 
0 
a=5 
85 
75 
15 
0 
0 
0 
0 
a=6 
15 
6 
0 
0 
0 
0 
0 
a=7 
1 
0 
0 
0 
0 
0 
0 
We see that the first two rows of the puzzle above correspond to the worst case. If we ignore all other constrains there are 675 ways to fill in each of the first two rows. By the way, the sequence of the number of ways to fill in the most difficult row for n from 1 to 10 is: 1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704. The maximizing pairs (a,b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3).
The actual skyscraper puzzles are designed so that they have a unique solution. It is the interplay between rows and columns that allows to reduce the number of overall solutions to one.
Share: