PH indicator

In mathematics, Lah numbers, discovered by Ivo Lah in 1955, 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:

$L(n,k)=(\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n!}{k!}.$

Signed Lah numbers:

$L^{\prime }(n,k)=(-1{)}^n(\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n!}{k!}.$

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:

$L(n,k)=\lfloor \begin{array}{c}n\\ k\end{array}\rfloor .$

Rising and falling factorials

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

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

For example, $x(x+1)(x+2)=6x+6x(x-1)+1x(x-1)(x-2).$

Compare the third row of the table of values.

Identities and relations

$L(n,k)=(\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n!}{k!}=(\genfrac{}{}{0ex}{}{n}{k})\frac{(n-1)!}{(k-1)!}$

$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)!}$

$L(n,k+1)=\frac{n-k}{k(k+1)}L(n,k).$

$L(n,k)={\sum }_j\left[\genfrac{}{}{0ex}{}{n}{j}\right]\left\{\genfrac{}{}{0ex}{}{j}{k}\right\},$ with $\left[\genfrac{}{}{0ex}{}{n}{j}\right]$ the Stirling numbers of the first kind, $\left\{\genfrac{}{}{0ex}{}{j}{k}\right\}$ the Stirling numbers of the second kind and with the conventions $L(0,0)=1$ and $L(n,k)=0$ if $k>n$.

$L(n,1)=n!$

$L(n,2)=(n-1)n!/2$

$L(n,3)=(n-2)(n-1)n!/12$

$L(n,n-1)=n(n-1)$

$L(n,n)=1$

Table of values

Below is a table of values for the Lah numbers:

$n_{}╲{}^k$	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

• Stirling numbers
• Pascal matrix