Skyscraper Numbers

Tanya Khovanova Department of Mathematics MIT 77 Massachusetts Avenue Cambridge, MA 02139-4307 USA

                       tanyakh@yahoo.com

Joel Brewster Lewis School of Mathematics University of Minnesota 127 Vincent Hall, 206 Church St. SE Minneapolis, MN 55455 USA

                        jblewis@umn.edu

Abstract We introduce numbers, depending on three parameters, which we call skyscraper numbers. We discuss properties of these numbers and their relationship with Stirling numbers of the first kind, and we also introduce the skyscraper sequence.

1 Introduction

In skyscraper puzzles the player has 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 are visible from this direction. For example, in the sequence 213645 there are three buildings (2,3,6) visible from the left and two (5,6) from the right.

In mathematical terminology, we are asked to build a Latin square such that each row and column is a permutation of length n with a given number of left-to-right and right-to-left-maxima. The 7-by-7 skyscraper puzzle in Figure 1 is from the Eighth World Puzzle Championship.

Figure 1: A skyscraper puzzle

Latin squares are notoriously complicated and difficult to enumerate. Thus, in this paper we discuss the combinatorics of a single row instead of asking about the entire puzzle. We give formal definitions and provide examples in Section 2. In Section 3 we give formulas for skyscraper numbers and in Section 4 we define the skyscraper sequence. In Section 5 we prove some properties of skyscraper numbers and the skyscraper sequence.

2 Definitions and Examples

What can we say about a row of a skyscraper puzzle if we ignore all information except the numbers given at the two ends of the row? In particular, how many permutations of the buildings are there that satisfy the given restrictions? Of course, the outside numbers have to be between 1 and n, and we leave as an exercise the proof that their sum must be between 3 and n + 1. Now we consider some of the simplest cases.

Suppose the two given 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.

Suppose the grid size is n and the outside numbers are a and b. Let us denote the total number of such permutations by f_{n}(a, b). We will assume that a is on the left and b is on the right. We call these number f_{n}(a, b) the skyscraper numbers and they are the object of our study.

In the previous example, we showed that f_{n}(n, 1) = 1. And of course we have f_{n}(a, b) = f_{n}(b, a).

Let us discuss a couple of other examples.

First, we want to discuss the case when the sum of the border numbers is the smallest, namely 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 any way we want.

Second, 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 + 1 − a) is \binom{n−1}{a−1}. Indeed, the position of the tallest building is uniquely defined — it has to take the a-th spot from the left. After that we can pick a set of a − 1 buildings that go to the left from the tallest building and the row is uniquely defined by this set.

3 Skyscraper Numbers

3.1 One-sided skyscraper numbers

Before going further let us see what happens if only a is given and b is unknown. Let us denote by c(n, a) the number of permutations of n buildings so that a buildings are visible from the left. If we put the shortest building on the left then the leftover buildings need to be arranged so that a − 1 of them are visible. If the shortest building is not on the left, then it can be in any of the n − 1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function c(n, a) satisfies the recurrence

c(n, a) = c(n − 1, a − 1) + (n − 1)c(n − 1, a),

and by iterating this recurrence we get

c(n, a) = ∑_{k=1}^{n−1} \frac{(n − 1)!}{(n − k − 1)!}c(n − k, a − 1).

Actually c(n, a) is a well-known function. The numbers c(n, a) are called unsigned Stirling numbers of the first kind (see sequence \underline{A132393} in the Online Encyclopedia of Integer Sequences [1]); not only do they count permutations with a given number of left-to-right (or right-to-left) 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; see for example [2, Chapter 1].

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
Table 1: The Stirling numbers c(n − 1, b − 1) = f_{n}(1, b)

3.2 The tallest building is on the left

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, b − 1 more buildings are seen from the right. That is, f_{n}(1, b) = c(n − 1, b − 1).

The non-zero values of f_{n}(1, b) for n and b not greater than 7 are collected in Table 1.

3.3 Skyscraper numbers

Now we have everything we need to consider the general case. In any permutation of length n, the left-to-right maxima consist of n and all left-to-right maxima that lie to its left; similarly, the right-to-left maxima consist of n and all the right-to-left maxima to its right. Thus, we can take any permutation counted by f_{n}(a, b) and split it into two parts by the location of n. Given a permutation π with a left-to-right and b right-to-left maxima, let k be the value 0 ≤ k ≤ n − 1 such that n is in position k + 1. Then the first k entries of π form a permutation with a − 1 left-to-right maxima, the last n − k − 1 entries of π form a permutation with b − 1 right-to-left maxima, and there are no other restrictions on the arrangement of the entries of π. Thus,

f_{n}(a, b) = ∑_{k=0}^{n−1} \binom{n − 1}{k}c(k, a − 1) · c(n − k − 1, b − 1).

Table 2 shows f_{7}(a, b), of which we already calculated the first row.

4 The Skyscraper Sequence

