Inclusion–Exclusion, the Pigeonhole Principle and Double Counting: Examples and Counterexamples

Take the ambient set $X:=8=\{0,1,2,3,4,5,6,7\}$ and the subsets

$A_0:=\{0,1,2,3\},A_1:=\{2,3,4,5\},A_2:=\{3,4,6\},A_3:=\{5,6,7\}\mathrm{.}$

First the family $(A_i{)}_{i\in 3}$, a sieve family with ambient set $X$ and index set $I:=3$ (A finite family $(A_i{)}_{i\in I}$ of subsets of a finite set $X$, the intersections $A_J$ for $J\subseteq I$, and the convention $A_{\mathrm{\varnothing }}=X$). Every intersection $A_J$ for $\mathrm{\varnothing }\mathrm{\ne }J\subseteq 3$ is listed:

The union is $A_0\cup A_1\cup A_2=\{0,1,2,3,4,5,6\}$, of size $7$, and the sieve returns $(4+4+3)-(2+1+2)+1=7$. The complementary form returns $8-(4+4+3)+(2+1+2)-1=1$, and indeed $X\setminus (A_0\cup A_1\cup A_2)=\{7\}$.

Now the family $(A_i{)}_{i\in 4}$, with $A_3$ adjoined and $I:=4$:

The union is now all of $X$, of size $8$, and the sieve returns $(4+4+3+3)-(2+1+0+2+1+1)+(1+0+0+0)-0=14-7+1=8$. The complementary form returns $8-14+7-1+0=0$, and indeed $X\setminus (A_0\cup A_1\cup A_2\cup A_3)=\mathrm{\varnothing }$.

• Adjoining one set changes every level of the sum. Passing from three sets to four adds a singleton term, three pair terms, three triple terms and one four-element term, and the totals at each level move accordingly; what stays fixed is that the alternating combination reproduces the size of the union.

• The terms that vanish are not omitted. $A_{\{0,3\}}$ and the three four-element-family triples are empty, so their terms are $0$; they are still terms of the sum, and writing them keeps the count of terms at each level equal to the number of subsets of that size, which is what the grouping in [L3] asserts.

• Where the complementary form gets its extra term. It runs over all subsets of the index set, including $\mathrm{\varnothing }$, whose term is $\iota \mid X\mid$. That is the only place the ambient set enters the arithmetic, and it is why the ambient set has to be named as part of the family.

Take $A:=5$ and $B:=3$, so $n=\mid A\mid =5$ and $k=\mid B\mid =3$.

By the formula. The number of surjections from an $n$-element set onto a $k$-element set is ${\sum }_{i<k+1}(-1{)}^i\left(\genfrac{}{}{0px}{}{k}{i}\right)(k-i{)}^n$, read in $\mathbb{R}$ through $\iota$ gives

$\iota \mid \mathrm{Surj}(A,B)\mid ={\sum }_{i<4}(-1{)}^i\iota \left(\genfrac{}{}{0px}{}{3}{i}\right)\iota ((3-i{)}^5),$

whose four terms are

so the count is $243-96+3-0=150$.

By direct subtraction. Every function $A\to B$ has an image $S:=f[A]\subseteq B$, and the sets $\{f:f[A]=S\}$ for $S\subseteq B$ partition the set of all $3^5=243$ functions $A\to B$. A function with image exactly $S$ is precisely a surjection $A\to S$, so the number of functions with image of size $j$ is $\left(\genfrac{}{}{0px}{}{3}{j}\right)$ times the number of surjections from a five-element set onto a $j$-element set. Those numbers are $0$ for $j=0$, since $A\mathrm{\ne }\mathrm{\varnothing }$; $1$ for $j=1$, the constant function; and $2^5-2=30$ for $j=2$, since a function into a two-element set fails to be onto exactly when it is one of the two constants. Hence

$243=\left(\genfrac{}{}{0px}{}{3}{0}\right)\cdot 0+\left(\genfrac{}{}{0px}{}{3}{1}\right)\cdot 1+\left(\genfrac{}{}{0px}{}{3}{2}\right)\cdot 30+\left(\genfrac{}{}{0px}{}{3}{3}\right)\cdot \mid \mathrm{Surj}(A,B)\mid =0+3+90+\mid \mathrm{Surj}(A,B)\mid ,$

