Proof involving Stirling numbers of the second kind

Question

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

Answer 1

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

Answer 2

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.