6.1. Counting#

How do we count things? $1, 2, 3, 4, 5, 6, 7, \ldots$. Sure. But can we determine the count of something without actually counting?

Using only letters and numbers, there are $218,340,105,584,896$ different possible passwords of length 8. There are $839,299,365,868,340,224$ different possible passwords of length 10. Sure, we could enumerate them all and count them. But good luck…

The Principles of Counting
The Pigeon Hole Principle
- Pigeon holes as functions
Generalized Pigeon Hole
Exercises

6.1.1. The Principles of Counting #

There are many algorithmic ways of counting. Here we look at 3.

Product Rule #

The product rule is the easiest method to understand.

Definition (product rule)

Given two choices, $n$ possibilities for the first, and $m$ possibilities for the second, then there are a total of $n \times m$ different combinations of choices.

Here’s a very simple example. Consider the set $S = \{a, b, c\}$. How many different sequences of length $3$ can be constructed using the elements of $S$? Well, we could list them all:

\[\begin{split} \begin{array}{lll} a, a, a \qquad & b, a, a \qquad & c, a, a \\ a, a, b & b, a, b & c, a, b \\ a, a, c & b, a, c & c, a, c \\ a, b, a & b, b, a & c, b, a \\ a, b, b & b, b, b & c, b, b \\ a, b, c & b, b, c & c, b, c \\ a, c, a & b, c, a & c, c, a \\ a, c, b & b, c, b & c, c, b \\ a, c, c & b, c, c & c, c, c \\ \end{array} \end{split}\]

That’s a lot. Or, we could apply the product rule.

For the first term of the sequence we have three possible choices: $a$, $b$, or $c$. For the second term of the sequence we have three possible choices: $a$, $b$, or $c$. For the third term of the sequence we have three possible choices: $a$, $b$, or $c$.

So, the total possible combination of choices is $3 \times 3 \times 3 = 27$.

The Product Rule for Sets #

The product rule can be made formal by considering sets and their Cartesian product.

Given two sets $A$ and $B$, the number of elements in $A \times B$ is $|A| \cdot |B|$. This may have been obvious from the Section on Cartesian Product.

This follows naturally from the product rule. The Cartesian product $A \times B$ is all tuples $(a,b)$ where $a \in A$ and $b \in B$. For the first coordinate, we have $n = |A|$ possible choices. For the second coordinate, we have $m = |B|$ possible choices. Therefore, the total number of tuples $(a,b)$ is $n \times m = |A| \cdot |B|$.

Let’s generalize this to any number of sets.

Let $A_1, A_2, A_3, \ldots, A_k$ be finite sets. Then:

\[ |A_1 \times A_2 \times A_3 \times \cdots \times A_k| = |A_1| \cdot |A_2| \cdot |A_3| \cdots |A_k| \]

Counting License Plates

Consider a province where the license plate format is $XYZ ABC$. Where $X,Y,Z$ are capital letters and $A,B,C$ are decimal digits. How many possible license plates are there?

We could proceed intuitively using the product rule. There are $26$ possible choices of letters for each of $X, Y, Z$. There are $10$ possible choices of digits for each of $A, B, C$. Therefore, the total number of license plates is:

\[ 26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 17,576,000 \]

We could also formalize this procedure.

Let $L = \{\text{A}, \text{B}, \text{C}, \ldots, \text{Y}, \text{Z}\}$ and $N = \{0,1,2,\cdots,8,9\}$. Clearly $|L| = 26$ and $|N| = 10$.

A license plate of the form $XYZ ABC$ can be viewed as a tuple $(l_1, l_2, l_3, n_1, n_2, n_3)$ and thus as an element of $L \times L \times L \times N \times N \times N$.

From the product rule applied to sets:

\[\begin{split} |L \times L \times L \times N \times N \times N| &= |L| \cdot |L| \cdot |L| \cdot |N| \cdot |N| \cdot |N| \\ &= 26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \\ &= 17,576,000 \end{split}\]

Sum Rule #

The sum rule applies when you must make a single choice from multiple groups.

Definition (sum rule)

Given a choice, where one can either choose from a group of $n$ or a group of $m$ possibilities, then there are a total of $n + m$ different choices.

