Proof of Counting Surjections and Derangements

Throughout, $\operatorname{Surj}([n],[k])$ and $D_{n}$ are finite, as subsets of the finite sets $[k]^{[n]}$ and $S_{n}$ (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (ix), Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (iv), Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv)); the elements of $S_{n}$ are exactly the bijections $[n]\to[n]$ (Permutations of a Set and the Set of Permutations of [n] (iii)); and for $p\in\mathbb{N}_{0}$ and $S\subseteq[p]$ we have $\#([p]\setminus S)=p-\#S$, because $\#S\le p$ and $\#S+\#([p]\setminus S)=\#[p]=p$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iv), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (v), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i), The Difference of Two Natural Numbers with Zero (i)); the intervals $\{m,\dots,n\}$ of $\mathbb{N}_{0}$ are finite sets (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii)); and elements of $\mathbb{N}_{0}$, which is closed under products, are read in the field $\mathbb{R}$, where they and powers such as $(-1)^{j}$ lie, and where their differences, products and powers keep their values (Multiplication on Omega (i), The Structure of ℝ as a Field and an Ordered Ring (i), Maps Given by Iterated Operations: Partial Iterates, Images of Natural Numbers, Powers and Operations over a Finite Set (ii), Maps Given by Iterated Operations: Partial Iterates, Images of Natural Numbers, Powers and Operations over a Finite Set (iv), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (iv), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (iii), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (v)). All formulas follow from The Principle of Inclusion and Exclusion (i), after grouping the subsets by size (the maps $S\mapsto\#S$ and $S\mapsto\#A_{S}$ on the subsets $S$ of the index set are those of The Maps i ↦ #C(i) and S ↦ #S (i) and The Maps i ↦ #C(i) and S ↦ #S (ii)).

Step 1 (surjections avoid no value). Let $k\in\mathbb{N}_{0}$, $X=[k]^{[n]}$, and for $i\in[k]$ let $A_{i}=\{\varphi\in X:i\notin\varphi([n])\}$. A map $\varphi\in X$ lies in none of the $A_{i}$ exactly when every $i\in[k]$ is a value of $\varphi$, so

$$X\setminus\bigcup_{i=1}^{k}A_{i}=\operatorname{Surj}([n],[k])$$

by The Sets of Injections, Surjections and Bijections between Two Sets (ii).

Step 2 (the sets $A_{S}$). Let $S\subseteq[k]$. For nonempty $S$, $\varphi\in A_{S}$ means that no element of $S$ is a value of $\varphi$; for $S=\emptyset$, $A_{\emptyset}=X$. In both cases

$$A_{S}=\{\varphi\in X:\varphi(a)\in[k]\setminus S\text{ for every }a\in[n]\}.$$

A map $[n]\to[k]$ with all its values in $[k]\setminus S$ is a map $[n]\to[k]\setminus S$, and conversely (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (iii)); so $A_{S}=([k]\setminus S)^{[n]}$, and by Counting Maps, Injections, Bijections and Permutations (i)

$$\#A_{S}=(k-\#S)^{n}.$$

Step 3 ((i)). By Steps 1 and 2 and The Principle of Inclusion and Exclusion (i) with $m=k$, and then Counting Subsets (iii) with $A=[k]$ and $g:\mathbb{N}_{0}\to\mathbb{R}$, $g(j)=(-1)^{j}(k-j)^{n}$ with $k-j$ and its power formed in $\mathbb{R}$,

$$\#\operatorname{Surj}([n],[k])=\sum_{S\in\mathcal{P}([k])}(-1)^{\#S}(k-\#S)^{n}=\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}.$$

Step 4 (derangements fix no point). Now let $X=S_{n}$ and, for $i\in[n]$, $A_{i}=\{\sigma\in S_{n}:\sigma(i)=i\}$. A permutation lies in none of the $A_{i}$ exactly when it fixes no point, so $X\setminus\bigcup_{i=1}^{n}A_{i}=D_{n}$ (Derangements (ii)). For $S\subseteq[n]$, both for $S=\emptyset$ and for nonempty $S$,

