Prove the identity $x^n = \sum^{n}_{k=0}S_{n,k}(x)_k$ 
Prove the following identity: $$x^n = \sum^{n}_{k=0}S_{n,k}(x)_k \space \space \space\space\space\space\space\space\space\space\space\space\space (n \geq 0)$$.

We are talking clearly about Stirling numbers of the second kind here. I don't know what exactly $(x)_k$ means, but in my script I have something defined like this:
$$x_0 := 1$$
$$(x)_n := x(x-1)(x-2)\ldots(x-n+1) = \sum_{k=0}^{n}(-1)^{n+k}s_{n,k}x^k$$
Any ideas about what it exactly talks about and how can I prove this problem?
 A: That is trivial to prove by assuming that $x$ is a non-negative integer. Assume that $|A|=n$ and $|B|=x$.
The LHS counts the number of functions $f:A\to B$. The RHS counts the number of functions from $A$ to $B$, according to the size of $f(A)$, since the Stirling number $S_{n,k}$ accounts for the number of ways for partitioning $A$ in $k$ pieces.
On the other hand, if two polynomials agree on $\mathbb{N}$, they agree on $\mathbb{R}$, too, and that proves the identity in the general case.
A: $(x)_k$ can be expressed as $\frac{x!}{(k-1)!} = \binom{x}{k}k!$
To distribute $n$ distinct objects into $x$ distinct boxes with empty boxes allowed, we have $$x^n \space \text{ways}$$
Or we could choose $k$ boxes to distribute the $n$ objects into with no empty boxes allowed, from $k=0$ to $k=n$
To choose the $k$ boxes we have $\binom{x}{k}$ ways.
To distribute $n$ objects into the $k$ boxes with no empty boxes allowed, we have:
$$k!S_{n,k} \space \text{ways}$$
Therefore, the number of ways to $n$ distinct objects into $x$ distinct boxes with empty boxes allowed, we have:
$$x^n = \sum^{n}_{k=0}\binom{x}{k}k!S_{n,k} $$
A: This also has a straightforward algebraic proof for $x=q$ with $q$ an integer which then extends to $q$ a complex number.
Recall the combinatorial  species  of  set
partitions which is given by
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z})),$$
producing the generating function
$$\exp(u(\exp(z)-1))$$
and in particular
$${n\brace k}
= n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$
Now we have
$$q^n = 
\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(qz) \; dz
\\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\sum_{p=0}^q {q\choose p} (\exp(z)-1)^p\; dz
\\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\sum_{p=0}^q {q\choose p} \times p! \times \frac{(\exp(z)-1)^p}{p!}\; dz.$$
Extracting the coefficient we obtain
$$\sum_{p=0}^q {q\choose p} \times p! \times {n\brace p}.$$
But $${q\choose p} \times p! = q^{\underline{p}}$$
and we have the claim.
A: See http://faculty.kfupm.edu.sa/ICS/malalla/Teaching/ICS253/TextBook/Apps_Ch6.pdf
page 102 on the pdf gives a nice explanation
The falling-factorial $x_k$ represents the number one-to-one functions from a $x$-set to a $k$-set
$S_{n,k}$ represents the number of $k$ sized partitions of n
So, we have $x_k$ $k$ sized partitions, and $S_{n,k}$ ways to organize these $k$ sized partitions
A: This identity can be proven by induction on $n$. The base case is trivial $x^0 = 1 = S_{0,0}(x)_0$. For the induction case we have 
\begin{align}
\sum_{k=0}^{n+1}S_{n+1,k}(x)_k &= \sum_{k=0}^{n+1}(S_{n,k-1}+k S_{n,k})(x)_k\\
&=\sum_{k=0}^{n+1}S_{n,k-1}(x)_k + \sum_{k=0}^{n+1}k S_{n,k}(x)_k\\
&=\sum_{k=0}^{n}S_{n,k}(x)_{k+1} + \sum_{k=0}^{n}k S_{n,k}(x)_k\\
&=\sum_{k=0}^{n}(x-k)S_{n,k}(x)_{k} + \sum_{k=0}^{n}k S_{n,k}(x)_k\\
&=x \sum_{k=0}^{n}S_{n,k}(x)_{k}.
\end{align}
Then by the induction hypothesis we obtain $\sum_{k=0}^{n+1}S_{n+1,k}(x)_k = x^{n+1}$.
