Combinatorial (and Algebraic Proof) of an Identity Involving Lah Numbers

Question

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.

Attempt

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.

Answer 1

$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). $$

Answer 2

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}\, .$$

Iterating:

$$\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}$$