# Proof involving Stirling numbers of the second kind

For all real numbers $x$, and all non-negative integers $n$, $$x^n = \sum_{k=0}^{n} S(n,k)\frac{x!}{(x-k)!}$$

I have a 2 questions with the proof that my textbook presents.

First they say that they will prove this for a stronger statement -- that the equality holds for all positive integers $x$. (1) Why is this a stronger statement? Aren't stronger statements usually more generalized?

The LHS is the number of all functions from $1,\ldots,n$ to $1,\ldots,x.$ (2) Why is this "obvious"? (What does it mean?).

-
Are you sure that the stronger statement isn’t that the equality holds for all positive real numbers $x$, with the fraction replaced by $x(x-1)\dots(x-k+1)$? – Brian M. Scott Jan 5 '13 at 23:43
I'm not sure about the first, but for the second. If we are mapping elements of $\{1,...,n\}$ to elements of $\{1,...,x\}$, for each of 1 to $n$, we have $x$ choices for our value of our function, so in total we have $x^n$ possibilities for our function. – Alex J Best Jan 5 '13 at 23:44
@BrianM.Scott Yeah, I'm looking at it right now and it says, in italics, all positive integers x. – AlanH Jan 5 '13 at 23:51
As stated, it doesn’t really make sense when $x$ is a positive integer less than $k$: it requires you to take the factorial of a negative integer. – Brian M. Scott Jan 6 '13 at 0:01
@BrianM.Scott Maybe it's assumed for all positive integers greater than equal to $k$? – AlanH Jan 6 '13 at 1:15

I don’t know exactly what your text actually says, but the general fact is that

$$x^n=\sum_{k\ge 0}\left\{n\atop k\right\}x^{\underline k}\;,\tag{1}$$

where $x^{\underline k}=x(x-1)(x-2)\dots(x-k+1)$; this holds for integer $n\ge 0$. Note that if $x$ is an integer and $x\ge k$, then $$x^{\underline k}=\frac{x!}{(x-k)!}\;,$$ and $(1)$ becomes your formula.

As for the second question, if $n$ and $x$ are positive integers, choosing a function $f$ from $\{1,\dots,n\}$ to $\{1,\dots,x\}$ is the same as choosing a value in $\{1,\dots,x\}$ for each $k\in\{1,\dots,n\}$. There are $x$ different ways to choose $f(1)$. For each of those there are $x$ ways to choose $f(2)$, so there are altogether $x^2$ combinations of values of $f(1)$ and $f(2)$. Each new choice of an $f(k)$ can be made in $x$ different ways, so in the end you have $x^n$ possible sequences of choices, i.e., $x^n$ functions from from $\{1,\dots,n\}$ to $\{1,\dots,x\}$.

-

The number $x^n$ is the number of functions from a size-$n$ set to a size-$x$ set. For example, $3^2=9$ is the number of functions from $\{a,b\}$ into $\{1,2,3\}$. You have $f(a)=\text{one of }1,2,3$ and $f(b)=\text{one of }1,2,3$, and it can be any of the three each time, so there are $9$ such functions.

The Stirling number $S(n,k)$ is the number of (un-ordered) partitions of a set of size $n$ into $k$ subsets. By definition of "partition" these are non-empty non-intersecting subsets whose union is the whole size-$n$ set.

For every function $f$ from a size-$n$ set $A$ to a size-$x$ set $B$, there is a partition of the domain $A$ defined by saying $x,y$ both belong to the same part if and only if $f(x)=f(y)$. So one way of specifying a function is this: First choose that partition. Call the number of parts $k$. Then choose which of the $x$ members of $B$ you'll map the members of the first part to. There are $x$ possible choices. Then choose which member of $B$ you'll map the members of the second part to. There are $x-1$ possible choices. Keep going, until you've chosen from among $x(x-1)(x-2)\cdots(x-k+1)$ possibilities.

So there are $S(n,k)$ ways to choose a partition of size $k$, then $x(x-1)(x-2)\cdots(x-k+1)$ possible choices of which function you pick from among those yielding that partition. Thus $S(n,k)x(x-1)(x-2)\cdots(x-k+1)$ is the number of functions that take $k$ values.

Each such function takes has a number of values in its range that is either $1$ or $2$ or $\cdots\cdots$ or $n$. So the number of functions is $$\sum_{k=1}^n S(n,k)x(x-1)(x-2)\cdots(x-k+1).$$ But the number of functions is also $x^n$. Therefore those numbers are equal.

This assumes $n$ and $x$ are non-negative integers, and that is less general than the statement that it holds for $n$ and non-negative integer and $x$ real. The latter statement must be true because the expression on both sides of the "$=$" is a polynomial in $x$, and a polynomial in one variable is determined by its value at infinitely many points.

-