so $\mid \mathrm{Surj}(A,B)\mid =243-93=150$, in agreement.

• The second route is not a rearrangement of the first. It partitions the functions by their image and uses the surjection counts onto smaller sets, which at sizes $0$, $1$ and $2$ are established directly rather than by the formula. So the agreement is a genuine check on the formula at $n=5$, $k=3$.

• The last term of the formula is $0$ and it is not decoration. At $i=k$ the factor is $0^n$, which vanishes because $n\ge 1$; at $n=0$ it would be $0^0=1$ instead, and that is the single point where the convention of Exponentiation of natural numbers, $m^n$, and its agreement with the integer power in $\mathbb{R}$ is load bearing for this formula.

Take $A:=4=\{0,1,2,3\}$ and write a bijection $f:A\to A$ as the tuple $(f(0),f(1),f(2),f(3))$. The derangements of $A$ (The derangement number $D_n$: the number of bijections of an $n$-element set with no fixed point) are exactly

$\begin{array}{lll}(1,0,3,2)& (1,2,3,0)& (1,3,0,2)\\ (2,0,3,1)& (2,3,0,1)& (2,3,1,0)\\ (3,0,1,2)& (3,2,0,1)& (3,2,1,0)\end{array}$

so $D_4=9$. Each tuple lists four distinct values, hence is a bijection, and no entry equals its position.

Against the formula. $\iota (D_n)=\iota (n!){\sum }_{i<n+1}(-1{)}^i\mathrm{/}\iota (i!)$, with the term at $i=0$ equal to $1$ and $D_0=1$ gives

$\iota (D_4)=\iota (4!){\sum }_{i<5}\frac{(-1{)}^i}{\iota (i!)}=24(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24})=24\cdot \frac{9}{24}=9.$

Against the two recurrences. The earlier values are $D_0=1$, $D_1=0$, $D_2=1$ and, by the first recurrence, $D_3=3D_2+(-1{)}^3=3-1=2$. Then $\iota (D_n)=\iota (n)\iota (D_{n-1})+(-1{)}^n$ for $n\ge 1$, and $D_n=(n-1)(D_{n-1}+D_{n-2})$ for $n\ge 2$ gives $\iota (D_4)=\iota (4)\iota (D_3)+(-1{)}^4=4\cdot 2+1=9$ from its first clause, and $D_4=3(D_3+D_2)=3(2+1)=9$ from its second.

• The case analysis is on $f(0)$ and then on $f(1)$, and the remaining two positions are then forced or free according to whether the two leftover values can be placed without creating a fixed point. Where exactly one placement avoids a fixed point the tuple is determined; where both do, the subcase splits. The branching pattern therefore differs between the cases even though each contributes the same number of derangements.

• The recurrences are checked at their first legal indices too. The first recurrence is used at $n=3$ and at $n=4$, both at least $1$; the second at $n=4$, which is at least $2$. Neither is evaluated where its hypothesis fails.

For $n\in \mathbb{N}$ consider the real number

$r_n:=\frac{\iota (D_n)}{\iota (n!)},$

the quotient of the count of derangements of an $n$-element set (The derangement number $D_n$: the number of bijections of an $n$-element set with no fixed point) by the count of all its bijections, $\mid \mathrm{Bij}(n)\mid =n!$ (The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$). The quotient is legitimate because $n!\mathrm{\ne }0$. Dividing the derangement formula by $\iota (n!)$ gives

$r_n={\sum }_{i<n+1}\frac{(-1{)}^i}{\iota (i!)},$

so $r_n$ is the truncated alternating sum itself. Its first values, obtained from $D_0=1$, $D_1=0$, $D_2=1$ and the first recurrence $\iota (D_n)=\iota (n)\iota (D_{n-1})+(-1{)}^n$ ($\iota (D_n)=\iota (n)\iota (D_{n-1})+(-1{)}^n$ for $n\ge 1$, and $D_n=(n-1)(D_{n-1}+D_{n-2})$ for $n\ge 2$), are

This is a ratio of two counts and nothing else. Nothing among this page's declared prerequisites defines a probability space, a measure or an expectation, so $r_n$ is not called a probability here and no statement about random behaviour is made. What is asserted is exactly that the numerator counts the fixed-point-free bijections, that the denominator counts all of them, and that the quotient is the displayed alternating sum.