Enumeration

Introduction

In this section we will consider problems involving counting the number of ways that we can choose a number of objects. These basically fall into two types: arrangement problems in which the order in which we make the choices is significant, and selection problems in which the order is not significant.

We have three basic rules in solving these problems.

The union rule: Let $A_1,A_2,\dots,A_k$ be finite, disjoint sets (i.e. finite sets such that, for $i\ne j$ , $A_i\cap A_j=\emptyset$ ). Then $|\bigcup_{i=1}^kA_i|=\sum_{i=1}^k|A_i|$ .

The product rule: Let $S$ be a set of ordered $k$ -tuples $(s_1,s_2,\dots,s_k)$ such that, for each $i=1,2,\dots,k$ and each possible choice of $s_1,s_2,\dots,s_{i-1}$ , there are $n_i$ possible choices for $s_i$ . Then $|S|=n_1n_2\cdots n_k$ .

The counting lemma: Let $A$ and $B$ be finite sets and let $\psi:A\to B$ be a function such that, for every $b\in B$ , $|\psi\inv(b)|=r$ . Then $|B|=|A|/r$ . (Here $\psi\inv(b)=\{\,a\in A:\psi(a)=b\,\}$ .)

Arrangement problems

We have $n$ different types of object and we want to put $r$ of them in a row. The ordering matters. We have an unlimited supply of each type of object. How many ways can we do this?

This is a straightforward use of the product rule. For example consider 4 consecutive throws of a 6-sided dice. The first throw gives us one out of six numbers, as does the second, third and fourth. Hence the number of possible results is $\displaystyle 6^4$ . In general, the number of arrangements of $r$ things from a set of $n$ things with replacement is

Given a set $X$ , an $r$ -permutation of $X$ is an arrangement of $r$ of the elements of $X$ in order, with no repetition of elements. We denote the number of $r$ -permutations of a set with $n$ elements by $P(n,r)$ . By the product rule, there are $n(n-1)(n-2)\cdots(n-r+1)$ $r$ -permutations of $X$ . So we have

In the case $r=n$ , we simply refer to a permutation of $X$ . The number of permutations of an $n$ -element set is $P(n,n)=n!$ .

In many cases, we do not want to consider all the permutations of $X$ as being distinct. For example, if we regard the two Gs in EGG as being identical, then there are only 3 ways to arrange the letters of the word EGG, rather than $3!=6$ .

Suppose that the elements of a set $X$ are partitioned into $k$ disjoint sets $X_1,X_2,\dots, X_k$ with $|X_i|=n_i$ .

• We wish to count the number of types of arrangement of the elements of $X$ , in which two arrangements are deemed to be of the same type if the corresponding terms come from the same set $X_i$ .

• We let $A$ denote the set of arrangements of the elements of $X$ , and $B$ the set of types of arrangement.

• If $\psi:A\to B$ is the function which takes a given arrangement to its type, then, for every $b\in B$ , $|\psi\inv(b)|=n_1!n_2!\cdots n_k!$ .

• So by the counting lemma we have

Example 6.8 Three jars of rhubarb jam and three jars of manuka honey are to be put in a row on a shelf. In how many different orders can they be placed so that there is a jar of jam at each end of the shelf?

Selections

We now consider counting problems in which the order we make our choices does not matter. In other words, instead of choosing an ordered $r$ -tuple of elements of a set $X$ , we are going to choose an $r$ -element subset of $X$ . We denote the number of $r$ -element subsets of an $n$ -element set by $C(n,r)$ , or $\binom nr$ .

To calculate $\binom nr$ , let $X$ be an $n$ -element set, let $A$ be the set of $r$ -permutations of $X$ and let $B$ be the set of $r$ -element subsets of $X$ . Define $\psi:A\to B$ by

Then, for any $Y\in B$ , $\psi\inv(Y)$ is the set of permutations of $Y$ , which has cardinality $P(r,r)=r!$ . So, by the counting lemma, we have

The numbers $\binom nr$ are called binomial coefficients. Some of their properties are given in section 6.5.

(a) How many (unordered) five-card poker hands, selected from an ordinary 52-card deck, are there?

(b) How many poker hands contain cards all of the same suit?

(c) How many poker hands contain three cards of one denomination and two cards of a second denomination?

(a) one suit?

(b) two suits?

(c) three suits?

(d) four suits?

Solution.

(a) ${4\choose1} {10 \choose4} = 840$ .

