Generating function of Lah numbers

Question

Let $L(n,k)\!\in\!\mathbb{N}_0$ be the Lah numbers. We know that they satisfy $$L(n,k)=L(n\!-\!1,k\!-\!1)+(n\!+\!k\!-\!1)L(n\!-\!1,k)$$ for all $n,k\!\in\!\mathbb{Z}$. How can I prove $$\sum_nL(n,k)\frac{x^n}{n!}=\frac{1}{k!}\Big(\frac{x}{1-x}\Big)^k$$ without using the explicit formula $L(n,k)\!=\!\frac{n!}{k!}\binom{n-1}{k-1}$?

Attempt 1: $\text{LHS}=\sum_nL(n\!-\!1,k\!-\!1)\frac{x^n}{n!}+\sum_n(n\!+\!k\!-\!1)L(n\!-\!1,k)\frac{x^n}{n!}\overset{i.h.}{=}?$

Attempt 2: $\text{RHS}\overset{i.h.}{=}$ $\frac{1}{k}\frac{x}{1-x}\sum_nL(n,k\!-\!1)\frac{x^n}{n!}=$ $\frac{1}{k}\frac{x}{1-x}\sum_nL(n\!-\!1,k\!-\!1)\frac{x^{n-1}}{(n-1)!}=$

$\frac{1}{k(1-x)}\sum_nn\big(L(n,k)-(n\!+\!k\!-\!1)L(n\!-\!1,k)\big)\frac{x^n}{n!}=?$

Answer 1

We have \begin{align} f_k(x)&:=\sum_{n\in\Bbb Z}L(n,k)\frac{x^n}{n!}\\ &=\sum_{n\in \Bbb Z}L(n-1,k-1)\frac{x^n}{n!}+\sum_{n\in \Bbb Z}(n+k-1)L(n-1,k)\frac{x^n}{n!}\\ &=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+\sum_{j\in \Bbb Z}(j+1+k-1)L(j,k)\frac{x^{j+1}}{(j+1)!}\\ &=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{j!}+(k-1)\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{(j+1)!}\\ &=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+xf_k(x)+(k-1)\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{(j+1)!} \end{align} hence $$(1-x)f_k(x)=\sum_{j\in \Bbb Z}L(j,k-1)\frac{x^{j+1}}{(j+1)!}+(k-1)\sum_{j\in \Bbb Z}L(j,k)\frac{x^{j+1}}{(j+1)!}.$$ Now we take the derivatives to get $$-f_k(x)+(1-x)f'_k(x)=f_{k-1}(x)+(k-1)f_k(x)$$ hence $$(1-x)f'_k(x)-kf_k(x)=f_{k-1}(x).$$ Multipliying by $(1-x)^{k-1}$ and using the formula for $f_{k-1}$ we get $$(1-x)^kf'_k(x)-k(1-x)^{k-1}f_k(x)=\frac{x^{k-1}}{(k-1)!}$$ so $$((1-x)^kf_k(x))'=\frac{x^{k-1}}{(k-1)!}.$$ Integrating, we get the wanted result up to another term (namely $C(1-x)^k$) but it should vanish using the value at $0$ and the initial definition of Lah numbers.

Answer 2

The given recurrence relation can be used to show that the Lah number $L(n,k)$ counts the number of poset structures on a set with $n$ elements that are a disjoint union of $k$ non-empty chains.

In the language of combinatorial species, $L(n,k)$ counts the number of $E_k\circ L_+$-structures on a set of cardinality $n$, where $E_k$ is the species of sets of size $k$ and $L_+$ is the species of non-empty linear orders.

Since $E_k$ has exponential generating function $E_k(x)=\frac{x^k}{k!}$ and $L_+$ has exponential generating function $L_+(x)=\frac x{1-x}$, $E_k(L_+)$ has exponential generating function $E_k(L_+(x))=\frac 1{k!}\left(\frac x{1-x}\right)^k$.

Therefore, $$ \sum_{n=0}^k L(n,k)\frac{x^n}{n!} = \frac 1{k!}\left(\frac x{1-x}\right)^k $$ as required.