$$A_{S}=\{\sigma\in S_{n}:\sigma(i)=i\text{ for every }i\in S\}.$$

Step 5 (a permutation fixing $S$ permutes the rest). Let $S\subseteq[n]$, $C=[n]\setminus S$ and $\sigma\in A_{S}$. If $a\in C$ and $\sigma(a)=i\in S$, then $\sigma(a)=\sigma(i)$, so $a=i\in S$ by injectivity, which is impossible; hence $\sigma(C)\subseteq C$. If $b\in C$, then $b=\sigma(a)$ for some $a\in[n]$, and $a\notin S$, since otherwise $b=\sigma(a)=a\in S$; hence every $b\in C$ is the value of $\sigma$ at a point of $C$. Therefore the restriction of $\sigma$ to $C$ (Domains and Restrictions of Maps (ii)), taken with codomain $C$ (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (iii)), is injective and surjective, that is, an element $\sigma|_{C}$ of $\operatorname{Bij}(C,C)$ (The Sets of Injections, Surjections and Bijections between Two Sets (iii)).

Step 6 (restriction is a bijection onto $\operatorname{Bij}(C,C)$). The map $\rho:A_{S}\to\operatorname{Bij}(C,C)$, $\sigma\mapsto\sigma|_{C}$, is injective: two elements of $A_{S}$ with the same restriction agree on $C$, and on $S$ both are the identity, so they agree on $[n]=C\cup S$. It is surjective: for $\beta\in\operatorname{Bij}(C,C)$, gluing $\beta$ with the identity map of $S$ gives a bijection $\sigma:[n]\to[n]$, since $C\cap S=\emptyset$ and $C\cup S=[n]$ (Gluing Maps on Disjoint Domains, and Shrinking the Codomain (i), Gluing Maps on Disjoint Domains, and Shrinking the Codomain (ii)); $\sigma$ fixes every point of $S$, so $\sigma\in A_{S}$, and $\rho(\sigma)=\beta$. Since $\#C=n-\#S$, Counting through Bijections, Injections and Surjections (i) and Counting Maps, Injections, Bijections and Permutations (iii) give

$$\#A_{S}=\#\operatorname{Bij}(C,C)=(n-\#S)!.$$

Step 7 ((ii)). By Steps 4 and 6 and The Principle of Inclusion and Exclusion (i) with $m=n$, and then Counting Subsets (iii) with $A=[n]$ and the map $g:\mathbb{N}_{0}\to\mathbb{R}$ given by $g(j)=(-1)^{j}(n-j)!$ for $j\le n$ and $g(j)=0$ for $j>n$ (Maps Defined by Cases (i)), whose value at $\#S$ is $(-1)^{\#S}(n-\#S)!$ (as $\#S\le n$ for $S\subseteq[n]$),

$$\#D_{n}=\sum_{S\in\mathcal{P}([n])}(-1)^{\#S}(n-\#S)!=\sum_{j=0}^{n}(-1)^{j}\binom{n}{j}(n-j)!.$$

Step 8 ((iii)). Let $j\in\{0,\dots,n\}$. By Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (v), $j!\,(n-j)!\binom{n}{j}=n!$. As $j!\neq0$ in $\mathbb{R}$ (Natural Numbers and Factorials Read in the Reals: the Order Carries Over, One Is Least, and Factorials Are Positive, Recursive and Nondecreasing (iii)), dividing by $j!$ gives

$$\binom{n}{j}(n-j)!=\frac{n!}{j!}.$$

Substituting this into Step 7 and taking the common factor $n!$ out of the sum (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (i)),

$$\#D_{n}=\sum_{j=0}^{n}(-1)^{j}\frac{n!}{j!}=n!\sum_{j=0}^{n}\frac{(-1)^{j}}{j!}.$$