This rule is actually quite simple and obvious. Consider picking your outfit of the day. In your closet you have 10 pairs of jeans and 5 pairs of chinos. How many different choices of pants do you have? 15, of course. You can wear one of your 10 pairs of jeans or one of your 5 pairs of chinos (but not both).

Counting Pets

You are adopting one pet from the local SPCA. Good job!

The shelter currently houses $17$ cats and $12$ dogs. How many choices for you have do your new pet?

You can either choose a cat or choose a dog. Therefore, there are $17+12 = 29$ choices.

The Sum Rule for Sets #

Given two sets $A$ and $B$, the number of elements in $A \cup B$ is $|A| + |B|$, so long as $A$ and $B$ share no elements.

This follows naturally from the union operation of disjoint sets. If $A$ and $B$ have no common elements, i.e. $A \cap B = \varnothing$, then their union contains all the elements of $A$ and all the elements of $B$ with no duplicates.

Let’s generalize this to any number of sets.

Let $A_1, A_2, A_3, \ldots, A_k$ be finite and pairwise disjoint sets. Then:

\[ |A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_k| = |A_1| + |A_2| + |A_3| + |A_k| \]

Sum and Product, together #

Of course, one may use the sum and product rule together.

Say you have to make one choice from group $A$ and a second choice from group $A$ or group $B$. Assuming the first and second choice can be the same choice, both the product rule and the sum rule apply.

For the first choice, there are $|A|$ possible choices. For the second choice, there are $|A| + |B|$ possible choices. The total number of choices is thus $|A| \cdot (|A| + |B|)$.

Here’s an example.

Counting Programming Language Variables

In most programming languages, the first character of a variable’s name must be a letter. From then on, characters may be numbers of letters. Assuming variables are case-sensitive, how many possible 4-character variable names are there?

There are 26 lower-case letters and 26 upper-case letters. There are also 10 individual decimal digit characters.

For a 4-character variable name we have 4 choices. The first choice must be a letter and thus there are $26+26 = 52$ possible choices. The second, third, and fourth choice can be a letter or a number, and thus there are $26+26+10 = 62$ possible choices.

In total, we have:

\[ 52 \cdot 62 \cdot 62 \cdot 62 = 12,393,056 \]

possible 4-character variable names.

Checkpoint

Counting rules

In some computer system, accounts must have a case-insensitive password of 6 to 8 characters in length. Those characters must only be letters, numbers, or one of $\texttt{!}$, $\texttt{\$}$, or $\texttt{?}$.

How many possible passwords are there to choose from?

Solution

Counting rules

For each character we can choose a letter, a number, or a special character. This is $26 + 10 + 3 = 39$ choices.

Passwords can be either 6, 7, or 8 characters long.

All length-6 passwords count: $39^6$.

All length-7 passwords count: $39^7$.

All length-8 passwords count: $39^8$.

Therefore, the total number of possible passwords is:

\[ 39^6 + 39^7 + 39^8 = 5,492,759,010,921 \]

The Principle of Inclusion-Exclusion #

The sum rule assumes that the sets from which you are choosing are disjoint. This is a strong assumption. When the sets to choose from are not disjoint, special care is needed so that choices are not double counted.

We may recall the following proposition from the section on Union and Intersection.

Proposition

For two sets $A$ and $B$ the cardinality of $A \cup B$ is given by:

\[ |A \cup B| = |A| + |B| - |A \cap B| \]

When $A$ and $B$ are disjoint sets, the sum rule tell us that $|A \cup B| = |A| + |B|$. When they are not disjoint, we must subtract the elements in $A \cap B$ to avoid double-counting those shared elements. This proposition can be called the subtraction rule.

More generally, the inclusion-exclusion principle applies to exclude items which are double counted, but then include items which have been doubly excluded.

This is easiest to see with the union of three sets.

../_images/Venn3.svg — Fig. 6.1 A Venn diagram of three sets.#

If we want to count the number of elements in the union of $A$, $B$, and $C$, there are many possibilities for double counting. The full formula is:

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C| \]

This formula says the following about $|A \cup B \cup C|$:

