Stirling numbers combinatorial proof

This is a Homework Question.

I am required to give a Combinatorial proof for the following.

$$S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$$

Hint given is : Show that $n!S(m,n)$ equals the number of onto functions $f\colon A \rightarrow B$ when $ |A|=m$ and $|B|=n. $

There were some other combinatorial proof questions on the assignment which I found easier to do but this one not so much. Could use help.

Solution 1:

Let $T$ denote the set of functions from $f:A\to B$ where $|A|=m$ and $|B|=n$ and $$S=\{f\in T \mid f \text{ is surjective}\}$$

If $f$ is surjective, then $f^{-1}(b)$ is non-empty for all $b\in B$. There are $S(m,n)$ many ways, to partition $m$ elements into $n$ non-empty set. For each such partition $A_1,\dots, A_n$, there are $n!$ ways to assign the pre-images $f^{-1}(b_1),\dots,f^{-1}(b_n)$, so $$|S| = n!S(m,n)$$

Now count the elements of $S$ again in an other way: For each $b\in B$, define $$M_b = \{ f: A\to B \mid f^{-1}(b)=\varnothing\}$$ Then $$S = T \setminus\bigcup\limits_{b\in B}M_b$$ Now use the Inclusion-exclusion principle to calculate $|S|$.

Solution 2:

Step 1:

We will partition the set $A$ with $m$ elements into $n$ blocks (nonempty subsets) and each of these blocks are then connected to each $n$ elements of the set $B$. Each block has $n!$ ways to connect with the set $B$, i.e, One such partition has $n!$ onto functions. Thus,

$\#\{f:A\to{B}:f \text{ is onto}\}$ = $n!$ $\times$ Number of partitons of the $m$ element set $A$ into $n$ nonempty blocks.

Take, Number of partitons of the $m$ element set $A$ into $n$ nonempty subsets =$S(m,n)$, Stirling numbers of the second.

$\#\{f:A\to{B}:f \text{ is onto}\}$=$n!\times S(m,n)$

Step 2:

$\#\{f:A\to B\}=n^m$

$$ \#\{f:A\to{B}:f\text{ is onto}\}=n^m-\Bigg[ \#\text{ of onto functions from $A$ to $B$ whose range misses atleast one element of $B$} \Bigg] $$ Lets take, $\#\text{ of onto functions from $A$ to $B$ whose range misses atleast one element of $B$}\equiv \#\text{ of onto }\geq{1}$

$$ \#\{f:A\to{B}:f\text{ is onto}\}=\binom{n}{0}n^m-\bigg[\#\text{ of onto }\geq{1}\bigg]\\=\binom{n}{0}n^m-\Bigg[\binom{n}{1}(n-1)^m-\bigg(\#\text{ of onto }\geq{2}\bigg)\Bigg]\\=\binom{n}{0}n^m-\Bigg[\binom{n}{1}(n-1)^m-\bigg(\binom{n}{2}(n-2)^m-\Big[\#\text{ of onto }\geq{3}\Big]\bigg)\Bigg]\\=\binom{n}{0}n^m-\Bigg[\binom{n}{1}(n-1)^m-\bigg(\binom{n}{2}(n-2)^m-\Big[........\# \text{ of onto }\geq{n-1}\Big]\bigg)\Bigg]\\=\binom{n}{0}n^m-\binom{n}{1}(n-1)^m +\binom{n}{2}(n-2)^m-\binom{n}{3}(n-3)^m+\binom{n}{4}(n-4)^m-.......\binom{n}{n-1}1^m=\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}(n-k)^m $$

$$ \#\{f:A\to{B}:f \text{ is onto}\}=\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}(n-k)^m=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m $$

From Step 1 and Step 2, $$ \#\{f:A\to{B}:f\text{ is onto}\}=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m=n!\times S(m,n) $$ The Stirling numbers of the second kind $$ \color{blue}{S(m,n)=\frac{1}{n!}.\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m} $$