I have been looking for mathematical proof for the expression to find the Stirling numbers of the second, $S(m,n)$. But I find it hard to understand.
My Attempt
We have two sets $A$ and $B$ wth $N(A)=m$ and $N(B)=n$, and we need to find the total number of onto functions from $A$ to $B$.
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 $$ S(m,n)=\frac{1}{n!}.\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m $$
Can I consider this as a well defined simple proof for the Stirling number of the second kind formula ?. Someone give a better explanation particularly for Step 2 ?