If $A$, $B$, and $C$ are all disjoint, then $|A \cup B \cup C| = |A| + |B| + |C|$, as expected by the sum rule.
If they are not disjoint, then $|A| + |B| + |C|$ double counts elements in the overlap of the sets. Thus, we remove one count for each element of $A \cap B$, $B \cap C$, and $A \cap C$.
However, in this removal process, we have removed too many counts for the elements of $A \cap B \cap C$. Notice these elements were triple counted by $|A| + |B| + |C|$. However, we have removed a total of three counts for each of those elements as they are all individually elements of $A \cap B$, $B \cap C$, and $A \cap C$. Thus, we must add back in $|A \cap B \cap C|$.

Generalizing the inclusion exclusion principle to many more sets is certainly possible, but the formula is unwieldy. Rather, consider a recursive construction.

Let $A$ and $B$ be sets, where $B$ itself is the union of two more sets $C$ and $D$ Then, we have:

\[\begin{align*} |A \cup B| &= |A| + |B| - |A \cap B| \\[2em] |B| = |C \cup D| &= |C| + |D| - |C \cap D| \\[2em] |A \cap B| &= |A \cap (B \cup C)| \\[0.5em] &= |(A \cap C) \cup (A \cap D)| \\[2em] |(A \cap C) \cup (A \cap D)| &= |A \cap C| + |A \cap D| - |(A \cap C) \cap (A \cap D)| \\[0.5em] &= |A \cap C| + |A \cap D| - |A \cap C \cap D| \\ \end{align*}\]

Putting all of these formulas together, we have:

\[\begin{split} |A \cup (C \cup D)| &= |A| + \left(|C| + |D| - |C \cap D|\right) - \left( |A \cap C| + |A \cap D| - |A \cap C \cap D| \right) \\[1em] &= |A| + |C| + |D| - |C \cap D| - |A \cap C| - |A \cap D| + |A \cap C \cap D| \end{split}\]

Checkpoint

Science Fair Inclusion-Exclusion

Your high school offers Biology, Chemistry, and Physics courses. There are $14$ students taking both Physics and Chemistry. There are $8$ students taking both Physics and Biology. There are $5$ students taking all three courses. There are $18$ students taking more than one science course.

You are looking for a partner for your school’s science fair. You are enrolled in Biology and Chemistry, and so you want your partner to also be enrolled in Biology and Chemistry. How many suitable partners are there to choose from?

Solution

Science Fair Inclusion-Exclusion

Let $P$ be physics students, $C$ be chemistry students, and $B$ be biology students. We know:

\[ |(P \cap B) \cup (P \cap C) \cup (B \cap C)| = 18 \]

We also know:

\[ |P \cap B| = 8, \quad\text{and}\quad |P \cap C| = 14, \quad\text{and}\quad |P \cap B \cap C| = 5 \]

From inclusion-exclusion:

\[\begin{split} |(P \cap B) & \cup (P \cap C) \cup (B \cap C)| \\[1em] &= |P \cap B| + |P \cap C| + |B \cap C| - |P \cap B \cap P \cap C| - |P \cap C \cap B \cap C| \\ &= |P \cap B| + |P \cap C| + |B \cap C| - 2|P \cap C \cap B| \\ \end{split}\]

Therefore, we have:

\[\begin{split} 18 &= 8 + 14 + |B \cap C| - 2(5) \\ |B \cap C| &= 28 - 8 - 14 \\ |B \cap C| &= 6 \end{split}\]

Finally, since we know ourselves belong to $B \cap C$, there are $6-1 = 5$ other people in both chemistry and biology who could be our partners.

6.1.2. The Pigeon Hole Principle #

../_images/PigeonHole.svg — Fig. 6.2 A pigeon in a cubby-hole.#

If there are 9 cubbys and 10 pigeons, there must be a cubby with more than one pigeon.

This is a simple idea that applies to more than just pigeons. If you have 9 lockers and 10 book bags, a locker must have more than one book bag.

This idea, when generalized, is the pigeon hole principle.

Theorem (pigeon hole principle)

Let $k$ be a positive integer. If there are more than $k$ objects to be placed into $k$ boxes, then at least one box contains two or more objects.

Proof:

Proceed by contrapositive. We look to prove that if every box contains fewer than 2 objects, then there are $k$ or fewer objects. There are $k$ boxes. Each box contains at most one object. Thus, the total number of objects is at most $k$. $\blacksquare$

