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

Question

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?

Answer 1

$(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} $$

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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