4.3. Counting principles

In the tutorials, it was argued that for any two finite sets $A$ and $B$, $|A\cup B|\le |A|+|B|$ and equality holds if the sets are disjoint. Can I say something stronger in the general case?

All sets are assumed to be finite in the section.

Proposition.

If $A\subseteq B$, then $|B\setminus A|=|B|-|A|$.

Proof:

Obviously $A$ and $B\setminus A$ are disjoint sets, so by the result from the tutorials, $|B|=|B\setminus A|+|A|$. Using that $A\subseteq B$, I get $|A|\le |B|$ and so the result follows.

The inclusion-exclusion principle

Corollary.

For any sets $A$ and $B$,

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

Proof:

By the proposition,

$$|A\cup B|=|A\setminus (A\cap B)\cup B\setminus (A\cap B)\cup A\cap B|$$ $$=|A|-|A\cap B|+|B|-|A\cap B|+|A\cap B|=|A|+|B|-|A\cap B|$$

Inclusion-exclusion principle.

For any finite family of finite sets $A_0,A_1,\dots ,A_{n-1}$,

$$\left|\bigcup _{i<n}{A}_i\right|=\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|.$$

You will need this technical lemma to complete the proof:

Lemma.

For $0<s\le n$,

$$\sum _{\tau \in [n+1{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|=\sum _{\tau \in [n{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|+\sum _{\tau \in [n{]}^{s-1}}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|.$$

Proof of lemma:

By associativity and commutativity of the intersection,

$$\sum _{\tau \in [n+1{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|=\sum _{\begin{array}{c}\tau \in [n+1{]}^s\\ n\notin \tau \end{array}}\left|\bigcap _{i\in \tau }{A}_i\right|+\sum _{\begin{array}{c}\tau \in [n+1{]}^s\\ n\in \tau \end{array}}\left|\bigcap _{i\in \tau }{A}_i\right|$$ $$=\sum _{\tau \in [n{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|+\sum _{\tau \in [n{]}^{s-1}}\left|\bigcap _{i\in \tau \cup \{n\}}{A}_i\right|=\sum _{\tau \in [n{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|+\sum _{\tau \in [n{]}^{s-1}}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|.$$

Proof of the inclusion-exclusion principle:

By induction on $n$. The case when $n=1$ is trivial. The case when $n=2$ is the corollary at the beginning of this section.

I will assume the inclusion-exclusion principle holds for any family of finite sets of size $n$. Now let $A_0,\dots ,A_n$ be an arbitrary family of $n+1$ finite sets.

On the one hand, expanding the left-hand side and using the inductive hypothesis twice:

$$\left|\bigcup _{i\le n}{A}_i\right|=\left|\bigcup _{i<n}{A}_i\right|+|A_n|-\left|\bigcup _{i<n}{A}_i\cap A_n\right|$$ $$=\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|+|A_n|-\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|$$

On the other hand, expanding the right-hand side by ordering the sum by the size of $\tau$, I apply the lemma above and simplify:

$$\sum _{\varnothing ⊊\tau \subseteq n+1}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|=\sum _{0<s\le n+1}\sum _{\tau \in [n+1{]}^s}(-1{)}^{s+1}\left|\bigcap _{i\in \tau }{A}_i\right|=\sum _{0<s\le n+1}\left((-1{)}^{s+1}\sum _{\tau \in [n+1{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|\right)$$ $$=\sum _{0<s\le n+1}\left((-1{)}^{s+1}\sum _{\tau \in [n{]}^s}\left|\bigcap _{i\in \tau }{A}_i\right|-(-1{)}^s\sum _{\tau \in [n{]}^{s-1}}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|\right)$$ $$=\sum _{0<s\le n+1}\left(\sum _{\tau \in [n{]}^s}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|-\sum _{\tau \in [n{]}^{s-1}}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|\right)$$ $$=\sum _{0<s\le n+1}\sum _{\tau \in [n{]}^s}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|-\sum _{0<s\le n+1}\sum _{\tau \in [n{]}^{s-1}}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|$$

The first double sum is just

$$\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|;$$

and the latter double sum, the indexing goes from $\tau \in [n{]}^0=\{\varnothing \}$ to $\tau \in [n{]}^n=\{n\}$. When $\tau =\varnothing$, the intersection is just $A_n$; therefore the second double sum may be rewritten as

$$\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\cap A_n\right|-|A_n|.$$

Combining both, I see that they are equal, hence the theorem is proved.

Alternative proof.

Let $B_i:=A_i\setminus A_n$ for $i<n$ and notice that ${\bigcup }_{i\le n}{A}_i={\bigcup }_{i<n}{B}_i\cup A_n$ which is a disjoint union and thus $\left|{\bigcup }_{i\le n}{A}_i\right|=\left|{\bigcup }_{i<n}{B}_i\right|+|A_n|$. Moreover,

$$\bigcap _{i\in \tau }{B}_i=\bigcap _{i\in \tau }{A}_i\setminus \bigcap _{i\in \tau }(A_i\cap A_n).$$

Exercise.

Complete the proof.

For example, for three sets, we have $n=\{0,1,2\}$, so the right-hand sum iterates over three singletons, three complements of singletons and $n$ (there are seven nonempty subsets of $n$ in this case). Therefore,

$$|A_0\cup A_1\cup A_2|=|A_0|+|A_1|+|A_2|-|A_0\cap A_1|-|A_0\cap A_2|-|A_1\cap A_2|+|A_0\cap A_1\cap A_2|.$$

Just as a sanity check, I write the following “obvious” fact, which can be of course proved using much simpler methods.

Corollary.

Assume, in addition to the hypotheses of the inclusion-exclusion principle, that the sets are pairwise disjoint. Then,

$$\left|\bigcup _{i<n}{A}_i\right|=\sum _{i<n}|A_i|.$$

Proof:

If the sets are pairwise disjoint, all intersections of two or more are empty. Therefore, only the cases when $\tau$ are singleton sets contribute to the sum, which simplifies to the above.

Application: Euler’s totient function

Let $\phi (n)$ denote the number of invertible elements of ${\mathbb{Z}}_n$. In Chapter 2, I proved that an integer $k$ is invertible mod $n$ if and only if $k\perp n$. I will show you a formula for computing $\phi (n)$ when the prime factorization of $n$ is known.

Suppose that $n={\prod }_{i=1}^r{p}_i^{{\alpha }_i}$ where the $p_i$ are distinct primes and $\alpha \ge 1$. Therefore, $k\perp n$ if and only if no $p_i$ divides $k$. Let $A_i$ be the set of integers $\le n$ that are divisible by $p_i$. The union of all the $A_i$ is thus precisely the set of elements of ${\mathbb{Z}}_n$ that are not invertible.

For each $i$, $A_i$ consists of the multiple of $p_i$, of which there are $n/p_i$. Similarly, for any prime factors of $n$, $p_{i_1},\dots ,p_{i_q}$, there are $n/p_{i_1}\cdots p_{i_q}$ many integers that share that prime factor. By the inclusion-exclusion principle, the number of integers $\le n$ that share no prime factors with $n$ is

$$\phi (n)=n-\sum _{p\mid n}\frac{n}{p}+\sum _{p<q}\frac{n}{pq}\pm \cdots =n\prod _{p\mid n}\left(1-\frac{1}{p}\right).$$

Application: derangements

In many situations, the above formula may be simplified. One such example is when the summand $\left|{\bigcap }_{i\in \tau }{A}_i\right|$ depends only on the size of $\tau$ (and not the particular elements of $\tau$).

Corollary.

Add to the hypotheses of the inclusion-exclusion principle the condition that there is a function $\omega$ such that $\left|{\bigcap }_{i\in \tau }{A}_i\right|=\omega (|\tau |)$ for all $\tau$. Then,

$$\left|\bigcup _{i<n}{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{n}{k})\omega (k).$$

Proof:

By the inclusion-exclusion principle, it is sufficient to notice that

$$\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\left|\bigcap _{i\in \tau }{A}_i\right|=\sum _{\varnothing ⊊\tau \subseteq n}(-1{)}^{|\tau |+1}\omega (|\tau |)=\sum _{k=1}^n\sum _{\tau \in [n{]}^k}(-1{)}^{|\tau |+1}\omega (|\tau |)$$ $$=\sum _{k=1}^n\sum _{\tau \in [n{]}^k}(-1{)}^{k+1}\omega (k)=\sum _{k=1}^n(-1{)}^{k+1}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\omega (k).$$

A derangement is a permutation with no fixed points. That is, let $\phi \in {\Phi }_X$ be a bijection $X\to X$. Then $\phi$ is called a derangement if for all $x\in X$, $\phi (x)\ne x$. How many of the $|X|!$ permutations are derangements? I will denote the number of derangements of a set of size $n$ by $!n$. Thus obviously $!n\le n!$.

Exercise.

Show that $!n=(n-1)(!(n-1)+!(n-2))$ by using a combinatorial argument, that is, without using the formula below.

Derangement formula.

$$!n=\sum _{k=0}^n\frac{(-1{)}^{k}n!}{k!}.$$

From Calculus, I know that the McLaurin series of the exponential function gives me

$$e^x=\sum _{k=0}^{\infty }\frac{x^k}{k!},$$

and thus $1/e\approx 0.37$ is a good approximation of the probability that a random permutation of $n$ objects, for large $n$, is a derangement. This limit converges rather quickly, and so with high probability, a random shuffle of cards will leave at least one card in the same place, for instance.

Exercise.

Show that $n!={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)!k$ and give a combinatorial interpretation of it.

The stars and bars theorem

Suppose I have $k$ bins and $n$ indistinguishable objects to put in them. If bins can be left empty, in how many ways can I place the objects in the bins?

The correct way to think about this problem is to ignore the bins and instead picture the bars $k-1$ separating the bins. As an example, here I placed an object in the first bin, left the second bin empty, three objects in the third bin, and so on.

$$\star ||\star \star \star |\star |\star |$$

Interchanging two stars makes no difference and I consider the arrangement the same (that’s what the object being indistinguishable means). There are two ways of counting the number of such arrangements. First, notice I have $n$ stars and $k-1$ bars for a total of $n+k-1$ symbols being permuted. The stars and bars are indistinguishable among themselves, so I must divide by each permutation of the two groups. In total, there are

$$\frac{(n+k-1)!}{n!(k-1)!}$$

star and bars arrangements. Alternatively, I can think of this as selecting, from a set of $n+k-1$ symbols, those that will be drawn as bars, or those that will be drawn as stars. In other words, respectively,

$$\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)\left(\genfrac{}{}{0ex}{}{n+k-1}{n}\right)$$

Of course, all of these numbers are equal.

Application: Number of Diophantine solutions

How many positive integers solve the equation

$$x_1+x_2+\cdots +x_{246}=2025?$$

What about non-negative solutions?