In mathematics, Lah numbers, discovered by Ivo Lah in 1955,[1] are coefficients expressing rising factorials in terms of falling factorials.
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. Lah numbers are related to Stirling numbers.
Unsigned Lah numbers:
![{\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3605e7e20af99a788e4938e090305832dc20e33)
Signed Lah numbers:
![{\displaystyle L'(n,k)=(-1)^{n}{n-1 \choose k-1}{\frac {n!}{k!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d19c9b972cd6bdb869edd3923fd6b729f0a5345d)
L(n, 1) is always n!; using 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; e.g., partitioning {1, 2, 3} into 3 non-empty subsets results in subsets of length 1.
- {(1), (2), (3)}
Paraphrasing Karamata-Knuth notation for Stirling numbers, it was
proposed to use the following alternative notation for Lah numbers:
![{\displaystyle L(n,k)=\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9943dc22bf3809fbadfde1bacfa7f9f117ceba58)
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
![{\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}={n \choose k}{\frac {(n-1)!}{(k-1)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b80522ec52ae0dd26f44edde704245a144206eaa)
![{\displaystyle L(n,k)={\frac {n!(n-1)!}{k!(k-1)!}}\cdot {\frac {1}{(n-k)!}}=\left({\frac {n!}{k!}}\right)^{2}{\frac {k}{n(n-k)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22e6f109a36ca3aef110864662f91fda1f7950b4)
![{\displaystyle L(n,k+1)={\frac {n-k}{k(k+1)}}L(n,k).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fba9101e4c962970a60eda7250055500b794785)
with
the Stirling numbers of the first kind,
the Stirling numbers of the second kind and with the conventions
and
if
.
![{\displaystyle L(n,1)=n!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31530669349531afa8e763bf5918a0b199063d3a)
![{\displaystyle L(n,2)=(n-1)n!/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5d4178dc14b9875c25b2976f192b281c9829118)
![{\displaystyle L(n,3)=(n-2)(n-1)n!/12}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a83a9cb1d1963285170db546b38107a7ad4e641)
![{\displaystyle L(n,n-1)=n(n-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14402f0ad95ea0adc9d988eb823be977774e9e10)
![{\displaystyle L(n,n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd3f849cf6556c96585c0ae5eab376b93a536d14)
Table of values
Below is a table of values for the Lah numbers:
![{\displaystyle _{n}\!\!\diagdown \!\!^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cd7c6a887ae41fd2fb2e2ff8cbd1a6180c6a19e) |
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