Illustration of the unsigned Lah numbers for n and k between 1 and 4

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 ${\displaystyle n}$th derivatives of ${\displaystyle e^{1/x))$.[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):

${\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!)).}$

Signed Lah numbers (sequence A008297 in the OEIS):

${\displaystyle L'(n,k)=(-1)^{n}{n-1 \choose k-1}{\frac {n!}{k!)).}$

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 KaramataKnuth notation for Stirling numbers, it has been proposed to use the following alternative notation for Lah numbers:

${\displaystyle L(n,k)=\sum _{j=0}^{n}\left[{\begin{matrix}n\\j\end{matrix))\right]\left$$(\begin{matrix}j\\k\end{matrix))\right$$)$

Rising and falling factorials

Let ${\displaystyle x^{(n)))$ represent the rising factorial ${\displaystyle x(x+1)(x+2)\cdots (x+n-1)}$ and let ${\displaystyle (x)_{n))$ represent the falling factorial ${\displaystyle x(x-1)(x-2)\cdots (x-n+1)}$.

Then ${\displaystyle x^{(n)}=\sum _{k=1}^{n}L(n,k)(x)_{k))$ and ${\displaystyle (x)_{n}=\sum _{k=1}^{n}(-1)^{n-k}L(n,k)x^{(k)}.}$

For example,

${\displaystyle x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x-1)(x-2).}$

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)!))={n \choose k}{n-1 \choose k-1}(n-k)!}$
${\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)!))}$
${\displaystyle L(n,k+1)={\frac {n-k}{k(k+1)))L(n,k).}$
${\displaystyle L(n+1,k)=(n+k)L(n,k)+L(n,k-1)}$ where ${\displaystyle L(n,0)=0}$, ${\displaystyle L(n,k)=0}$ for all ${\displaystyle k>n}$, and ${\displaystyle L(1,1)=1.}$
${\displaystyle L(n,k)=\sum _{j}\left[{n \atop j}\right]\left$$(j \atop k}\right\},}$ where ${\displaystyle \left[{n \atop j}\right]}$ are the Stirling numbers of the first kind and ${\displaystyle \left\((j \atop k}\right$$)$ are the Stirling numbers of the second kind, ${\displaystyle L(0,0)=1}$, and ${\displaystyle L(n,k)=0}$ for all ${\displaystyle k>n}$.
${\displaystyle L(n,1)=n!}$
${\displaystyle L(n,2)=(n-1)n!/2}$
${\displaystyle L(n,3)=(n-2)(n-1)n!/12}$
${\displaystyle L(n,n-1)=n(n-1)}$
${\displaystyle L(n,n)=1}$
${\displaystyle \sum _{n\geq k}L(n,k){\frac {x^{n)){n!))={\frac {1}{k!))\left({\frac {x}{1-x))\right)^{k))$

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

Recent practical application

In recent years, Lah numbers have been used in steganography for hiding data in images. A few researchers,[6] [7] such as Dr Sudipta Kumar Ghosal, have exploited them in this domain as an alternative to DCT, DFT and DWT because of the low complexity—${\displaystyle O(n\log n)}$—of calculation of their integer coefficients.

3. ^ Daboul, Siad; Mangaldan, Jan; Spivey, Michael Z.; Taylor, Peter J. (2013). "The Lah Numbers and the nth Derivative of ${\displaystyle e^{1 \over x))$". Mathematics Magazine. 86 (1): 39–47. doi:10.4169/math.mag.86.1.039. JSTOR 10.4169/math.mag.86.1.039. S2CID 123113404.