Lah number

In mathematics, the (signed and unsigned) Lah numbers are coefficients expressing rising factorials in terms of falling factorials and vice versa. They were discovered by Ivo Lah in 1954.^[1][2] Explicitly, the unsigned Lah numbers ${\displaystyle L(n,k)}$ are given by the formula involving the binomial coefficient

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

for ${\displaystyle n\geq k\geq 1}$.

Unsigned Lah numbers have an interesting meaning in combinatorics: they count the number of ways a set of ${\textstyle n}$ elements can be partitioned into ${\textstyle k}$ nonempty linearly ordered subsets.^[3] Lah numbers are related to Stirling numbers.^[4]

For ${\textstyle n\geq 1}$, the Lah number ${\textstyle L(n,1)}$ is equal to the factorial ${\textstyle n!}$ in the interpretation above, the only partition of ${\textstyle \{1,2,3\}}$ into 1 set can have its set ordered in 6 ways:$${\displaystyle \{(1,2,3)\},\{(1,3,2)\},\{(2,1,3)\},\{(2,3,1)\},\{(3,1,2)\},\{(3,2,1)\}}$$${\textstyle L(3,2)}$ is equal to 6, because there are six partitions of ${\textstyle \{1,2,3\}}$ into two ordered parts:$${\displaystyle \{1,(2,3)\},\{1,(3,2)\},\{2,(1,3)\},\{2,(3,1)\},\{3,(1,2)\},\{3,(2,1)\}}$$${\textstyle L(n,n)}$ is always 1 because the only way to partition ${\textstyle \{1,2,\ldots ,n\}}$ into ${\displaystyle n}$ non-empty subsets results in subsets of size 1, that can only be permuted in one way. In the more recent literature,^[5][6] Karamata–Knuth style notation has taken over. Lah numbers are now often written as$${\displaystyle L(n,k)=\left\lfloor {n \atop k}\right\rfloor }$$