The pigeon hole principle is perhaps the most simple proof you will see in this course. But, it is very powerful with many applications.

Birthdays and pigeons

Proposition

In any group of 367 people, at least two people have the same birthday

Proof: At most, there are 366 days in a year (because of leap years). Each of these 367 people are born on a particular day of those 366. Thus, by the pigeon hole principle, at least two people share the same birthday.

Here’s a more interesting and math-y example.

Divisors and pigeons

Proposition

For every integer $n$ there is a multiple of $n$ whose digits are only 0s and 5s.

Proof:

Consider the list of $n+1$ integers:

\[ 5,\ 55,\ 555,\ \ldots\ ,\ 555\ldots55 \]

where the last number has $n+1$ digits.

By Euclidean division with $n$ as the divisor, the possible remainders $r$ are $0 \leq r < n$. Thus, there are $n$ possible remainders.

We divide each of the numbers in our list by $n$. By the pigeon hole principle, since there are $n+1$ numbers in our list, at least two of them must have the same remainder.

The difference of these two numbers in our list is certainly divisible by $n$, since they have the same remainder. Moreover, the difference itself will have the form $55..5500...00$ and thus its digits are only 0s and 5s. $\blacksquare$

Pigeon holes as functions #

Recall from Injective, Surjective, Bijective an important fact about bijective functions. If a bijection exists between sets $A$ and $B$ then $|A| = |B|$. Now, what if $|A| > |B|$?

Recall that functions are always total. For $f: A \rightarrow B$, every element $a$ of $A$ must have an associated output, $f(a)$. When $|A| > |B|$, notice what the total property implies: the pigeon hole principle!

Let $P$ be the set of pigeons and $H$ be the set of pigeon holes with $|P| > |H|$.

No matter how you define $f: P \rightarrow H$, it is impossible for $f$ to be injective. That is, there must always be an element of $H$ which has more then one element of $P$ mapped to it.

Such a function from $P$ to $H$ with $|P| > |H|$ is the formalization of putting “objects” into “boxes”, as stated in the definition of the pigeon hole principle.

6.1.3. Generalized Pigeon Hole #

We can extend the pigeon hole principle to get an even stronger result. Rather than having “at least two objects are in the same box”, we can actually count the maximum number of objects in any box.

Theorem (generalized pigeon hole principle)

If $N$ objects are placed into $k$ boxes, then there is at least one box containing $\lceil N/k \rceil$ or more objects.

Proof:

Proceed by contrapositive. Suppose that none of the $k$ boxes contain more than $\lceil N/k \rceil -1$ objects. Then, the total number of objects must be $k \times \left( \lceil N /k \rceil -1 \right)$.

However, notice that:

\[ k \left( \bigg\lceil \frac{N}{k} \bigg\rceil -1 \right) < k \left( (\frac{N}{k} + 1) - 1\right) = N \]

Thus, there are strictly less than $N$ objects, a contradiction. Therefore, it must be that at least one box contains at least $\lceil N/k \rceil$ objects. $\blacksquare$

Birthdays and generalized pigeons

In a group of $100$ people, there are at least $9$ people which are born in the same month.

Why? Generalized pigeon hole principle. There are $12$ months in the year. By the generalized pigeon hole principle, there must be at least one month with $\lceil 100 / 12 \rceil = 9$, or more, people sharing that month as their birthday.

Try one yourself now.

Checkpoint

Dice and pigeons

How many times must you roll a pair of standard 6-sided dice to guarantee that you roll a $2$ three times?

Solution

Dice and pigeons

When you roll a pair of dice, there are $11$ unique outcomes:

\[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 \]

To guarantee you roll a $2$ three times, you must roll the dice a lot. In fact, with what we know (i.e. the (generalized) pigeon hole principle), we cannot guarantee that a $2$ will ever be rolled three times.

We can only guarantee that some outcome from the list of possible outcomes appears at least three times. For that, if we roll the dice 23 times ($\lceil 23 / 11 \rceil = 3$), then we are guaranteed that at least one of the outcomes occurs $3$ or more times.

6.1.4. Exercises #

