Combinatorial proof of ${n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$

Question

It's known that Stirling numbers of the second kind satisfy the following relation:

$${n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$$

However I have not ever seen any proof of this relation,I would like to see a combinatorial proof if that's possible,thanks for who helps me.

Answer 1

This is the same as $$k^n=\sum_{r=0}^k r!{n\brace r}\binom kr.$$ The left side counts the number of maps from $[n]=\{1,\ldots,n\}$ to $[k]$. The $r$-th summand on the right counts the number of these whose image has size $r$.

Answer 2

Firstly we can just divide by $k!$ at the end. $${n \brace k}=\frac{k^n - \sum_{r=1}^{k-1}\frac{{n \brace r}k!}{(k-r)!}}{k!}$$ Now we can prove this very simply going term by term. Let us assume we have $k$ distinct boxes and $n$ distinct boxes. The number of ways to distribute the $n$ objects is $k^n$.

Now Let us look at the cases where at least one box is empty. There must be some subset of boxes that have at least one object. Let us denote the number of boxes with at least one object as $r$.

The number of ways to distribute $n$ objects into $r$ distinct boxes such that at least one box has an element is ${n \brace r}r!$. We know we aren't double counting, since all objects are distinct, So any box with at least one object has to be different from another box.

Now any $r$ of the $k$ boxes may be the ones with objects, so we have to multiply by $\binom{k}{r}$. So the number of ways of filling $r$ boxes out of $k$ boxes becomes $\binom{k}{r}{n \brace r}r!$. We know we aren't double counting here because only the $r$ selected boxes have objects, and they have at least one object, so they all have distinct objects.

Now the number of ways to put $n$ objects into $k$ boxes such that all boxes have at least one object, is just the number of ways to distribute the objects minus the number of ways to distribute the objects such that at least one is empty.

So $r$ can range anywhere from $1$ to $k-1$. So we need to subtract $\sum_{r=1}^{k-1} \binom{k}{r}{n \brace r}r!$ which is equal to $\sum_{r=1}^{k-1} \frac{{n \brace r}k!}{(k-r)!}$.

Now this is the number of ways to distribute the numbers into $k$ distinct boxes such that all boxes have at least one element. Now since all boxes have at least one object, no 2 boxes have the same objects, so the number of ways to distribute them into $k$ subsets, is just that divided by $k!$.

Answer 3

A combinatorial argument can be used to demonstrate the validity of

$\tag 1 \displaystyle k^n=\sum_{r=1}^k r!{n\brace r}\binom kr$

See the next section for part of the logic.

To get the formula

$\quad \displaystyle {n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$

from there you must use algebra.

HINT 1: Show that

$\quad \displaystyle k!{n\brace k} = k^n - \sum_{r=1}^{k-1} r!{n\brace r}\binom kr$

HINT 2: Simplify

$\quad \displaystyle \frac{r! \times \binom kr }{k!}$

---

Counting functions

Here is a part of the counting argument:

How many functions map a set $A$ with $n$ elements into a set $B$ with $k$ elements where the image contains $r$ elements?

We use the rule of product:

Recall the theory

$\quad$ Induced surjection and induced bijection

There are ${n\brace r}$ ways to partition $A$ into $r$ blocks to get the quotient of $A$.

There are $\binom kr$ way of selecting the image in $B$.

There are $r!$ ways of specifying the correspondence between the quotient and the image.

ANS: $\displaystyle {n\brace r}\binom kr \, r!$