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

  • $\begingroup$ show your works $\endgroup$ – emonHR Nov 19 '19 at 19:29
  • $\begingroup$ 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*} $\endgroup$ – 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})).$$

| cite | improve this answer | |

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.