Lah number
In mathematics, the Lah numbers, discovered by Ivo Lah in 1954,[1][2] are coefficients expressing rising factorials in terms of falling factorials. They are also the coefficients of the th derivatives of .[3]
Unsigned Lah numbers have an interesting meaning in combinatorics: they count the number of ways a set of n elements can be partitioned into k nonempty linearly ordered subsets.[4] Lah numbers are related to Stirling numbers.[5]
Unsigned Lah numbers (sequence A105278 in the OEIS):
Signed Lah numbers (sequence A008297 in the OEIS):
L(n, 1) is always n!; in the interpretation above, the only partition of {1, 2, 3} into 1 set can have its set ordered in 6 ways:
- {(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)} or {(3, 2, 1)}
L(3, 2) corresponds to the 6 partitions with two ordered parts:
- {(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {(3), (1, 2)} or {(3), (2, 1)}
L(n, n) is always 1 since, e.g., partitioning {1, 2, 3} into 3 non-empty subsets results in subsets of length 1.
- {(1), (2), (3)}
Adapting the Karamata–Knuth notation for Stirling numbers, it has been proposed to use the following alternative notation for Lah numbers:
Rising and falling factorials
Let represent the rising factorial and let represent the falling factorial .
Then and
For example,
Compare the third row of the table of values.
Identities and relations
- where , for all , and
- where are the Stirling numbers of the first kind and are the Stirling numbers of the second kind, , and for all .
Table of values
Below is a table of values for the Lah numbers:
k n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | |||||||||||
2 | 2 | 1 | ||||||||||
3 | 6 | 6 | 1 | |||||||||
4 | 24 | 36 | 12 | 1 | ||||||||
5 | 120 | 240 | 120 | 20 | 1 | |||||||
6 | 720 | 1800 | 1200 | 300 | 30 | 1 | ||||||
7 | 5040 | 15120 | 12600 | 4200 | 630 | 42 | 1 | |||||
8 | 40320 | 141120 | 141120 | 58800 | 11760 | 1176 | 56 | 1 | ||||
9 | 362880 | 1451520 | 1693440 | 846720 | 211680 | 28224 | 2016 | 72 | 1 | |||
10 | 3628800 | 16329600 | 21772800 | 12700800 | 3810240 | 635040 | 60480 | 3240 | 90 | 1 | ||
11 | 39916800 | 199584000 | 299376000 | 199584000 | 69854400 | 13970880 | 1663200 | 11880 | 4950 | 110 | 1 | |
12 | 479001600 | 2634508800 | 4390848000 | 3293136000 | 1317254400 | 307359360 | 43908480 | 3920400 | 217800 | 7260 | 132 | 1 |
See also
References
- Lah, Ivo (1954). "A new kind of numbers and its application in the actuarial mathematics". Boletim do Instituto dos Actuários Portugueses. 9. pp. 7–15.
- John Riordan, Introduction to Combinatorial Analysis, Princeton University Press (1958, reissue 1980) ISBN 978-0-691-02365-6 (reprinted again in 2002 by Dover Publications).
- Daboul, Siad; Mangaldan, Jan; Spivey, Michael Z.; Taylor, Peter J. (2013). "The Lah Numbers and the nth Derivative of ". Mathematics Magazine. 86 (1). pp. 39–47. JSTOR 10.4169/math.mag.86.1.039.
- Petkovsek, Marko; Pisanski, Tomaz (Fall 2007). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers". Pi Mu Epsilon Journal. 12 (7). pp. 417–424. JSTOR 24340704.
- Comtet, Louis (1974). Advanced Combinatorics. Dordrecht, Holland: Reidel. p. 156.