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.
 A: 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|$.
A: 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}
$$
A: Principle of Inclusion Exclusion: If $S$ is a set containing $N$ elements. Then the number of objects in $S$ having none of the properties $A_1,A_2,...,A_m$ is 
$$
N(A'_1\cap A'_2\cap ...\cap A'_m)=N-\Big[\sum_{i_1}N(A_{i_1})-\sum_{i_1,i_2}N(A_{i_1}\cap A_{i_2})+\sum_{i_1,i_2,i_3}N(A_{i_1}\cap A_{i_2}\cap A_{i_3})-.....\\
+(-1)^{k-1}\sum_{{i_1},{i_2},{i_3}...,{i_k}}N(A{i_1}\cap A_{i_2}\cap A_{i_3}\cap ...\cap A{i_k})+....+(-1)^{m-1}N(A_{1}\cap A_{2}\cap A_{3}\cap ....\cap A_{m})\Big]\\
\implies \boxed{N\Big(\bigcap_{i=1}^mA'_i\Big)=N-N\Big(\bigcup_{i=1}^mA_i\Big)\\
=N-\bigg[ \sum (-1)^{k-1}\sum_{{i_1},{i_2},{i_3}...,{i_k}}N(A{i_1}\cap A_{i_2}\cap A_{i_3}\cap ...\cap A{i_k}) \bigg]\\
=N-\bigg[ \sum (-1)^{k-1}\sum_{{i_1},{i_2},{i_3}...,{i_k}}N\Big(\bigcap_{i=1}^mA_i\Big)\bigg]}
$$
where ${i_1},_{i_2},...,_{i_k}$ are distinct in all the cases.
Let $A=\{a_1,a_2,...,a_m\}$ and $B=\{b_1,b_2,...,b_n\}$, where $m\geq n$, and let $S$ be the set of all functions $f:A\to B$. Then then number of elements in $S$ is, $N=N(S)=n^m$.
Let $A_i=\{b_i \text{is not in the range of }f\}$, then $N(A'_i)$ counts the number of functions that have $b_i$ in their range, ie., $N(A_i)=(n-1)^m,....,N(A_1\cap A_2\cap ...\cap A_k)=(n-k)^m$ for each $i=1,2,...,m$.
$$
\sum_{i_1}N(A_{i_1})={}^nC_1(n-1)^m\\
\sum_{i_1,i_2}N(A_{i_1}\cap A_{i_2})={}^nC_2(n-2)^m\\
.\\
.\\
\sum_{{i_1},{i_2},{i_3}...,{i_k}}N(A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap ...\cap A{i_k})={}^nC_k(n-k)^m
$$
$$
\#\{f:A\to B:f\text{ is onto}\}=N(A'_1\cap A'_2\cap ...\cap A'_m)=N-\Big[\sum_{i_1}N(A_{i_1})-\sum_{i_1,i_2}N(A_{i_1}\cap A_{i_2})+\sum_{i_1,i_2,i_3}N(A_{i_1}\cap A_{i_2}\cap A_{i_3})-.....\\
+(-1)^{k-1}\sum_{{i_1},{i_2},{i_3}...,{i_k}}N(A{i_1}\cap A_{i_2}\cap A_{i_3}\cap ...\cap A{i_k})+....+(-1)^{m-1}N(A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap ....\cap A_{i_m})\Big]
\\
=n^m-\Bigg[ {}^nC_1(n-1)^m-{}^nC_2(n-2)^m+{}^nC_3(n-3)^m-....(-1)^{k-1} .{}^nC_k(n-k)^m \Bigg]\\
={}^nC_0n^m-{}^nC_1(n-1)^m+{}^nC_2(n-2)^m-{}^nC_3(n-3)^m+....(-1)^{k} .{}^nC_k(n-k)^m \\
=\sum_{k=0}^n (-1)^k.{}^nC_k(n-k)^m=n!.\frac{1}{n!}\sum_{k=0}^n (-1)^k.{}^nC_k(n-k)^m=n!.S(m,n)
$$
