Combinatorial Interpretation of Unsigned Stirling and Lah Numbers^{∗}

Marko Petkovšek^{†} and Tomaž Pisanski^{‡} IMFM/TCS, University of Ljubljana Jadranska 19, SI-1000 Ljubljana Slovenia

October 16, 2002

Abstract The combinatorial role of unsigned Stirling and Lah numbers is reexamined in connection with ordi-

nary powers, rising factorial powers, and falling factorial powers. Several bijective proofs are given.

§ 1. Introduction. In this paper we examine three families of numbers with interesting combinatorial interpretations. We use three basic combinatorial proof techniques: the bijective proof, the rule of summation, and the method of distinguished element.

Let A and B be any two (finite) sets. Then |A| = |B| if and only if there exists a bijection f : A → B. Finding such a bijection is called a bijective proof of the identity |A| = |B|.

Another simple but powerful combinatorial tool is the rule of summation: If A ∩ B = ∅ then |A ∪ B| = |A| + |B|. This rule admits a straightforward generalization from two to k sets: one can divide a set into several disjoint parts (subsets) and then count the number of elements in the whole set by adding up the sizes of the parts.

The method of distinguished element is quite useful when setting up recurrence relations. Let A be a family of subsets of a set A. Pick a distinguished element x ∈ A and let P (X, x) be a predicate relating X ⊆ A to x. Denote by A(x) the family of those sets X from A for which P (X, x) is true, and by A − x its complement in A. Then obviously the rule of summation applies:

|A| = |A(x)| + |A − x|.

As a warm-up, let us use the method of distinguished element to prove Pascal’s identity. If A is the family of k-element subsets of an n-element set A, then |A| = \binom{n}{k}. Pick x ∈ A and let P (X, x) stand for x ∈ X. Clearly, |A(x)| = \binom{n−1}{k−1} and |A − x| = \binom{n−1}{k}, so \binom{n}{k} = \binom{n−1}{k−1} + \binom{n−1}{k}.

Our notation follows and extends the one from [2]. In particular, the Karamata notation [3] for the unsigned Stirling numbers is extended to the unsigned Lah numbers. Unless stated otherwise, we assume that n, k ≥ 1.

§ 2. Stirling numbers of the second kind. Let \left\{{n \atop k}\right\} denote the number of partitions of a set with n elements into k nonempty blocks. Then

\left\{{n \atop n}\right\} = \left\{{n \atop 1}\right\} = 1, \left\{{n \atop k}\right\} = 0 for n < k,

\left\{{n \atop k}\right\} = \left\{{n − 1 \atop k − 1}\right\} + k \left\{{n − 1 \atop k}\right\}.

The proof uses the method of distinguished element. Let N = {1, 2, …, n} and x = {1}. Take A = 2^{N}, A = \{partitions of N into k blocks\}, and P (X, x) = (x ∈ X). Then |A| = \left\{{n \atop k}\right\}, |A(x)| = \left\{{n−1 \atop k−1}\right\}, and |A − x| = k \left\{{n−1 \atop k}\right\}.

∗Work supported in part by MŠZŠ RS under grant P0-511-0101.

†Marko.Petkovsek@fmf.uni-lj.si

‡Tomaz.Pisanski@fmf.uni-lj.si

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 7 & 6 & 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 15 & 25 & 10 & 1 & 0 & 0 & 0 \\ 6 & 1 & 31 & 90 & 65 & 15 & 1 & 0 & 0 \\ 7 & 1 & 63 & 301 & 350 & 140 & 21 & 1 & 0 \\ 8 & 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 \end{matrix}

Table 1: Stirling numbers of the second kind \left\{{n \atop k}\right\}.

§ 3. Unsigned Stirling numbers of the first kind. Let \left[{n \atop k}\right] denote the number of permutations of an n-element set that have k disjoint cycles. Then

\left[{n \atop n}\right] = \left[{n \atop 1}\right] = 1, \left[{n \atop k}\right] = 0 for n < k,

\left[{n \atop k}\right] = \left[{n − 1 \atop k − 1}\right] + (n − 1) \left[{n − 1 \atop k}\right].

The proof again uses the method of distinguished element. The predicate here is true if and only if the corresponding permutation has a cycle of length 1 containing the distinguished element.

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 6 & 11 & 6 & 1 & 0 & 0 & 0 & 0 \\ 5 & 24 & 50 & 35 & 10 & 1 & 0 & 0 & 0 \\ 6 & 120 & 274 & 225 & 85 & 15 & 1 & 0 & 0 \\ 7 & 720 & 1764 & 1624 & 735 & 175 & 21 & 1 & 0 \\ 8 & 5040 & 13068 & 13132 & 6769 & 1960 & 322 & 28 & 1 \end{matrix}

