For natural numbers $k\leq n$, [[Number of k-Permutations of n Letters (Injections between Finite Sets)|we have counted]] that the number of *injections* $f:[k]\to [n]$ is given by ${n!}/{(n-k)!}$ (if $k>n$ then the [[Pigeonhole Principle|pigeonhole principle]] asserts that $f:[k]\to [n]$ cannot be injective; also if $k=n$ then an injection $f:[k]\to [n]$ must also be surjection and hence bijective which yields that that there are $n!$ permutations of $[n]$). The proof uses the fact that the values of $f(1), f(2),\dots, f(k)$ can be determined independently. What makes [[Surjection|surjections]] *harder* to count? We consider a few ideas below. Let's define $\text{Surj}(k,n)$ to be the number of surjections from $[k]$ to $[n]$. First note that if $k<n$ then $\text{Surj}(k,n)=0$ so we may assume that $k\geq n$. - **Idea 0**: Consider the possibilities for $f(1), f(2),\dots, f(k)$. We find that we cannot determine their values independently hence we cannot apply the product rule directly. - **Idea 1:** Consider the possibilities for $f^{-1}(1), f^{-1}(2), \dots, f^{-1}(n)$. First, $f^{-1}(1)$ can be any subset of $[k]$ with size at least $1$, by the surjectivity of $f$, and at most $k-(n-1)$, since we need at least $n-1$ elements of $[k]$ remaining to map to $\{ 2,3 \dots,n \}$. Next, $f^{-1}(1)$ can be any subset of $[k]\setminus f^{-1}(1)$ with size between $1$ and $k-\#f^{-1}(1)-(n-2)$ - and again we have dependence. However, we gain the following recurrence relation: $\text{Surj}(k,n)= \sum_{i=1}^{k-(n-1)} \binom{n}{i}\text{Surj}(k-i, n-1).$ - **Idea 2:** Partitioning by size of range yields and subtracting from [[Placing Labelled Balls into Labelled Boxes|total number of functions]] from $[k]\to [n]$, $n^k$ $\begin{align} \text{Surj}(k,n) &= n^{k}- \sum_{i=1}^{n-1} \#\{ \text{surjections } f: [k]\to [n] \mid \ \#f([k]) = i \} \\ &= n^{k} - \sum_{i=1}^{n-1} \# \binom{[n]}{i} \times \# \{\text{surjections } f: [k] \to \text{chosen }i\text{-element subset of $[n]$} \}\\ &= n^{k} - \sum_{i=1}^{n-1} \binom{n}{i}\text{Surj}(k, i) \end{align}$ - **Idea 3:** Partitioning the set of surjections $f:[k] \rightarrow[n]$ into two subsets based on whether $\left|f^{-1}(f(1))\right|=1$ or $\left|f^{-1}(f(1))\right|>1$ yields $\begin{equation} \operatorname{Surj}(k, n)=n \cdot(\operatorname{Surj}(k-1, n)+\operatorname{Surj}(k-1, n-1)) .\end{equation}$ > [!NOTE] Theorem > $\text{Surj}(k,n) = \sum_{j=0}^{n} (-1)^{n-j} j^{k} \binom{n}{j}$where $\text{Surj}(k,n)$ denotes the number of surjections $f:[k] \to [n]$. ###### Proof by Inclusion-Exclusion For $i\in [n]$, let $A_{i}=\{ f:[k] \to [n] \mid i \not\in f([k]) \}.$Then $\text{Surj}(k,n)= n^{k} - \#(A_{1} \cup A_{2} \cup \dots \cup A_{n}).$ By [[Inclusion-Exclusion Principle|inclusion-exclusion]], $\#\left( \bigcup_{i=1}^{n} A_{i} \right) = \sum_{\substack{I\subset[n] \\ I\neq \emptyset}} (-1)^{\#I+1} \#\left( \bigcap_{i\in I}A_{i} \right).$ Now $\bigcap_{i\in I} A_{i} =\{ f: [k] \to [n] \setminus I \}$ so $\#( \bigcap_{i\in I} A_{i}) = (n-\#I)^k$ which yields $\text{Surj}(k, n) = n^{k}- \sum_{\substack{I \subseteq [n] \\ I \neq \emptyset}} (-1)^{\#I +1} (n-\#I)^{k}$To gain a more concise expression, for a fixed $m \in [n]$, we count the number of subsets $I\subseteq[n]$ such that $\#I = m$: $\begin{align} \text{Surj}(k, n) &= n^{k}- \sum_{m=1}^{n} (-1)^{m+1} (n-j)^{k}\sum_{\substack{I \subseteq [n] \\ \#I = m}} 1 \\ &= n^{k}- \sum_{m=1}^{n} (-1)^{m+1}(n-m)^{k}\binom{n}{m} \\ &= \sum_{m=0}^{n} (-1)^{j} (n-m)^{k} \binom{n}{m} \end{align}$Finally, substituting $j=n-m$ and $\binom{n}{m}=\binom{n}{n-m}$ yield$\text{Surj}(k,n) = \sum_{j=0}^{n} (-1)^{n-j} j^{k} \binom{n}{j}.$ # Applications **Stirling numbers of the second kind**: A surjective function $f : [k] \to [n]$ induces a partition of $[k]$ into $n$ nonempty parts, by declaring $i \sim j$ if and only if $f(i) = f(j)$. The parts of the partition are precisely the preimages $f^{-1}(1)$, $f^{-1}(2)$, \dots, $f^{-1}(n)$. However, different surjections can induce the same partition if they differ by a relabelling of the target set $[n]$. This relabelling corresponds to an action of the symmetric group $S_n$ on the set of surjections $\text{Surj}(k, n)$, where $\sigma \in S_n$ acts on $f$ by composition: $(\sigma \cdot f)(i) = \sigma(f(i))$. This action is *free*, since no non-identity permutation fixes a surjection; and two surjections belong to the same orbit if and only if they define the same set partition. Therefore, by Burnside’s lemma (or simply by counting orbits under a free group action), the number of orbits — that is, the number of distinct partitions of $[k]$ into $n$ parts — is given by $S(k, n) = \frac{\# \text{Surj}(k, n)}{n!},$where $S(k, n)$ is known as a [[Stirling numbers of the second kind|Stirling number of the second kind]].