Question The question is to prove the following identity

$$ L_{n+1, k+1}=\sum_{i=0}^nL_{i,k}(n+k+1)_{n-i}\tag{1} $$

where $(n)_k$ denotes the falling factorial of length $k$ and $L_{n, k}$ denotes the Lah Numbers. This question is from Aigner's A Course in Enumeration.

Context I am free to use the characterizations of the Lah Numbers $L_{n,k}$ as the connecting coefficients between the rising factorials and falling factorials or that it counts the number of ways to partition the set $[n]$ into $k$ nonempty linearly ordered subsets and have also proven the identity $$ (x+1)^{(n)}=\sum_{k=0}^n L_{n+1, k+1}(x-1)_k\tag{2} $$ where $x^{(n)}$ denotes the rising factorial. I am also aware of a two term recurrence for the Lah Numbers but would like to prove (1) without it.


Combinatorial Proof Rewriting (1) as $$ L_{n+1, k+1}=\sum_{i=0}^nL_{n-i,k}(n+k+1)_{i}\tag{3} $$ my idea is to choose and arrange $i$ elements to be the same block as $1$ and then to partition the remaining $n-i$ elements into $k$ linearly ordered blocks. The problem is I am having trouble interpreting what $(n+k+1)_{i}$ means in this context.

Algebraic Proof

I have two ideas here and was unable to get far with both of them. First we can use the fact that $L_{i,k}=\frac{i!}{k!}\binom{i-1}{k-1}$ and substitute into the RHS of (1) and to manipulate the resulting binomial coefficients but it is a mess. My second idea was to show $$ \sum_{k=0}^n\left(\sum_{i=0}^nL_{i,k}(n+k+1)_{n-i}\right)(x-1)_k=(x+1)^{(n)}\tag{4} $$ and conclude using (2) but was unable to get beyond interchanging summation.

Any help on a combinatorial or algebraic approach is welcome.


$L_{n+1,k+1}$ is the number of partitions of $\{1,2,\dots,n,n+1\}$ into $k+1$ non-empty ordered subsets. Let the rank of such a partition be the largest number $i$ for which $i+1$ is not in the same subset as any of $1,2,\dots,i$. Then

$L_{i,k}(n+k+1)_{n-i}$ is the number of partitions with rank $i$.

Why? A partition of rank $i$ can be specified by first choosing a partition of $\{1,2,\dots,i+1\}$ into ordered subsets, then adding in the elements $\{i+2,i+3,\dots,n+1\}$. The elements $\{1,2,\dots,i+1\}$ must span all $k+1$ subsets, since by definition of rank, every subsequent element is in a subset with a previous element. Since $i+1$ is in a different subset than $\{1,2,\dots,i\}$, there are $L_{i,k}$ ways to place the numbers $\{1,2,\dots,i+1\}$. Then, the element $i+2$ can be added to one of these subsets in $k+i+2$ ways (either at the start of one of the $k+1$ subsets, or immediately after one of the $i+1$ elements). Next, element $i+3$ can be added in $k+i+3$ ways, then $i+4$ can be added in $k+i+4$ ways, and so on.

Putting this all together, the number of ways to choose the partition of rank $i$ is $$ L_{i,k}\cdot (k+i+2)\cdot(k+i+3)\cdot\ldots\cdot(n+k+1)=L_{i,k}(n+k+1)_{n-i}. $$

Side note: the combinatorial proof in your post leads to a proof of the similar identity $$ L_{n+1,k+1}=\sum_i L_{i,k}\binom{n}i(n+1-i)!=\sum_i L_{i,k}(n)_{n-i}\cdot(n+1-i). $$

  • $\begingroup$ (+1) It's seems obvious when you put it like that. Nice work! $\endgroup$ – N. Shales Jun 1 '18 at 14:05
  • 1
    $\begingroup$ Haha, it wasn't obvious to me! I was stuck on this problem for a long time until I saw your answer. I would say my answer is just a rewording of yours which doesn't explicitly mention the two-term recurrence @N.Shales $\endgroup$ – Mike Earnest Jun 1 '18 at 14:16
  • $\begingroup$ Perhaps that's why it made sense to me. Still, I was stumped on how to turn my recurrence into a bijection so it's good to see you've managed it :) $\endgroup$ – N. Shales Jun 1 '18 at 14:29

A partial combinatorial proof may go as follows:

The set $S=\{1,2,\ldots , n+1\}$ can be split into $k+1$ non-empty ordered sets in $L_{n+1,k+1}$ ways.

Alternatively, element $k+1$ is in an ordered set on it's own in $L_{n,k}$ ways or appears between elements in the $k+1$ ordered sets in $(n+k+1)L_{n,k+1}$ ways.

Hence the recurrence

$$L_{n+1,k+1}=L_{n,k}+(n+k+1)L_{n,k+1}\, .$$


$$\begin{align}L_{n+1,k+1}&=L_{n,k}+(n+k+1)(L_{n-1,k}+(n+k)L_{n-1,k+1})\\[1ex] &=L_{n,k}+(n+k+1)L_{n-1,k}+(n+k+1)(n+k)L_{n-1,k+1}\\[1ex] &=L_{n,k}+(n+k+1)L_{n-1,k}+(n+k+1)(n+k)(L_{n-2,k}+(n+k+1)L_{n-2,k+1})\\[1ex] &=L_{n,k}+(n+k+1)^\underline{1}L_{n-1,k}+(n+k+1)^\underline{2}L_{n-2,k}+(n+k+1)^\underline{3}L_{n-2,k+1}\\[1ex] &\hspace1.4ex\vdots\\[1ex] &=\sum_{i=0}^{n-k}(n+k+1)^\underline{i}L_{n-i,k}\, .\end{align}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.