Skip to content

3.24 Stirling number formula

Proposition

\(S(k,n)=\frac{1}{n!}\cdot\left|\phi:[k]\to[n]:\phi\text{ is surjective}\right|\)

Interpretation of \(\left|\phi:[k]\to[n]:\phi\text{ is surjective}\right|\): We have \(k\) balls and \(n\) boxes labelled. Every box has at least one ball

Proof

\(\Phi:\left\lbrace\phi:[k]\to[n]:\phi\text{ is surjective}\}\right.\to\left\lbrace\text{equivalence relations on }[k]\text{ with }n\text{ equivalence classes}\right\rbrace\)

Where \(\phi\mapsto(x\sim y\text{ if and only if }\phi(x)=\phi\left(y)\right)\) and we know \(\forall i= 1,...,n,\phi^{-1}(\{i\})\neq \empty\)

image​

Here every equivalence relation has exactly \(n!\) surjective functions producing it, so the division principle implies the desired result

How to count surjective functions?

Consider subtraction principle: (All possible functions) - (non surjective functions)

image​

Part 1. Inclusion-exclusion principle

Let \(A_1,...,A_n\) be finite sets, then \(|A_{1}\cup\ldots\cup A_{n}|=\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\bigcap\limits_{j\in J}A_{j}\right |\)

Particular Cases

n = 1, \(J\) can be \(\{1\}\)

\(|A_{1}|=\sum\limits_{J\subseteq\{1\},J\neq\emptyset}(-1)^{|1|+1}|\bigcap\limits_{j\in\left\lbrace1\right\rbrace} A_{1}|=\left|A_{1}\right|\)

n = 2, \(J\) can be \(\{1\},\{2\},\{1,2\}\)

\(|A_{1} \cup A_{2}| = (-1)^{2} | \bigcap\limits_{j \in \{1\}}A_{j} |\)​\(+ (-1)^{2} | \bigcap\limits_{j \in \{2\}}A_{j} |\)​\(+(-1)^{3}|\bigcap\limits_{j\in\{1,2\}}A_{j}|=|A_{1}|+|A_{2}|-|A_{1}\cap A_{2}|\)

image​

Proof(Important)

Let \(S=\{(x,J)\in (A_{1}\cup...\cup A_{n})\times \{\text{non-empty subsets of }\{1,.. .,n\}\}|x\in \bigcap_{j\in J}A_{j}\}\) recall that \(\bigcap\limits_{j\in\left\lbrace1\right\rbrace}A_{j}=A_{1}\)

e.g. if \(x\in A_1\cap A_2\) it contributes \((x,\{1\}),(x,\{2\})\) and \((x,\{1,2\})\) to \(S\)

Notices \(\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1 )^{|J|+1}\left|\bigcap\limits_{j\in J}A_{j}\right|=\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\left\lbrace\left(y,K\right)\in S:K=J\right\rbrace \right|\) (fix K, where \(y\in\bigcap_{j\in J}A_{j}\) )

Since \(y\in A_1\cup...\cup A_n\) as well, then we can partition that set according to the value of \(y\)

\(=\)​\(\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1 )^{|J|+1}\sum\limits_{x\in A_1\cup...\cup A_{n}}\left|\left\lbrace\left(y,K\right )\in S: K=J,y=x\right\rbrace\right|\)

\(=\sum\limits_{x\in A_1\cup...\cup A_{n}}\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\left\lbrace\left(y,K\right)\in S:K=J,y=x\right\rbrace \right|\)​

Let's analyze\(\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1 )^{|J|+1}\left|\left\lbrace\left(x,K\right)\in S:K=J\right\rbrace\right|\)

Suppose that \(x\in A_{j1}\cap ...\cap A_{jk}\) but \(\forall j\notin\left\lbrace j1,\ldots,jk\right\rbrace\). Then \(x\notin A_{j}\cap(A_{j1}\cap ...\cap A_{jk})\)

image​

In this case, the pairs, that contribute to this formula are indexed by all possible non-empty subsets of \(\{j1,...,jk\}\)

What about signs?

image​

\((-1)^{0+1}\binom{k}{0}+ (-1)^{1+1}\binom{k}{1}+ (-1)^{2+1}\binom{k}{2}+ (-1)^{3+1} \binom{k}{3}+ \dots + (-1)^{k+1}\binom{k}{k}= 1.\)

\((-1)(1-1)^k = 0\)

  • Contribution from singletons
  • Contribution from 2-element sets
  • Contribution from \(K=\{j_{1},j_{2},...j_{k}\}\)

Thus \(\sum\limits_{x\in A_1\cup...\cup A_{n}}\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\left\lbrace\left(y,K\right)\in S:K=J,y=x\right\rbrace \right|=\sum\limits_{x\in A_1\cup...\cup A_{n}}1=\left|A_{1}\cup...\cup A_{n}\right |\)

Now we want to remove the condition of \(J\neq \empty\), then

Another way to write the inclusion-exclusion formula

Suppose \(\exists A\), such that \(A_1, \dots, A_n \subseteq A\) .

Convention: We say that \(\bigcap_{j \in \emptyset} A_j = A\)

\(\left|A\setminus(A_{1}\cup\dots\cup A_{n})\right|=\sum\limits_{J\subseteq\{1,\dots,n\}} (-1)^{\left|J\right|}\left|\bigcap_{j\in J}A_{j}\right|\)

Part 2. how to count the number of surjections?

Let \(A=\) all possible functions \([k]\to [n]\)

\(A_{1}=\left\lbrace\phi:\left\lbrack k\right\rbrack\to\left\lbrack n\right\rbrack :\phi^{-1}\left(\left\lbrace1\right\rbrace\right)=\emptyset\right\rbrace\), \(A_{2}=\left\lbrace\phi:\left\lbrack k\right\rbrack\to\left\lbrack n\right\rbrack :\phi^{-1}\left(\left\lbrace2\right\rbrace\right)=\emptyset\right\rbrace\),....

\(A_{n}=\left\lbrace\phi:\left\lbrack k\right\rbrack\to\left\lbrack n\right\rbrack :\phi^{-1}\left(\left\lbrace n\right\rbrace\right)=\emptyset\right\rbrace\)

Then \(|\text{surj}|=\left|A\setminus(A_{1}\cup\cdots\cup A_{n})\right|\)

Thus \(\bigcap_{j \in J}A_{j}= \left\{ \phi : [k] \to [n] \ \Big| \ \phi^{-1}(J) = \bigcup _{j \in J}\phi^{-1}(\{j\}) = \emptyset \right\}\) and \(\left|\bigcap_{j\in J}A_{j}\right|=(n-\left|J\right|)^{k}\)​

For example \(\phi\in A_{1}\cap A_{3}\cap A_{5}\)

image​

Then \(\left|A\setminus(A_{1}\cup\dots\cup A_{n})\right|=\) \(\sum_{J\subseteq\{1,\dots,n\}}(-1)^{\left|J\right|}(n-\left|J\right|)^{k}\) \(=\sum_{j=0}^{n}\sum_{\substack{J\subseteq\{1,\dots,n\}\\\left|J\right|=j}}(-1)^{j} (n-j)^{k}\)

\(=\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\left(n-j\right)^{k}\)

Remark: This result is divisible by \(n!\)

Then \(S(k,n)=\frac{1}{n!}\cdot\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\left(n-j\right )^{k}\)

‍