What is the combinatorial interpretation behind the recursive relation: $L(n,k+1)=\frac{n-k}{k\left(k+1\right)}L(n,k)$

What is the combinatorial interpretation behind the following recursive relation: $$L(n,k+1)=\frac{n-k}{k\left(k+1\right)}L(n,k)$$

Where $L(n,k)$ denotes Lah numbers.


I tried the same method ,setting $n+1 \mapsto n $ and $k \mapsto k+1$ gives:

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

It seems that after some algebra the desired relation can be derived,but does there exist a direct combinatorial proof?


It’s easier to interpret the equivalent equation

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

The lefthand side of $(1)$ is the number of ways to partition $[n]=\{1,2,\ldots,n\}$ into $k+1$ ordered lists and label one of the lists $a$ and another $b$. We can then append the list $b$ to the list $a$ to form a single list $c$ and mark the element of $c$ that was the first element of $b$. This produces a partition of $[n]$ into $k$ ordered lists, one of which contains a marked element that is not the first element of that list.

The lefthand side of $(1)$ is the number of ways to partition $[n]$ into $k$ ordered lists and mark one of the $n-k$ elements that are not the first element of any list. If we have one of these partitions, we can take the list $c$ that contains the marked element and split it into sublists that we mark $a$ and $b$: $a$ contains the elements that precede the marked element of $c$, and $b$ contains the marked element and those that follow it in $c$. Clearly this operation is the inverse of the operation described in the first paragraph, so I’ve described a bijection that establishes $(1)$.