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 Karamata–Knuth 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:

Recent practical application

In recent years, Lah numbers have been used in steganography for hiding data in images. Compared to alternatives such as DCT, DFT and DWT, it has lower complexity—${\displaystyle O(n\log n)}$—of calculation of their integer coefficients.^{[6] [7]}