(b) ${4\choose 2} \left[ {10 \choose3}{10 \choose1} + {10 \choose2}{10 \choose2} + {10 \choose1}{10 \choose3} \right] = 26,550$ .

(c) ${4\choose 3} \left[ {10 \choose2}{10 \choose1}{10 \choose1} + {10 \choose1}{10 \choose2}{10 \choose1} + {10 \choose1}{10 \choose1}{10 \choose2} \right] = 54,000$ .

(d) ${4\choose 4} {10 \choose1}{10 \choose1}{10 \choose1}{10 \choose1} = 10,000$ .

(a) $9$ people?

(b) $5$ men and $4$ women?

(a) $9$ men or $9$ women?

Solution.

(a) ${29 \choose 9} = 10,015,005$ .

(b) ${16 \choose 5} \times {13 \choose 4} = 3,123,120$ .

(c) ${16 \choose 9} + {13 \choose 9} = 11,440 + 715 = 12,155$ .

(a) $4000 is to be invested in each stock?

(b) $6000 is to be invested in one stock, $5000 in another, $3000 in the third, and $2000 in the fourth?

Selections with repetitions allowed

Suppose we have a bag containing a large number of marbles in each of three colors: brown, yellow and blue. In how many ways can we select 5 marbles from the bag? In this case we are selecting 5 objects from 3 types, with order unimportant and with repetition allowed.

To answer this question, we will exhibit a 1-1 correspondence between the set of solutions and the set of sequences of 5 0s and 2 1s. The correspondence is as follows: a selection of $i$ brown marbles, $j$ blue marbles and $p$ yellow marbles corresponds to the sequence of $i$ 0s followed by a 1 followed by $j$ 0s followed by a 1 followed by $p$ 0s. For example, the selection “1 brown, 0 blue, 4 yellow” corresponds to the sequence 0110000.

So now we just need to work out how many sequences of 5 0s and 2 1s there are. Well, there are 7 symbols, and we must select the 2 places to put the 1s. So the answer is $\binom72$ .

In general, the number of ways of selecting $n$ objects from $k$ types, with order unimportant but with repetition allowed, is

= number of ways of selecting $n$ objects of $k$ different types

= number of ways of placing $n$ indistinguishable objects into $k$ bijections

= number of ways of arranging $n$ objects and $k-1$ dividers

In Section 6.5 we learn that

$\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$ .

If $k$ is greater than $n$ then it is easier to calculate the expression to the right.

1. 16 muffins?

2. 16 muffins with at least one of each kind?

3. 16 muffins with at least two peach and at least three chocolate?

4. 16 muffins with no more than two broccoli?

5. 16 muffins with at least two cheese, at least three chocolate and no more than two broccoli muffins?

(a) How many different assortments of one dozen donuts can be purchased?

(b) How many different assortments of one dozen donuts can be purchased that include at least one donut of each type?

(c) How many different assortments of one dozen donuts can be purchased that include no more than three chocolate donuts?

1. Any distribution is allowed.

2. No more than 80% of the students may pass.

3. No fewer than 50% of the students may pass.

4. No more than 20% of the students may get A grades.

5. Conditions 2, 3 and 4 apply.

(a) In how many ways can the money be distributed among the $3$ strangers?

(b) In how many ways can the money be distributed among the $3$ strangers if each stranger gets at least $100?

Solution.

(a) ${{7+3 -1} \choose {3-1}} = 36$ .

(b) ${{4+3 -1} \choose {3-1}} = 15$ . _First give $100 to each stranger and then share out the remaining $400.

Some properties of binomial coefficients

We now describe some of the facts about the binomial coefficients $\binom nk$ . First, the reason for the name.

Fact 1: for any real numbers $a$ and $b$ , and any $n\in\N$ ,

This is the binomial theorem. We will prove this later, using induction and Fact 3 (below).

Fact 2: For any $n\in\N$ and $k\in\{0,1,\dots,n\}$ ,

This is because the number of ways of selecting $k$ objects is the same as the number of ways of selecting which $n-k$ objects to omit.

Fact 3 (Pascal’s Identity): For any $n\in\N$ and $k\in\{0,1,\dots,n\}$ ,

This is because we can choose $k+1$ of the $n+1$ objects either by choosing $k+1$ of the first $n$ objects or by choosing $k$ of the first $n$ objects together with the $(n+1)^{\text{th}}$ object.

