# Summation including Stirling numbers of the second kind

I would like to show the following: (I am pretty sure it is correct but was not able to prove it.)

$$\begin{eqnarray*} &&\sum_{j=1}^{n}j\binom{n}{j}S\left( n,j\right) j! =n(n^n-(n-1)^n) \\ && \end{eqnarray*}$$

where $$S(n,j)$$ stands for the Stirling numbers of the second kind.

First of all let's change it like the following:
Divide both sides by $$n$$ and simplify the $$\frac{j}{n}$$ in the sum in the LHS with $$\binom{n}{j}$$: $$\frac{j}{n}\cdot\binom{n}{j}=\frac{j\cdot n!}{n\cdot j!\cdot(n-j)!}=\frac{(n-1)!}{(j-1)!\cdot(n-j)!}=\binom{j-1}{n-1}$$
So actually we want to prove the following: $$\displaystyle\sum_{j=1}^{n}{\binom{n-1}{j-1}\cdot j!\cdot S_{(n,j)}}=n^n-(n-1)^n$$
Now assume that $$A={\{1,2,\dotsb,n}\}$$. Then the RHS is equal to the number of all $$n$$-tuples of elements of $$A$$ that contain $$1$$, since $$n^n$$ is the number of all $$n$$-tuples of $$A$$ and $$(n-1)^n$$ is the number of all $$n$$-tuples of $$A$$ without $$1$$.

Now we'll prove that the LHS has the same value.
We'll prove that the number of all $$n$$-tuples of $$A$$ that have exactly $$j$$ different elements and have $$1$$ in them is equal to $$\binom{n-1}{j-1}\cdot j!\cdot S_{(n,j)}$$ :
Step1: First of all we'll chose the elements we want to use in our $$n$$-tuple. Including $$1$$ is one of the conditions so it's one of the elements we choose. Then we want $$j-1$$ other elements and our choices are $$\{2,3,\dotsb,n\}$$ so there are $$\binom{n-1}{j-1}$$ different ways for doing that.
Step2: Now we choose where to position the $$j$$ elements we picked in step1. For this we have to assign a set of positions of our $$n$$-tuple to our elements (and these sets shall be non-empty). For this there are exactly $$S_{(n,j)}$$ different ways. For each partition of $$\{1,2,\dotsb,n\}$$ (which are our positions in the $$n$$-tuple) to $$j$$ non-empty sets, if a position falls into the partition number $$i$$, then label this position with $$i$$. At last we have to fill our partitions with our pre-chosen elements! Since there are $$j$$ different labels of the positions of our $$n$$-tuple and we have $$j$$ elements, there are exactly $$j!$$ different ways to choose which element shall fill all of the positions labeled with each number.

So at last, there are $$\binom{n-1}{j-1}$$ methods for choosing the elements of our $$n$$-tuple and $$j!\cdot S_{(n,j)}$$ methods to place them in our n-tuple; so there are exactly $$\binom{n-1}{j-1}\cdot j!\cdot S_{(n,j)}$$ pairwise different $$n$$-tuples that have exactly $$j$$ different elements and also have the element $$\{1\}$$. So summing this for different $$j$$'s, we'll have the number of all different $$n$$-tuples that have the element $$\{1\}$$ and hence the proof is complete!

Using the Stirling number EGF we find for $$n\ge 1$$

$$\sum_{j=1}^n j{n\choose j} {n\brace j} j! = n \sum_{j=1}^n {n-1\choose j-1} {n\brace j} j! \\ = n \sum_{j=0}^{n-1} {n-1\choose j} {n\brace j+1} (j+1)! \\ = n \times n! [z^n] \sum_{j=0}^{n-1} {n-1\choose j} \frac{(\exp(z)-1)^{j+1}}{(j+1)!} (j+1)! \\ = n \times n! [z^n] (\exp(z)-1) \sum_{j=0}^{n-1} {n-1\choose j} (\exp(z)-1)^{j} \\ = n \times n! [z^n] (\exp(z)-1) \exp((n-1)z) \\ = n \times n! [z^n] (\exp(nz)-\exp((n-1)z)) = n (n^n - (n-1)^n).$$

as claimed. Here we have used the fact that set partitions have combinatorial class

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

which gives the EGF

$$\exp(u(\exp(z)-1))$$

so that

$$\sum_{n\ge j} {n\brace j} \frac{z^n}{n!} = [u^j] \exp(u(\exp(z)-1)) = \frac{(\exp(z)-1)^j}{j!}.$$