Table 2: Unsigned Stirling numbers of the first kind \left[{n \atop k}\right].

§ 4. Unsigned Lah numbers. Let ⌊{n \atop k}⌋ denote the number of ways to partition an n-element set into k non-empty (linearly ordered) queues. The numbers ⌊{n \atop k}⌋ are called the unsigned Lah numbers (cf. [8, pp. 43–44], [9, pp. 48–49], [1, pp. 135, 156]). We have

⌊{n \atop n}⌋ = ⌊{n \atop 1}⌋ = 1, ⌊{n \atop k}⌋ = 0 for n < k,

⌊{n \atop k}⌋ = ⌊{n − 1 \atop k − 1}⌋ + (n + k − 1) ⌊{n − 1 \atop k}⌋.

The proof once again uses the method of distinguished element. The predicate here is true if and only if the corresponding partition has a queue of length 1 containing the distinguished element.

There are no closed-form expressions for \left\{{n \atop k}\right\} or \left[{n \atop k}\right]; however, one can easily find one for ⌊{n \atop k}⌋. To construct a partition into k queues, first put the n elements into a single queue, then cut it into k pieces by choosing k − 1 out of the n − 1 possible cut points. This can be done in n! \binom{n−1}{k−1} ways, but each partition appears k! times, so

⌊{n \atop k}⌋ = \frac{n!}{k!} \binom{n − 1}{k − 1} [Unsigned Lah Numbers].

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 6 & 6 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 24 & 36 & 12 & 1 & 0 & 0 & 0 & 0 \\ 5 & 120 & 240 & 120 & 20 & 1 & 0 & 0 & 0 \\ 6 & 720 & 1800 & 1200 & 300 & 30 & 1 & 0 & 0 \\ 7 & 5040 & 15120 & 12600 & 4200 & 630 & 42 & 1 & 0 \\ 8 & 40320 & 141120 & 141120 & 58800 & 11760 & 1176 & 56 & 1 \end{matrix}

Table 3: Unsigned Lah numbers ⌊{n \atop k}⌋.

§ 5. Rising and falling factorial powers. Following [2], write

x\overline{n} = x(x + 1) ⋯ (x + n − 1) [Rising Factorial Power],
x\underline{n} = x(x − 1) ⋯ (x − n + 1) [Falling Factorial Power].

Just as the ordinary powers x^{k}, the rising factorial powers x\overline{k} and the falling factorial powers x\underline{k}, for k = 1, 2, …, n, form a basis of the linear space of polynomials of degree at most n with zero constant term. These three bases are pairwise connected by six families of connection coefficients expressing the elements of one basis in terms of another.

§ 6. Stirling identities. It is well known (see, e.g., [2, Table 264]) that for positive integer n we have

x^{n} = ∑_{k=1}^{n} \left\{{n \atop k}\right\} x\underline{k} [Stirling Identity of the Second Kind],

x\overline{n} = ∑_{k=1}^{n} \left[{n \atop k}\right] x^{k} [Stirling Identity of the First Kind].

§ 7. Ivo Lah and his identity. In 1955, Slovenian mathematician and actuary Ivo Lah (Štrukljeva vas, 1896 – Ljubljana, 1979) proved [5] that we also have

x\overline{n} = ∑_{k=1}^{n}⌊{n \atop k}⌋ x\underline{k} [Lah Identity].

Note that by defining x^{0} = x\overline{0} = x\underline{0} = 1 and \left\{{n \atop 0}\right\} = \left[{n \atop 0}\right] = ⌊{n \atop 0}⌋ = δ_{n,0} it is possible to extend these identities to the usual spaces of polynomials of degree at most n (see [2]). In this case, the formula for Lah numbers should be written as ⌊{n \atop k}⌋ = n!/k!\binom{n−1}{n−k}.

§ 8. The strategy of proof. In the proof of these three identities we will use the same strategy. As each of them asserts the equality of two polynomials in x, it suffices to prove them for sufficiently many values of x. In fact we will prove them for all positive integers x. In each case we will present a bijective proof and apply the rule of summation. In order to visualize the sets enumerated by the left- and right-hand sides of these identities, we will use the following legend (cf. [7, Book III, Ch. XVIII]).

