Rising Factorial and Stirling number of the 1st kind

Question

Is it true that

$$(x+1)^{\bar{n}}= \sum_{k \ge 0} \sum _{i=0}^{n} {i \choose k}s_{n,i}\,\,x^k \,\,\,\,?$$ where $s_{n,i}$ is the Stirling number of the first kind and the $\bar{n}$ denote rising factorial. If yes, could anyone please show me?

I have been able to prove that $$(x+1)^{\bar{n}}= \sum_{k \ge 0} s_{n+1,k+1}\,\,x^k \,\,\,\,$$

My goal is to try to get that $$s_{n+1,k+1} = \sum _{i=0}^{n} {i \choose k}s_{n,i}$$ by equating (comparing) both identities

Answer 1

Are you familiar with the identity $$ x^{\overline n} = \sum_{i=0}^n s_{n,i}x^i?\tag{$*$} $$ The desired result follows pretty quickly substituting $x+1$ for $x$ in $(*)$: $$ (x+1)^{\overline n}=\sum_{i=0}^n s_{n,i}(x+1)^i = \sum_{i=0}^ns_{n,i}\sum_{k\ge 0}\binom{i}kx^k. $$ Identity $(*)$ can be proved by induction on $n$ using the relation $s_{n+1,k}=s_{n,k-1}+ns_{n,k}$, combined with $x^{\overline{n+1}}=x\cdot x^{\overline n}+nx^{\overline n}$. There is also a combinatorial proof.

Answer 2

For the identity

$$\sum_{p=k}^n {n\brack p} {p\choose k} = {n+1\brack k+1}$$

we obtain on the LHS using formal power series

$$n! [z^n] \sum_{p=k}^n {p\choose k} \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^p$$

We have $\log\frac{1}{1-z} = z + \cdots$ so there is no contribution to the coefficient extractor when $p\gt n$ and we may continue with

$$n! [z^n] \sum_{p\ge k} {p\choose k} \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^p \\ = n! [z^n] \sum_{p\ge 0} {p+k\choose k} \frac{1}{(p+k)!} \left(\log\frac{1}{1-z}\right)^{p+k} \\ = n! [z^n] \left(\log\frac{1}{1-z}\right)^{k} \sum_{p\ge 0} {p+k\choose k} \frac{1}{(p+k)!} \left(\log\frac{1}{1-z}\right)^{p} \\ = n! [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k} \sum_{p\ge 0} \frac{1}{p!} \left(\log\frac{1}{1-z}\right)^{p} \\ = n! [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k} \exp\log\frac{1}{1-z} \\ = n! [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k} \frac{1}{1-z}.$$

For the RHS we start from

$$\sum_{n\ge 0} {n\brack k+1} \frac{z^n}{n!} = \frac{1}{(k+1)!} \left(\log\frac{1}{1-z}\right)^{k+1}$$

so that by differentiation

$$\sum_{n\ge 0} {n+1\brack k+1} \frac{z^n}{n!} = \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^{k} \frac{1}{1-z}.$$

We see that the LHS and the RHS have the same EGF and this proves the claim. Here we have made repeated use of the labeled combinatorial class

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

This is the decomposition of permutations into sets of disjoint cycles.