Exercise 6.1

Recall that a byte consists of 8 binary digits. How many different bytes are there that begin with $1$ or end with $0$?

Solution to Exercise 6.1

In a byte there are 8 bits, and each bit belongs to $\{0,1\}$.

When a byte begins with $1$, there are $7$ remaining bits to choose from and so $2^7$ possible bytes.

When a byte ends with $0$, there are $7$ remaining bits to choose from and so $2^7$ possible bytes.

Now, how many bytes both start with $1$ and end with $0$? Those number of bytes were double counted. If we fix the first and last bit, there are $6$ remaining bits to choose from and so $2^6$ such bytes.

In total we have $2^7 + 2^7 - 2^6 = 192$ possible bytes.

Exercise 6.2

On the internet, every computer must have an IP address.

In Version 4 of the IP standard, there are 3 possible “classes” of IP addresses for computers connected to the internet. Class A is a 31-bit binary number. Class B is a 30-bit binary number. Class C is a 29-bit binary number.

If no IP address can have every bit assigned to 1, nor every bit assigned to 0, how many possible IP addresses are there for computers connected to the internet?

Solution to Exercise 6.2

Class A counts $2^{31} - 2$.

Class B counts $2^{30} - 2$.

Class C counts $2^{29} - 2$.

We subtract 2 for the addresses containing only 1s and only 0s.

Therefore, the total number of addresses is:

\[ 2^{31} + 2^{30} + 2^{29} - 6 = 3,758,096,378 \]

Exercise 6.3

How many cards must you draw from a standard 52-card deck to guarantee that you will have $4$ cards of the same suit?

Solution to Exercise 6.3

There are 4 suits in a standard deck of cards. If we want to guarantee that we get 4 cards of the same suit, we must draw $13$ cards, since $\lceil 13 / 4\rceil = 4$.

Exercise 6.4

9 sports teams participate in a round robin, where every teams plays every other team, and ties are not allowed. Prove that if no team loses all of its games, then there must be at least two teams that end up with the same number of wins.

Solution to Exercise 6.4

Each teams plays 8 games. Every team has at least 1 win. So 9 teams are pigeons, the holes are the number of wins: $1, 2, 3, 4, 5, 6, 7, 8$. Therefore, by PHP, at least two teams have the same number of wins.

Exercise 6.5

Let $A$ be a set of $n+1$ integers. Prove that there must exist $x,y \in A$ with $x \neq y$ such that $n \mid x-y$

Solution to Exercise 6.5

There are $n+1$ integers in $A$. By Euclidean division with $n$, there are $n+1$ different remaidners. Thus, by PHP, at least two of them have the same remainder. Let those be $x$ and $y$. $x-y$ is divisible by $n$ since $x = q_1n + r$ and $y = q_2n + r$.

Exercise 6.6

The generalized pigeon hole principle can be stated using sets, functions, and the number of pre-images of a particular image.

Let $f: A \rightarrow B$ be a function where $|A| = N$ and $|B| = M$. Let $k$ be a positive integer. If $k < \frac{N}{M}$ then there is some $b \in B$ with at least $k+1$ distinct pre-images.

What is the contrapositive of this definition? Note that the contrapositive is equivalent.

Solution to Exercise 6.6

Let $f: A \rightarrow B$ be a function where $|A| = N$ and $|B| = M$ Let $k$ hbe a positive integer. If every $b \in B$ has at most $k$ pre-images, then $N \leq kM$.

Exercise 6.7

A class of 42 students is required to break into 12 groups of size no more than 6. Show that there are at least 5 groups of 3 or more students. (Hint: consider a proof by contradiction on the contrapositive from Exercise 6.6).

Solution to Exercise 6.7

Assume for contradiction that there are at most 4 groups of 3 or more students. Thus, there are $8$ groups of $2$ or fewer students. But, there are no more than $6$ students per group. Thus the 4 groups of 3 or more students have at most $24$ students in total. The $8$ groups of $2$ or fewer have at most $16$ students. Thus, that total number of students is at most $40$. A contradiction! Thus, there must be at least $5$ groups with 3 or more students.

This is actually the “contrapositive form” of pigeon-hole principle.

Counting

Contents

6.1. Counting#