Here's a curious polynomial identity I stumbled upon: for $r, n \in \mathbb{N}$ and $r > n$, \[ f(n, r) = r^n - \binom{r}{1}(r - 1)^n + \binom{r}{2}(r - 2)^n + \dots + (-1)^{r - 1}r = 0. \] This can be proved by brute force expansion, but there is a really nice combinatorial argument in connection with the following problem.
How many surjective functions of the form $f\colon \{1, 2, \dots, n\} \to \{1, 2, \dots, r\}$ are there?
Consider such a function $f$; for each $i \in \{1, 2, \dots, n\}$, we have $r$ choices for $f(i)$, giving us at most $r^n$ functions. However, $f$ must be surjective, so we must get rid of those functions which fail to hit some $j \in \{1, 2, \dots, r\}$ in the codomain. There are $(r - 1)^n$ functions whose codomain misses a particular $j$, and $\binom{r}{1}$ ways to choose this missing element, hence we take away their product. This isn't the end, since now we've removed those functions which miss at least two points, say $j, k \in \{1, 2, \dots, r\}$ in the domain, more than once! Thus, we must add back $\binom{r}{2}(r - 2)^n$ of those. Again, we've over-counted functions which miss at least three points, hence we take them away, and so on.
This argument uses what's known as the Inclusion-Exclusion Principle. When we're done, we see that the answer turns out to be \[ \begin{aligned} f(n, r) &= r^n - \binom{r}{1}(r - 1)^n + \binom{r}{2}(r - 2)^n + \dots + (-1)^{r - 1}r \\ &= \sum_{k = 0}^r (-1)^{r - k} \binom{r}{k}k^n. \end{aligned} \] However, when $r > n$, there is no way to make a function $f\colon \{1, 2, \dots, n\} \to \{1, 2, \dots, r\}$ surjective: there are simply too many targets in the codomain! This means that $f(n, r) = 0$.
There is another way of thinking about counting surjective functions: for each $j \in \{1, 2, \dots, r\}$, we have to choose it's pre-image $f^{-1}(j) \subset \{1, 2, \dots, n\}$. These pre-images must be non-empty (otherwise, $f$ would not be surjective), mutually exclusive, and exhaustive. Thus, we are really looking for the number of ways of partitioning $n$ objects (in the domain) into $r$ labelled boxes (in the co-domain). This is precisely what Stirling numbers of the second kind are for. Although they are defined using $n$ objects and $r$ unlabeled boxes, we simply insert a factor of $r!$, i.e. the number of ways of labeling those $r$ boxes. This gives us a proof of the relation \[ \begin{Bmatrix}n \\ r\end{Bmatrix} = \frac{1}{r!}f(n, r) = \frac{1}{r!}\sum_{k = 0}^r (-1)^{r - k} \binom{r}{k}k^n. \]
Proof by expansion
For the sake of completeness, here's a proof of the identity using binomial expansions! Our expression can be rewritten as \[ f(n, r) = \sum_{k = 0}^r (-1)^{r - k} \binom{r}{k}k^n = \sum_{k = 0}^r (-1)^{k} \binom{r}{k}(r - k)^n. \] Expanding, this gives \[ \sum_{k = 0}^r (-1)^{k} \binom{r}{k}\sum_{j = 0}^n\binom{n}{j}r^j k^{n - j}. \] Now, we can collect the coefficients of the powers of $r$. For instance, the coefficient of $r^n$ is \[ \sum_{k = 0}^r (-1)^k \binom{r}{k} = (1 - 1)^r = 0. \] More generally, the coefficient of $r^m$, $0 \leq m < n$ is given by \[ \sum_{k = 0}^r (-1)^k\binom{r}{k}\binom{n}{m} k^{n - m}. \] Note that when we perform this sum, $\binom{n}{m}$ can be pulled out, and the exponent $n - m$ of $k$ is a constant. Thus, what we are really interested in are the sums \[ S_a = \sum_{k = 0}^r (-1)^k \binom{r}{k}k^a, \qquad a = n - m, \; 1 \leq a \leq n. \] We evaluate these using the usual trick of differentiation; expand \[ (1 - x)^r = \sum_{k = 0}^r \binom{r}{k}x^k, \] and differentiate with respect to $x$. This gives \[ -r(1 - x)^{r - 1} = \sum_{k = 0}^r \binom{r}{k}kx^{k - 1}. \] Putting $x = 1$ gives us $S_1 = 0$. Now, multiply by $x$ and differentiate again, giving \[ -r(1 - x)^{r - 1} + r(r - 1)x(1 - x)^{r - 2} = \sum_{k = 0}^r \binom{r}{k}k^2x^{k - 1}. \] Putting $x = 1$ gives us $S_2 = 0$. We simply repeat this process, multiplying by $x$ and differentiating to get all $S_a = 0$, $1 \leq a \leq n$. Note that we can do this because $r > n$; at every stage, the lowest coefficient of $(1 - x)$ on the left is $r - a \geq r - n \geq 1$. Thus, the left hand side always vanishes at $x = 1$.
This shows that all the coefficients of $r$ are identically zero when $r > n$, proving that $f(n, r) = 0$.
Comments
Post a Comment