§ 9. The legend of Jason and the Argonauts. According to a legend, Ljubljana, the capital of modern Slovenia, known as Emona in Roman times, was founded already by Jason and the Argonauts when they were fleeing on their ship Argo with the Golden Fleece from the Black Sea via the Danube River, upstream the Sava River and finally reaching the dead-end at the source of the Nauportus River which is the present-day Ljubljanica. The dragon that Jason supposedly slaughtered while camping on the bank of Ljubljanica is still the dominant symbol in the city coat-of-arms. The legend tells us that the Argonauts carried Argo on their shoulders over the Alps (in fact, over Slovenian Carst) to the Adriatic Sea.

§ 10. Proof of Lah identity. For the purpose of this proof let us assume that the Argonauts took Argo apart and that each Argonaut carried one piece of the ship (including the chest with the Golden Fleece, of course). As there are several trails leading from the source of Ljubljanica to the coast, we may assume that various groups of Argonauts took separate trails, thereby minimizing the possibility of losing the Golden Fleece to the pursuing party. Let n be the number of Argonauts, and x the number of available trails. Since all the trails were narrow (no highways in those days!), we may further assume that each group of Argonauts taking the same trail proceeded in a queue or a column (i.e., was linearly ordered). In how many different ways could the Argonauts have reached the Adriatic Sea?

We will count the possible placements of the Argonauts along the trails in two different ways. First, assume that j Argonauts have already been placed. As there are d + 1 ways to insert a new element into a queue of length d, we see that we can place the (j + 1)-st Argonaut in x + j ways. All in all, there are x(x + 1) ⋯ (x + n − 1) = x\overline{n} possible placements, the left-hand side of the Lah identity.

Now count the placements depending on k, the number of trails actually used. First partition the n Argonauts into k nonempty queues in ⌊{n \atop k}⌋ ways, then assign to each queue its separate trail. This can be done in x\underline{k} ways. Altogether, there are ∑_{k=1}^{n}⌊{n \atop k}⌋ x\underline{k} possible placements, the right-hand side of the Lah identity. – We presented a slightly different proof of Lah identity in [6].

§ 11. Proof of Stirling Identity of the Second Kind. Repeat the preceding proof, but now ignore the order in each group of Argonauts. There are x^{n} ways to assign trails to the Argonauts. Again assume that k trails are actually used. Partition the Argonauts into k nonempty blocks in \left\{{n \atop k}\right\} ways, then assign a separate trail to each of the blocks. The identity follows.

§ 12. Proof of Stirling Identity of the First Kind. The left-hand side of the identity is interpreted as in the Lah case. For the right-hand side choose a permutation π of the Argonauts that has k disjoint cycles. This can be done in \left[{n \atop k}\right] ways. To each cycle assign a trail in x^{k} ways. Thus, indirectly, a trail has been assigned to each Argonaut. Now order the subset of Argonauts which were assigned the same trail by restricting π to this subset. For example, take π = ⟨78631452⟩ = (175)(28)(364) and assign trail 3 to (175) and trail 2 to both (28) and (364). Then the Argonauts proceed along trail 2 in the order ⟨86342⟩ and along trail 3 in the order ⟨715⟩ while the other trails are empty. – Altogether there are ∑_{k=1}^{n} \left[{n \atop k}\right] x^{k} possible placements.

§ 13. The inverse identities. By substituting −x for x in the Stirling and Lah identities, and replacing (−x)\underline{k} with (−1)^{k}x\overline{k} and vice versa, we obtain the inverse identities

x^{n} = ∑_{k=1}^{n}(−1)^{n+k}\left\{{n \atop k}\right\} x\overline{k},

x\underline{n} = ∑_{k=1}^{n}(−1)^{n+k}\left[{n \atop k}\right] x^{k},

x\underline{n} = ∑_{k=1}^{n}(−1)^{n+k}⌊{n \atop k}⌋ x\overline{k}.

We are not aware of a nice combinatorial interpretation of these identities; perhaps one could be obtained using the Principle of Inclusion and Exclusion.

§ 14. Matrix representations. Stirling and Lah identities and their inverses imply simple relations among Stirling and Lah numbers which can be most succinctly stated in matrix form. Let S, s and L denote infinite lower-triangular matrices whose (n, k)-th entries are \left\{{n \atop k}\right\}, \left[{n \atop k}\right], and ⌊{n \atop k}⌋, respectively. The upper left 8 × 8 corners of these matrices are shown in Tables 1, 2, and 3, respectively. A glance at the Stirling and Lah identities shows that

