# Lah numbers and Stirlng numbers both kind relation proof

How can i prove this? $$L(n,k)=\displaystyle\sum_{\substack{j=0}}^{n}|s(n,j)|S(j,k)$$

• show your works – emonHR Nov 19 '19 at 19:29
• I stared with \begin{align*} x^{\overline{n}}=x(x+1)\cdots (x+n-1)=\sum_{k=1}^n|s(n,k)|x^{k}\qquad \qquad n>0 \end{align*} – Thiago Milani Cabral Nov 19 '19 at 19:53

We seek to evaluate

$$\sum_{j=k}^n {n\brack j} {j\brace k}.$$

Using the standard EGFs this becomes

$$\sum_{j=k}^n n! [z^n] \frac{1}{j!} \left(\log\frac{1}{1-z}\right)^j j! [w^j] \frac{1}{k!} \left(\exp(w)-1\right)^k \\ = \frac{n!}{k!} [z^n] \sum_{j=k}^n \left(\log\frac{1}{1-z}\right)^j [w^j] \left(\exp(w)-1\right)^k.$$

Now since $$\log\frac{1}{1-z} = z + \cdots$$ we may extend the sum (variable $$j$$) beyond $$n$$ with no additional contribution (observe the coefficient extractor $$[z^n]$$):

$$\frac{n!}{k!} [z^n] \sum_{j\ge k} \left(\log\frac{1}{1-z}\right)^j [w^j] \left(\exp(w)-1\right)^k.$$

Note also that $$\exp(w)-1 = w + \cdots$$ so the coefficient extractor $$[w^j]$$ starting at $$j=k$$ covers the entire series for $$\left(\exp(w)-1\right)^k$$ and we may write

$$\frac{n!}{k!} [z^n] \left(\exp\left(\log\frac{1}{1-z}\right)-1\right)^k.$$

Next note that we have the formal power series identity

$$\exp\log\frac{1}{1-z} = \frac{1}{1-z}$$

which we prove by observing that it says that permutations are sets of cycles, i.e.

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{P} = \textsc{SET}(\textsc{CYC}(\mathcal{Z})).$$

This means we may continue with

$$\frac{n!}{k!} [z^n] \frac{z^k}{(1-z)^k}.$$

This is

$$\frac{n!}{k!} [z^{n-k}] \frac{1}{(1-z)^k} = \frac{n!}{k!} {n-k+k-1\choose k-1} = \frac{n!}{k!} {n-1\choose k-1}$$

which is indeed the definition of a Lah number. We have by inspection of the EGF

$$\frac{1}{k!} \left(\frac{z}{1-z}\right)^k$$

that Lah numbers represent the combinatorial class

$$\textsc{SET}(\textsc{SEQ}_{\ge 1}(\mathcal{Z})).$$

Compare with Stirling numbers of the second kind, which are

$$\textsc{SET}(\textsc{SET}_{\ge 1}(\mathcal{Z})).$$