The inclusion/exclusion principle

We know that if $A$ and $B$ are disjoint sets then $|A\cup B|=|A|+|B|$ . What if $A$ and $B$ are not disjoint? In counting $|A|+|B|$ , we have counted the elements of $A\cap B$ twice, so if we subtract $|A\cap B|$ , we will get the right number. In other words,

What about three sets $A$ , $B$ and $C$ ? As before, in counting $|A|+|B|+|C|$ the elements of $A\cap B$ , $A\cap C$ , and $B\cap C$ will be counted more than once. If we subtract $\bigl(|A\cap B|+|A\cap C|+|B\cap C|\bigr)$ , we will have dealt properly with elements which are in two of the sets. However, elements of $A\cap B\cap C$ will have been added three times and subtracted three times, so we must add them in again to get

In general, let $A_1, A_2,\dots,A_n$ be sets. Let $I=\{1,2,\dots,n\}$ . For $1\le k\le n$ , let $\mathcal P_k=\{\,J\subseteq I:|J|=k\,\}$ . Then

This result is known as the inclusion/exclusion principle.

To prove this result, consider the contribution of a typical element $x$ of $\bigcup_{i=1}^n A_i$ to the right hand side of the equation. Suppose that $x$ is in $m$ of the sets, namely $A_{i_1},A_{i_2},\dots,A_{i_m}$ . First, fix some $k$ with $1\le k\le n$ . The contribution of $x$ to $\sum_{J\in\mathcal P_k}\left|\bigcap_{i\in J}A_i\right|$ is the number of sets in $\mathcal P_k$ which are subsets of $\{i_1,i_2,\dots,i_m\}$ , in other words the number of $k$ -element subsets of an $m$ -element set, which is $\binom mk$ . In particular, $x$ contributes nothing if $k>m$ . So the total contribution of $x$ to the right hand side of ($*$ ) is

Solution. For each $n\in\mathbb{P} = \Z_{\ge 1}$ , let $M_n$ denote the set of numbers between 1 and 1000 which are divisible by $n$ . Then $|M_n|=\left\lfloor\frac{1000}n\right\rfloor$ . Notice that $M_m\cap M_n=M_l$ , where $l$ is the least common multiple of $m$ and $n$ . By the inclusion/exclusion principle, we have

The pigeonhole principle

In its simplest form, the pigeonhole principle states that if $m$ objects (maybe letters or pigeons) are placed into $n$ boxes (called “pigeonholes”), and $m>n$ , then one pigeonhole must receive at least two objects.

In general, if the number of objects is more than $k$ times the number of pigeonholes, then some pigeonhole must contain at least $k+1$ objects.

In general, if the elements of a set with $N$ elements are partitioned into $k$ subsets, then one of the subsets must contain at least $\left\lceil\frac Nk\right\rceil$ elements.\ (Note $\left\lceil\:\:\right\rceil$ is the ceiling function. $\left\lceil x\right\rceil$ means take the smallest integer which is greater than or equal to $x$ . For example $\left\lceil 9.1\right\rceil=10$ .)

Proof: Suppose $A$ is a set with $|A|=N$ , and $A$ is partitioned into subsets $A_1,A_2,\dots,A_k$ . In other words, $A_1,A_2,\dots,A_k$ are disjoint sets whose union is the whole of $A$ . Let $x=\frac Nk$ . Suppose that $|A_i|<x$ for each $i$ . Then

This contradiction shows that there must be at least one $i$ such that $|A_i|\ge x$ . But then, since $|A_i|$ is an integer, we must have $|A_i|\ge\lceil x\rceil$ , ie $|A_i|\ge\left\lceil\frac Nk\right\rceil$ , as required.

Solution. Let $p=$ ‘the number of sets of identical objects’.

There are now two possibilities, either $p \leq n$ or $p > n$ .

(i) Suppose that $p\leq n$ , then $\frac{n^2+1}{p} > n$ , therefore some set of identical objects contains at least $n+1$ objects. That is, at least $n+1$ objects are identical.

(ii) Suppose that $p > n$ , then there are at least $n+1$ sets of identical objects. That is, at least $n+1$ objects are all different.

Hence, among a collection of $n^2 +1$ objects, there are either $n+1$ which are identical or $n+1$ which are all different.

Trickier pigeonhole applications

We now give some examples which show how the pigeonhole principle can be used to solve non-trivial problems.