L = s S.

Furthermore, let D be the infinite diagonal matrix whose (n, k)-th entry is D_{n,k} = (−1)^{n}δ_{n,k}. Then it follows from the Stirling and Lah identities and their inverses that

S^{−1} = DsD, s^{−1} = DSD, L^{−1} = DLD.

As D^{−1} = D, we can express all the relevant matrices in terms of S (and D):

s = DS^{−1}D, L = DS^{−1}DS.

§ 15. Signed Stirling and Lah numbers. In the literature, Stirling numbers of the first kind often denote the signed integers (−1)^{n+k}\left[{n \atop k}\right] which are the entries of DsD. This definition has the advantage that Stirling matrices of the first and second kind are then inverse to each other.

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & −1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & −3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & −6 & 11 & −6 & 1 & 0 & 0 & 0 & 0 \\ 5 & 24 & −50 & 35 & −10 & 1 & 0 & 0 & 0 \\ 6 & −120 & 274 & −225 & 85 & −15 & 1 & 0 & 0 \\ 7 & 720 & −1764 & 1624 & −735 & 175 & −21 & 1 & 0 \\ 8 & −5040 & 13068 & −13132 & 6769 & −1960 & 322 & −28 & 1 \end{matrix}

Table 4: (Signed) Stirling numbers of the first kind (−1)^{n+k}\left[{n \atop k}\right].

Also Lah numbers are defined in [5] as the signed integers L_{n,k} = (−1)^{n}⌊{n \atop k}⌋ which are the entries of DL. This matrix is self-inverse, so the Lah identity and its inverse take on the quasi-symmetric forms

\begin{matrix}n\k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & −6 & −6 & −1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 24 & 36 & 12 & 1 & 0 & 0 & 0 & 0 \\ 5 & −120 & −240 & −120 & −20 & −1 & 0 & 0 & 0 \\ 6 & 720 & 1800 & 1200 & 300 & 30 & 1 & 0 & 0 \\ 7 & −5040 & −15120 & −12600 & −4200 & −630 & −42 & −1 & 0 \\ 8 & 40320 & 141120 & 141120 & 58800 & 11760 & 1176 & 56 & 1 \end{matrix}

Table 5: (Signed) Lah numbers (−1)^{n}⌊{n \atop k}⌋.

x\overline{n} = ∑_{k=1}^{n}(−1)^{n}L_{n,k} x\underline{k}, x\underline{n} = ∑_{k=1}^{n}(−1)^{k}L_{n,k} x\overline{k}.

§ 16. Historical note. Recent research of publications of Ivo Lah showed that he published an account on Lah numbers already in 1954 [4]. In this paper we extend the Karamata^{1} notation from Stirling to Lah numbers. We note in passing that both Jovan Karamata and Ivo Lah were among the six representatives from the Kingdom of Yugoslavia who took part at the 11th International Congress of Actuaries in Paris, June 17 – 24, 1937. However, only Lah actively participated at the Congress presenting three of his papers.

Acknowledgement. The authors express their thanks to Andrej Bauer for streamlining the first part of the proof of Lah identity in § 10.

References

[1] Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, revised and enlarged edition, D. Reidel Publ. Co., Dordrecht, Holland, 1974.

[2] Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Mass., 1989.

[3] Jovan Karamata, Théorèmes sur la sommabilité exponentielle et d’autres sommabilités rattachant, Mathematica (Cluj) 9 (1935), 164–178.

[4] Ivo Lah, A new kind of numbers and its application in the actuarial mathematics, Boletin do Instituto dos Actuarios Portugueses 9 (June 1954), 7–15.

[5] Ivo Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitteilungsbl. Math. Statist. 7 (1955), 203–212.

[6] Marko Petkovšek and Tomaž Pisanski, The Lah identity and the Argonauts, The ΠME Journal 11 (2002), 385–386.

[7] Gaius Plinius Secundus Maior, Naturalis Historia, Vol. 2, with an English translation by H. Rackham, W. Heinemann: London; Harvard University Press: Cambridge Mass., 1947.

[8] John Riordan, An Introduction to Combinatorial Analysis, John Wiley & Sons, Inc., New York, 1958.

[9] John Riordan, Combinatorial Identities, John Wiley & Sons, Inc., New York, 1968.

1Jovan Karamata (Zagreb 1902 - Geneve 1967), Serbian mathematician.