Summation of: (binomial coefficients * Stirling numbers of the second kind)

Question

Problem: Simplify the following equation: \begin{equation} \sum\limits_{k=1}^n \dbinom{n}{k} \begin{Bmatrix} n\\ k \end{Bmatrix} k! \end{equation}

A solution: I am aware of the following relation: \begin{equation} \sum\limits_{t=1}^n t^n = \sum\limits_{k=1}^n \dbinom{n+1}{k+1} \begin{Bmatrix} n\\ k \end{Bmatrix} k! \end{equation}

Now, I am struggling to get to a somewhat similar (i.e., clean) expression for the given equation.

Thanks for your help!

Answer 1

Using the $[x^k]:f(x)$ to represent the coeficient of $x^k$ in the power series for $f(x)$.

We recall the well known expression for the Stirling numbers of the second kind \begin{eqnarray*} \begin{Bmatrix} n\\ k \end{Bmatrix} k! = n! [x^n]:(e^x-1)^k. \end{eqnarray*} So your sum can be rewritten as \begin{eqnarray*} \sum_{k=1}^{n} \dbinom{n}{k} \begin{Bmatrix} n\\ k \end{Bmatrix} k! &=& n! [x^n]: \sum_{k=1}^{n} \dbinom{n}{k}(e^x-1)^k \\ &=& n! [x^n]: (1+e^x-1)^n -1 \\ &=& n! [x^n]: e^{nx} -1 =\color{red}{n^n}. \end{eqnarray*}

Answer 2

The answer is $n^n$, as mentioned in Donald's answer, and here is a combinatorial proof.

Letting $[n]=\{1,2,\dots,n\}$, a function from $f:[n]\to [n]$ is specified by

• a subset $K$ of $[n]$ of size $k$ , for some $1\le k\le n$, equal to the range of $f$,
• a partition of the domain $[n]$ into $k$ parts, and
• an ordering of those $k$ parts.

The interpretation is that $f(x) = y$ when $x$ is in part number $i$, and $y$ is the $i^{th}$ smallest element of $K$.