We see that the first two rows of the puzzle above (see Figure 1) have the same pair of numbers, namely 2 and 3, outside. If we ignore all other constraints there are 675 ways to fill in each of the first two rows. The number 675 is the largest number in the Table 2. We can say that these two rows of the puzzle are the most difficult to fill in: the pair of numbers 2 and 3 is the least restrictive. Given n, we call such a pair the maximizing pair.

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

Table 2: The skyscraper numbers f_{7}(a, b)

The sequence of the number of ways to fill in the most difficult row for n from 1 to 20 is as follows:

1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704, 4342080, 50457000, 31548456, 8484089328,

121882518576, 1865935562400, 30341974222944, 522466493255424,
9499883854364928, 181927524046316544.

We call this sequence the skyscraper sequence and it is now sequence \underline{A218531} in the OEIS [1].

For n = 1 to 30, the maximizing pairs (a, b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 3), (3, 4), (3, 4), (3, 4), (3, 4), (3, 4), (3, 4), (4, 4), (4, 4), (4, 4), (4, 4). One may notice that the numbers in these pairs do not differ by more than 1. We will prove that in Theorem 2.

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.

5 Properties

If we look at the antidiagonal in Table 2 we can notice that the numbers there are exactly a row of the Pascal triangle. Moreover, if we rescale other lines that are parallel to the antidiagonal by their gcd we get exactly the Pascal triangle! We combine these observations in the following lemma.

Lemma 1. f_{n}(a, b) = f_{n}(a + b − 1, 1) · \binom{a+b−2}{a−1}.

Proof. The number f_{n}(a+b−1, 1) counts the number of ways to arrange skyscrapers so that the tallest building is on the right and the permutation has a + b − 1 left-to-right maxima. For every skyscraper that is a left-to-right maximum but is not the tallest building, consider the group of buildings that are immediately after it to the right and that are located before the next left-to-right maximum. Choose b − 1 of these left-to-right maxima and move them together with their groups to the right end of the permutation. Put these maxima and their groups in the reverse order. The resulting permutation will have a left-to-right maxima and b right-to-left maxima. Moreover this operation is clearly reversible and so is a bijection.

We also give a second proof of this lemma using the definition of Stirling numbers in terms of cycles.

Proof. We want to show that f_{n}(a, b) = ∑_{k=0}^{n−1} \binom{n−1}{k} · c(k, a − 1) · c(n − k − 1, b − 1) is equal to \binom{a+b−2}{a−1} · c(n, a + b − 2). We can do this using the fact that c(n, a + b − 2) counts also permutations of length n − 1 with a + b − 2 cycles. Let us count permutations of length n − 1 with a + b − 2 cycles, of which a − 1 are colored red and b − 1 are colored blue, in two different ways: on one hand, we may first choose a permutation of length n − 1 with a + b − 2 cycles, then choose a − 1 of these cycles to be red, in \binom{a+b−2}{a−1} · c(n − 1, a + b − 2) ways. On the other hand, for any k between 0 and n − 1 we may first choose k elements to be in red cycles, then make a permutation on these k entries with exactly a − 1 cycles, and make a permutation with exactly b − 1 cycles on the remaining n − k − 1 entries. Thus we have in total ∑_{k=0}^{n−1} \binom{n−1}{k} · c(k, a − 1) · c(n − k − 1, b − 1) ways in this case. So the two things are equal, as claimed.

Now we are ready to prove the promised theorem about maximizing pairs for the skyscraper sequence.

Theorem 2. The numbers in the maximizing pairs do not differ by more than 1.

Proof. The maximum number in a table corresponding to the given n is the maximum number in its line parallel to antidiagonal. As each diagonal is proportionate to a row in the Pascal’s triangle, the maximum can be found in its middle.

Now let us sum all numbers in each row of Table 2. We get the following sums: 720, 1764, 1624, 735, 175, 21, 1. These numbers bring us back to the sequence \underline{A132393} in the OEIS [1]. These numbers are a row in the triangle of unsigned Stirling numbers of the first kind. This brings us to the next lemma:

Proposition 3. ∑_{b} f_{n}(a, b) = f_{n+1}(a + 1, 1).

Proof. Consider a row of length n + 1 with a + 1 left-to-right maxima and 1 right-to-left maximum. In this configuration the tallest building is on the right. If we remove the tallest building, then we get a row of length n with a left-to-right maxima and an unknown number of right-to-left maxima.

Skyscraper numbers are fun to play with. We are sure that they are hiding many more secrets.

References

[1] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, 2013. Available at http://

   oeis.org.

[2] Richard P. Stanley, Enumerative Combinatorics, Volume 1. Cambridge University Press, 2012.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 11Y55. Keywords: sequences, skyscraper puzzle, Stirling numbers.

(Concerned with sequences \underline{A132393}, \underline{A218531}.)

Received May 3 2013; revised version received July 7 2013. Published in Journal of Integer Sequences, July 30 2013.

Return to Journal of Integer Sequences home page.