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.
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).