proof sum of power using Stirling number question is prove
$$ 1^{k} + 2^{k} + 3^{k} + \dots + n^{k} = \sum_{i=1}^{n} S(k,i) \cdot i! \cdot {{n+1}\choose{i+1}} $$
In my opinion, LHS means number of functions from X to Y (X has 'k' element and Y has 'n' element)
And $$\sum_{i=1}^{k} S(k,i) \cdot i!$$ on RHS means number of function from X to Y (X has 'k' element and Y has only 'i' element).
But I can't get the meaning of ${n+1}\choose{i+1}$ on the RHS.
I know ${n}\choose{i}$ means choose i element among n element in Y but I can't get why add 1 respectively.
 A: Hint: Yes, you are in the right track, but notice that in the LHS each function is counted a bunch of times, say that you have a function, call it $f$, in $[n]^{[k]}$(meaning from $[k]=\{1,2,\cdots ,k\}$ to $[n]=\{1,2,\cdots ,n\}$). Let $m_f=\max _{x\in [k]}f(x)$ then notice that $f$ also belongs to $[m_f]^{[k]},$ to $[m_f+1]^{[k]}$ all the way to $[n]^{[k]}$. The $\binom{n+1}{i+1}$is choosing the image of $f$ (the first $i$ numbers of the set) and an integer $1\leq \ell\leq n+1$(the biggest number chosen) such that it counts how many times you are counting the function $f$(as seen before each function has a multiplicity in the LHS).
A: We seek to simplify
$$\sum_{q=1}^n {k\brace q} q! {n+1\choose q+1}.$$
This is
$$k! [z^k] \sum_{q=1}^n {n+1\choose q+1} (\exp(z)-1)^q
\\ = k! [z^k] \frac{1}{\exp(z)-1}
\sum_{q=1}^n {n+1\choose q+1} (\exp(z)-1)^{q+1}
\\ = k! [z^k] \frac{1}{\exp(z)-1}
\sum_{q=2}^{n+1} {n+1\choose q} (\exp(z)-1)^{q}.$$
Observe that with $k\ge 1$ this is
$$- k! [z^{k+1}] \frac{z}{\exp(z)-1}
+ k! [z^{k+1}] \frac{z\exp((n+1)z)}{\exp(z)-1}
\\ = k! [z^{k+1}] \frac{z(\exp((n+1)z)-1)}{\exp(z)-1}
\\ = k! [z^k] \sum_{q=0}^n \exp(qz)
= \sum_{q=1}^n q^k.$$
Note that when we regard $k$ as a parameter we can write the initial
sum as
$$\sum_{q=1}^k {k\brace q} q! {n+1\choose q+1}.$$
This is because if $n\lt k$ we may raise to $k$ because the binomial
coefficient is zero on the added range. If $n\gt k$ we may lower to $k$ due to the Stirling number. We then have
$$\bbox[5px,border:2px solid #00A000]{
(n+1) n \sum_{q=1}^k {k\brace q} 
\frac{(n-1)^{\underline{q-1}}}{q+1}.}$$
We find e.g. letting $k=3$ that
$$\sum_{q=1}^n q^3
= (n+1) n \left[ {3\brace 1} \frac{1}{2}
+ {3\brace 2} \frac{n-1}{3}
+ {3\brace 3} \frac{(n-1)(n-2)}{4}\right].$$
