2
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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!}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .