A bank card has a four-digit code, each digit from \(0\) to \(9\) . How many of the possible codes contain a repeated digit? Most people guess that such codes are a small minority. One way to find out is to sort the codes with a repeat into types, those with one pair, two pairs, three of a kind, and so on, and count each type; this works, but it is easy to miss a type or to count a code under two headings. Another way is to count the codes with no repeat, which is much simpler, and subtract. The answer turns out to be \(4960\) of the \(10000\) codes, very nearly half.
The example shows what counting is. It is not arithmetic; the arithmetic is trivial. It is the art of describing a set so that its size becomes evident, and of being sure that the description produces every element exactly once. The rigorous form of “describing a set so that its size is evident” is a bijection with a set whose size is known. This chapter builds a small collection of counting principles from that idea, each with a proof, and then turns to the two standard ways a count goes wrong: counting something twice, and not counting it at all.
5.1 The basic principles
Recall from Definition 2.10 that a set \(A\) has \(n\) elements, written \(\lvert A\rvert=n\) , when there is a bijection from \([n]\) to \(A\) . It is convenient to let \([0]\) denote the empty set, so that the empty set, with \(0\) elements, is covered by the same wording. The counting rules of this chapter are deduced from that definition. Before it can be used, one point must be settled that the notation \(\lvert A\rvert\) takes for granted: a set cannot have \(m\) elements and also \(n\) elements for two different numbers \(m\) and \(n\) . That is the first part of the first theorem, and the later parts depend on it.
Theorem 5.1 (size, bijection, sum, product, and complement rules). Let \(m,n\in\mathbb N\) , and let \(A\) and \(B\) be finite sets.
(a) If there is an injective function from \([m]\) to \([n]\) , then \(m\le n\) . Consequently the number of elements of a finite set is well defined: if there are bijections from \([m]\) to \(A\) and from \([n]\) to \(A\) , then \(m=n\) .
(b) If there is a bijection from \(A\) to \(B\) , then \(\lvert A\rvert=\lvert B\rvert\) .
(c) If \(A\) and \(B\) are disjoint, then \(\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert\) .
(d) \(\lvert A\times B\rvert=\lvert A\rvert\cdot\lvert B\rvert\) .
(e) If \(A\subseteq U\) and \(U\) is finite, then \(\lvert U\setminus A\rvert=\lvert U\rvert-\lvert A\rvert\) .
Proof. (a) Let \(P(m)\) be the statement: for every \(n\in\mathbb N\) , if there is an injective function from \([m]\) to \([n]\) , then \(m\le n\) . We prove \(P(m)\) by induction on \(m\) . \(P(0)\) holds because \(0\le n\) for every \(n\) . Let \(m\ge 0\) , assume \(P(m)\) , and let \(f:[m+1]\to[n]\) be injective. Put \(c=f(m+1)\) ; since \(c\in[n]\) , we have \(n\ge 1\) . For \(i\in[m]\) the value \(f(i)\) is different from \(c\) , because \(f\) is injective. Define \(g:[m]\to[n-1]\) by \(g(i)=f(i)\) if \(f(i)<c\) and \(g(i)=f(i)-1\) if \(f(i)>c\) . Its values do lie in \([n-1]\) . It is injective: if \(f(i)\) and \(f(j)\) are on the same side of \(c\) and \(g(i)=g(j)\) , then \(f(i)=f(j)\) and so \(i=j\) ; and if \(f(i)<c<f(j)\) , then \(g(i)<c\le g(j)\) , so \(g(i)\ne g(j)\) . By \(P(m)\) applied to \(g\) , \(m\le n-1\) , that is, \(m+1\le n\) . This is \(P(m+1)\) .
Now let \(g:[m]\to A\) and \(h:[n]\to A\) be bijections. Then \(h^{-1}\circ g\) is a bijection from \([m]\) to \([n]\) by Theorems 2.8 and 2.9, and its inverse is a bijection from \([n]\) to \([m]\) . Both are injective, so \(m\le n\) and \(n\le m\) .
(b) If \(g:[n]\to A\) and \(f:A\to B\) are bijections, then \(f\circ g:[n]\to B\) is a bijection by Theorem 2.8.
(c) If either set is empty the claim is immediate. Otherwise let \(g:[m]\to A\) and \(h:[n]\to B\) be bijections. Define \(k:[m+n]\to A\cup B\) by \(k(i)=g(i)\) for \(i\le m\) and \(k(i)=h(i-m)\) for \(i>m\) . It is surjective because \(g\) and \(h\) are, and injective because \(g\) and \(h\) are and because a value of \(g\) is never a value of \(h\) , the sets being disjoint.
(d) By induction on \(m=\lvert A\rvert\) . If \(m=0\) the product is empty. If \(A\) has \(m+1\) elements, choose \(a\in A\) ; then \(A\times B\) is the disjoint union of \((A\setminus\{a\})\times B\) , which has \(m\lvert B\rvert\) elements by the induction hypothesis, and \(\{a\}\times B\) , which has \(\lvert B\rvert\) elements because \(b\mapsto(a,b)\) is a bijection. By (c) the total is \((m+1)\lvert B\rvert\) .
(e) \(U\) is the disjoint union of \(A\) and \(U\setminus A\) ; apply (c). This uses the fact that a subset of a finite set is finite, which is proved by a routine induction on the number of elements of the larger set and which we use without further comment.
Part (a) is the pigeonhole principle in its barest form, proved here directly by induction so that nothing later is circular: Theorem 5.11 and Corollary 5.12 rest on the sum rule and on sizes being well defined, and both are now in hand.
Parts (c) and (d) extend by induction to any finite number of sets, and (d) is most often used in a slightly more general form.
Theorem 5.2 (product rule for successive choices). Suppose every object of a set \(S\) is determined by a sequence of \(k\) choices, in such a way that different sequences of choices give different objects, and suppose that the \(i\) -th choice can be made in exactly \(n_i\) ways whatever the earlier choices were. Then \(\lvert S\rvert=n_1n_2\cdots n_k\) .
Proof. By induction on \(k\) . For \(k=1\) the claim is the definition of \(n_1\) . For the step, sort the objects according to their first choice. There are \(n_1\) classes, they are disjoint, and by the induction hypothesis each has \(n_2\cdots n_k\) elements. By the sum rule the total is \(n_1\cdot n_2\cdots n_k\) .
The rule has two hypotheses, and each is a place where counts go wrong. The number of options at each stage must not depend on the earlier choices, although the set of options may. And the choices must be recoverable from the object: if two different sequences of choices can produce the same object, the product overcounts.
Corollary 5.3 (three standard counts). Let \(A\) be a set with \(k\) elements and \(B\) a set with \(n\) elements. The number of functions from \(A\) to \(B\) is \(n^{k}\) . The number of injective functions from \(A\) to \(B\) is \(n(n-1)(n-2)\cdots(n-k+1)\) , which is \(0\) if \(k>n\) . The number of subsets of \(B\) is \(2^{n}\) .
Proof. List the elements of \(A\) as \(a_1,\dots,a_k\) . A function is determined by choosing \(f(a_1)\) , then \(f(a_2)\) , and so on, each in \(n\) ways. For an injective function the value \(f(a_i)\) must avoid the \(i-1\) values already used, leaving \(n-i+1\) options whatever those values were. For subsets, list the elements of \(B\) as \(b_1,\dots,b_n\) ; a subset is determined by deciding, for each \(b_i\) in turn, whether it is included, a choice between \(2\) options. Equivalently, subsets of \(B\) correspond bijectively to strings of \(n\) bits.
Example 5.1: Codes with a repeated digit
A code is a function from the four positions to the ten digits, so there are \(10^{4}=10000\) codes. A code with no repeated digit is an injective function, and there are \(10\cdot 9\cdot 8\cdot 7=5040\) of those. By the complement rule the number of codes with at least one repeated digit is
Counting the complement was natural here because “at least one repeat” is a disjunction of many overlapping conditions, while its negation, “all digits different”, is a single clean condition. Whenever a count involves the words “at least one”, consider counting the opposite.
Example 5.2: When the order of the choices matters
How many three-digit integers, from \(100\) to \(999\) , are even and have three different digits?
Try choosing the digits from left to right. The first digit can be chosen in \(9\) ways, since it is not \(0\) , and the second in \(9\) ways, since it differs from the first. The third must be even and different from both, and the number of options now depends on how many even digits have been used already. The product rule does not apply.
Choose in a different order: the last digit first. Even then one case distinction is needed, because the first digit must avoid \(0\) . If the last digit is \(0\) , the first digit can be chosen in \(9\) ways and the middle digit in \(8\) , giving \(9\cdot 8=72\) numbers. If the last digit is \(2\) , \(4\) , \(6\) , or \(8\) , which is \(4\) ways, the first digit must avoid \(0\) and the last digit, which is \(8\) ways, and the middle digit must avoid the two digits used, which is \(8\) ways, giving \(4\cdot 8\cdot 8=256\) numbers. The two cases are disjoint, so the answer is \(72+256=328\) .
The most constrained choice should be made first, and where the number of options still varies, the sum rule splits the count into cases within each of which the product rule holds.
One more rule converts a count of labelled or ordered objects into a count of unlabelled or unordered ones.
Theorem 5.4 (division rule). Let \(f:A\to B\) be a function between finite sets such that every element of \(B\) has exactly \(k\) preimages. Then \(\lvert B\rvert=\lvert A\rvert/k\) .
Proof. The preimages \(f^{-1}(\{b\})\) , for \(b\in B\) , are disjoint, and their union is \(A\) , since every element of \(A\) is mapped to some \(b\) . Each has \(k\) elements, so by the sum rule \(\lvert A\rvert=k\lvert B\rvert\) .
5.2 Permutations and combinations
Definition 5.5 (permutation, binomial coefficient). A permutation of a finite set \(A\) is an arrangement of all its elements in a row, that is, a bijection from \([n]\) to \(A\) where \(n=\lvert A\rvert\) . A \(k\) -permutation of \(A\) is an arrangement of \(k\) different elements of \(A\) in a row. For integers \(0\le k\le n\) , the binomial coefficient \(\binom nk\) , read “\(n\) choose \(k\) ”, is the number of \(k\) -element subsets of an \(n\) -element set.
Theorem 5.6 (counting arrangements and selections). Let \(0\le k\le n\) . An \(n\) -element set has \(n!\) permutations and \(\frac{n!}{(n-k)!}\) \(k\) -permutations, and
Proof. A \(k\) -permutation is an injective function from \([k]\) to the set, so by Corollary 5.3 there are \(n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}\) of them; the case \(k=n\) gives \(n!\) permutations. Now consider the function that sends each \(k\) -permutation to the set of its entries, a \(k\) -element subset. Every \(k\) -element subset is the image of exactly \(k!\) different \(k\) -permutations, namely its own \(k!\) arrangements. By the division rule the number of \(k\) -element subsets is \(\frac{n!}{(n-k)!}\) divided by \(k!\) .
By convention \(0!=1\) , so \(\binom n0=\binom nn=1\) : there is one empty subset and one full one. The two kinds of count answer different questions. A \(k\) -permutation is an ordered selection without repetition, and a \(k\) -subset is an unordered one. The first question to ask of a counting problem is whether rearranging a selection gives a different object.
Example 5.3: Committees under a constraint
A committee of \(5\) is to be chosen from \(12\) people. Order within a committee is irrelevant, so with no restriction there are \(\binom{12}{5}=792\) committees.
Suppose two of the people, Ana and Ben, refuse to serve together. Count the forbidden committees: those containing both. Such a committee is completed by choosing \(3\) of the other \(10\) people, in \(\binom{10}{3}=120\) ways. By the complement rule there are \(792-120=672\) acceptable committees.
A second method confirms this. Sort the acceptable committees by which of the two they contain. Neither: \(\binom{10}{5}=252\) . Exactly one: \(2\) ways to say which, then \(\binom{10}{4}=210\) ways to complete, giving \(420\) . The cases are disjoint, and \(252+420=672\) .
Now suppose each committee also names one of its members as chair. Choosing the committee and then the chair gives \(792\cdot 5=3960\) . Choosing the chair first, from all \(12\) people, and then the other \(4\) members from the remaining \(11\) gives \(12\cdot\binom{11}{4}=12\cdot 330=3960\) . Two correct counts of the same set must agree, and that simple remark is a method of proof, as the next section shows.
Example 5.4: Arrangements of a word with repeated letters
How many different strings can be made by rearranging the letters of BANANA? There are six letters, but \(6!=720\) is too large, because swapping two of the A’s does not change the string.
Make the letters distinguishable by attaching labels: three A’s with labels \(1,2,3\) , two N’s with labels \(1,2\) , and one B. The labelled letters have \(720\) arrangements. Erasing the labels is a function from labelled arrangements to strings, and each string is the image of exactly \(3!\cdot 2!=12\) labelled arrangements, obtained by permuting the labels among the A’s and among the N’s. By the division rule the number of strings is
The same reasoning gives \(\frac{11!}{4!\,4!\,2!}=34650\) arrangements of the letters of MISSISSIPPI, which has four I’s, four S’s, two P’s, and one M.
5.3 Binomial coefficients and combinatorial proof
A combinatorial proof of an identity shows that both sides count the same set, or exhibits a bijection between a set counted by one side and a set counted by the other. Such a proof explains the identity as well as verifying it.
Theorem 5.7 (properties of binomial coefficients). For integers \(n\ge 1\) and \(0\le k\le n\) :
(a) \(\binom nk=\binom n{n-k}\) ;
(b) (Pascal’s rule) \(\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}\) when \(1\le k\le n-1\) ;
(c) \(\sum_{j=0}^{n}\binom nj=2^{n}\) ;
(d) \(k\binom nk=n\binom{n-1}{k-1}\) when \(k\ge 1\) .
Proof. (a) Taking complements is a bijection from the \(k\) -element subsets of \([n]\) to the \((n-k)\) -element subsets; it is its own inverse.
(b) Sort the \(k\) -element subsets of \([n]\) by whether they contain the element \(n\) . Those that do not are the \(k\) -element subsets of \([n-1]\) , of which there are \(\binom{n-1}{k}\) . Those that do correspond, by removing \(n\) , to the \((k-1)\) -element subsets of \([n-1]\) , of which there are \(\binom{n-1}{k-1}\) . The two kinds are disjoint and exhaust the possibilities.
(c) Both sides count all subsets of \([n]\) : the right side by Corollary 5.3, the left side by sorting the subsets according to their size.
(d) Both sides count the pairs consisting of a \(k\) -element subset of \([n]\) and one distinguished element of it. Choosing the subset and then the element gives \(\binom nk\cdot k\) . Choosing the distinguished element first, in \(n\) ways, and then the other \(k-1\) elements from the remaining \(n-1\) gives \(n\binom{n-1}{k-1}\) .
Pascal’s rule builds the binomial coefficients row by row with additions only, in the triangular array that bears Pascal’s name. The coefficients take their name from the following theorem.
Theorem 5.8 (binomial theorem). For all real numbers \(x\) , \(y\) and every \(n\in\mathbb N\) ,
Proof. Write \((x+y)^{n}\) as a product of \(n\) factors \((x+y)\) . Expanding the product by the distributive law gives a sum of \(2^{n}\) terms, one for each way of selecting \(x\) or \(y\) from each factor. A term in which \(x\) was selected from exactly \(k\) of the factors equals \(x^{k}y^{n-k}\) , and the number of such terms is the number of ways to say which \(k\) of the \(n\) factors contributed \(x\) , which is \(\binom nk\) . Collecting equal terms gives the formula.
Setting \(x=y=1\) recovers Theorem 5.7(c). Setting \(x=-1\) and \(y=1\) gives, for \(n\ge 1\) ,
which says that a nonempty finite set has as many subsets of even size as of odd size. That alternating sum is the engine of inclusion and exclusion in Section 5.5.
Example 5.5: Paths on a grid
A path starts at the point \((0,0)\) of the integer grid and moves in unit steps, each step either right (R) or up (U). How many such paths end at \((4,3)\) ?
A path to \((4,3)\) makes exactly \(7\) steps, of which \(4\) are R and \(3\) are U, in some order. Conversely every string of \(7\) letters with exactly three U’s describes one such path. The correspondence between paths and strings is a bijection, and a string is determined by the set of positions of its U’s, a \(3\) -element subset of \(7\) positions. So there are \(\binom 73=35\) paths.
Figure 5.1 counts the same paths another way. A path reaching \((i,j)\) arrived by its last step either from \((i-1,j)\) or from \((i,j-1)\) , and these cases are disjoint, so the number of paths to a point is the sum of the numbers for those two neighbours. Starting from \(1\) along the two edges and adding, the label at \((4,3)\) comes out as \(35\) . The addition rule is Pascal’s rule read on the grid, since the number of paths to \((i,j)\) is \(\binom{i+j}{j}\) .
Restricted counts follow from the product rule. A path to \((4,3)\) that passes through \((2,2)\) consists of a path from \((0,0)\) to \((2,2)\) followed by a path from \((2,2)\) to \((4,3)\) , and the second part is a path with two R steps and one U step. So there are \(\binom 42\cdot\binom 31=6\cdot 3=18\) paths through \((2,2)\) , and \(35-18=17\) that avoid it.
Example 5.6: An identity proved by counting a committee twice
Claim (Vandermonde’s identity). For natural numbers \(m\) , \(n\) , \(r\) with \(r\le m\) and \(r\le n\) ,
Proof. Consider a group of \(m\) women and \(n\) men, and count the committees of \(r\) people. The right side counts them directly, as \(r\) -element subsets of a set of \(m+n\) people. For the left side, sort the committees by the number \(k\) of women they contain. A committee with exactly \(k\) women is made by choosing the women in \(\binom mk\) ways and then the \(r-k\) men in \(\binom n{r-k}\) ways; by the product rule there are \(\binom mk\binom n{r-k}\) of these. The classes for different \(k\) are disjoint, and every committee falls in one, so by the sum rule the total is the left side.
For \(m=5\) , \(n=4\) , \(r=3\) the identity reads \(4+30+40+10=84\) , and \(\binom 93=84\) . Taking \(m=n=r\) and using the symmetry \(\binom n{n-k}=\binom nk\) gives \(\sum_k\binom nk^{2}=\binom{2n}{n}\) ; for \(n=4\) this is \(1+16+36+16+1=70\) .
No algebra was needed, and none would have been as short. The pattern, “sort the objects by some feature, count each class, add”, is how nearly all summation identities for binomial coefficients are proved.
5.4 Selections with repetition
Suppose \(10\) identical sweets are to be shared among \(4\) children. A distribution is described by four natural numbers adding up to \(10\) . The sweets are indistinguishable, so only the numbers matter. How many distributions are there?
Theorem 5.9 (stars and bars). Let \(n\ge 0\) and \(k\ge 1\) be integers. The number of solutions of
in natural numbers \(x_1,\dots,x_k\) is \(\binom{n+k-1}{k-1}\) . The number of solutions in positive integers is \(\binom{n-1}{k-1}\) when \(n\ge k\) .
Proof. Encode a solution as a string of \(n\) stars and \(k-1\) bars: \(x_1\) stars, a bar, \(x_2\) stars, a bar, and so on, ending with \(x_k\) stars. Conversely, any string of \(n\) stars and \(k-1\) bars decodes to a solution: \(x_1\) is the number of stars before the first bar, \(x_i\) the number between bar \(i-1\) and bar \(i\) , and \(x_k\) the number after the last bar. Encoding and decoding are inverse to each other, so solutions correspond bijectively to such strings. A string has \(n+k-1\) symbols and is determined by the positions of its \(k-1\) bars, so there are \(\binom{n+k-1}{k-1}\) strings.
For positive solutions, substitute \(x_i=y_i+1\) . Then \(x_1+\dots+x_k=n\) with all \(x_i\ge 1\) becomes \(y_1+\dots+y_k=n-k\) with all \(y_i\ge 0\) , and the substitution is a bijection between the two sets of solutions. By the first part there are \(\binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}\) of them.
A solution of the equation is also a way of choosing \(n\) objects from \(k\) types when repetition is allowed and order is irrelevant: \(x_i\) is the number chosen of type \(i\) . So the theorem counts unordered selections with repetition.
Example 5.7: Sharing ten sweets
With \(n=10\) and \(k=4\) , the number of ways to share \(10\) identical sweets among \(4\) children is \(\binom{13}{3}=286\) . For example the string of stars and bars with \(3\) stars, a bar, no stars, a bar, \(5\) stars, a bar, and \(2\) stars encodes the distribution \((3,0,5,2)\) .
If every child must receive at least one sweet, the count is \(\binom 93=84\) .
If instead the first child may receive at most \(3\) sweets, with no other restriction, count the complement: distributions with \(x_1\ge 4\) . Substituting \(x_1=y_1+4\) turns these into the solutions of \(y_1+x_2+x_3+x_4=6\) in natural numbers, of which there are \(\binom 93=84\) . So \(286-84=202\) distributions give the first child at most \(3\) .
Lower bounds on the variables are absorbed by a substitution; upper bounds are handled by the complement rule, and when several upper bounds are present, by inclusion and exclusion.
The four basic selection counts can now be set side by side.
Example 5.8: One question with four answers
“In how many ways can \(3\) scoops be chosen from \(4\) flavours?” The question is incomplete until two things are settled: whether the order of the scoops matters, and whether a flavour may be repeated.
| Repetition allowed | Repetition not allowed | |
|---|---|---|
| Order matters | \(4^{3}=64\) | \(4\cdot 3\cdot 2=24\) |
| Order does not matter | \(\binom{6}{3}=20\) | \(\binom{4}{3}=4\) |
The top row counts functions and injective functions from the \(3\) positions to the \(4\) flavours. The bottom right counts \(3\) -element subsets. The bottom left counts solutions of \(x_1+x_2+x_3+x_4=3\) in natural numbers, which by Theorem 5.9 number \(\binom{3+4-1}{4-1}=\binom 63=20\) . In general, for \(k\) selections from \(n\) types the four entries are \(n^{k}\) , \(\frac{n!}{(n-k)!}\) , \(\binom{n+k-1}{k}\) , and \(\binom nk\) .
The division rule connects the right-hand column, \(24/3!=4\) , because every unordered selection without repetition has exactly \(3!\) orderings. It does not connect the left-hand column: \(64/6\) is not even an integer. A selection with repetition such as vanilla, vanilla, mint has only \(3\) different orderings, not \(6\) , so the map from ordered to unordered selections is not \(k\) -to-one for any single \(k\) . The hypothesis of Theorem 5.4 is not a formality.
5.5 Inclusion and exclusion
The sum rule requires disjoint sets. When sets overlap, adding their sizes counts the overlap twice, and the correction has a systematic form.
Theorem 5.10 (inclusion and exclusion). For finite sets \(A\) , \(B\) , \(C\) :
In general, for finite sets \(A_1,\dots,A_n\) , the size of \(A_1\cup\dots\cup A_n\) is the sum, over all nonempty sets \(S\subseteq[n]\) of indices, of \((-1)^{\lvert S\rvert+1}\) times the size of the intersection of the sets \(A_i\) with \(i\in S\) .
Proof. We show that every element \(x\) of the union contributes exactly \(1\) to the alternating sum. Suppose \(x\) belongs to exactly \(m\) of the sets, where \(m\ge 1\) . Then \(x\) lies in the intersection indexed by \(S\) exactly when \(S\) is a subset of the \(m\) indices of sets containing \(x\) . For each \(j\) from \(1\) to \(m\) there are \(\binom mj\) such sets \(S\) of size \(j\) , each contributing \((-1)^{j+1}\) . So the total contribution of \(x\) is
by the alternating-sum consequence of the binomial theorem. An element outside the union belongs to none of the intersections and contributes \(0\) . Hence the alternating sum equals the number of elements of the union.
The usual application counts the elements of a universe that have none of several properties: take \(A_i\) to be the set of elements with property \(i\) , compute the size of the union, and subtract from the size of the universe.
Example 5.9: Divisibility, and the units modulo a product of two primes
How many integers from \(1\) to \(1000\) are divisible by at least one of \(2\) , \(3\) , \(5\) ?
Let \(A\) , \(B\) , \(C\) be the sets of multiples of \(2\) , \(3\) , \(5\) in that range. The number of multiples of \(d\) from \(1\) to \(1000\) is the quotient \(\lfloor 1000/d\rfloor\) , so \(\lvert A\rvert=500\) , \(\lvert B\rvert=333\) , \(\lvert C\rvert=200\) . An integer is in \(A\cap B\) exactly when it is divisible by both \(2\) and \(3\) , which by Theorem 4.7(b) means divisible by \(6\) ; so \(\lvert A\cap B\rvert=166\) , and similarly \(\lvert A\cap C\rvert=100\) and \(\lvert B\cap C\rvert=66\) from the multiples of \(10\) and \(15\) . Finally \(\lvert A\cap B\cap C\rvert=33\) from the multiples of \(30\) . Therefore
and \(1000-734=266\) integers in the range are divisible by none of the three.
The same method answers the question that closed Chapter 4. Let \(n=pq\) with \(p\) and \(q\) distinct primes. An integer from \(1\) to \(n\) fails to be coprime to \(n\) exactly when it is divisible by \(p\) or by \(q\) . There are \(q\) multiples of \(p\) , \(p\) multiples of \(q\) , and one multiple of both, namely \(n\) . So \(q+p-1\) integers are not coprime to \(n\) , and the number of units modulo \(n\) is
For \(n=143=11\cdot 13\) this is \(143-13-11+1=120\) , the modulus that governed the exponents in Example 4.10.
Example 5.10: Surjections and derangements
Surjections. How many functions from a \(5\) -element set to \(\{1,2,3\}\) are surjective? There are \(3^{5}=243\) functions in all. Let \(A_i\) be the set of functions that miss the value \(i\) . A function misses a given value exactly when it maps into the other two, so \(\lvert A_i\rvert=2^{5}=32\) ; it misses two given values when it is constant at the third, so each pairwise intersection has \(1\) element; and no function misses all three. By inclusion and exclusion the number of non-surjective functions is \(3\cdot 32-3\cdot 1+0=93\) , and the number of surjections is \(243-93=150\) .
Derangements. A derangement is a permutation with no fixed point: no element stays in its own position. How many of the \(4!=24\) permutations of \(\{1,2,3,4\}\) are derangements? Let \(A_i\) be the set of permutations that fix \(i\) . Fixing \(j\) specified elements leaves the other \(4-j\) to be permuted freely, so an intersection of \(j\) of the sets has \((4-j)!\) elements, and there are \(\binom 4j\) such intersections. The number of permutations with at least one fixed point is
so there are \(24-15=9\) derangements. If four people each put a hat in a pile and take one back at random, in \(9\) of the \(24\) possible outcomes nobody gets their own.
5.6 The pigeonhole principle
The last principle counts nothing exactly. It asserts that when there are more objects than places to put them, some place receives more than one.
Theorem 5.11 (pigeonhole principle). Let \(f:A\to B\) be a function between finite sets, and let \(k\) be a positive integer. If \(\lvert A\rvert>k\lvert B\rvert\) , then some element of \(B\) has at least \(k+1\) preimages. In particular, if \(\lvert A\rvert>\lvert B\rvert\) then \(f\) is not injective.
Proof. We prove the contrapositive. Suppose every element of \(B\) has at most \(k\) preimages. The preimages \(f^{-1}(\{b\})\) are disjoint and their union is \(A\) , so by the sum rule \(\lvert A\rvert\) is a sum of \(\lvert B\rvert\) numbers each at most \(k\) , and \(\lvert A\rvert\le k\lvert B\rvert\) .
Corollary 5.12 (maps between sets of equal size). Let \(A\) and \(B\) be finite sets with \(\lvert A\rvert=\lvert B\rvert\) . A function \(f:A\to B\) is injective if and only if it is surjective.
Proof. Let \(n=\lvert A\rvert=\lvert B\rvert\) . If \(f\) is injective, its range has \(n\) elements, since \(f\) is a bijection from \(A\) to its range, and a subset of \(B\) with \(n\) elements is all of \(B\) by the complement rule. If \(f\) is surjective, every element of \(B\) has at least one preimage. The \(n\) preimage sets \(f^{-1}(\{b\})\) are disjoint with union \(A\) , so their sizes are \(n\) positive integers adding up to \(n\) . Each of them must therefore be \(1\) , which says that \(f\) is injective.
The corollary is the fact used without comment in the proof of Fermat’s little theorem. For infinite sets it fails, as Example 2.3 showed with an injection from \(\mathbb Z\) to \(\mathbb Z\) that is not surjective.
A pigeonhole argument has two ingredients to be chosen: the objects and the boxes. The skill is in the choice of boxes.
Example 5.11: A number that divides another
Claim. Among any \(n+1\) different integers chosen from \(\{1,2,\dots,2n\}\) , there are two such that one divides the other.
Proof. Every positive integer can be written uniquely as \(2^{e}m\) with \(e\ge 0\) and \(m\) odd, by unique factorization; call \(m\) its odd part. The odd part of an integer in \(\{1,\dots,2n\}\) is one of the \(n\) odd numbers \(1,3,5,\dots,2n-1\) . Let \(f\) send each of the \(n+1\) chosen integers to its odd part. There are \(n+1\) objects and \(n\) possible values, so by the pigeonhole principle two chosen integers \(a<b\) have the same odd part \(m\) : \(a=2^{e}m\) and \(b=2^{e'}m\) with \(e<e'\) . Then \(b=2^{e'-e}a\) , so \(a\) divides \(b\) .
The number \(n+1\) cannot be lowered: the \(n\) integers \(n+1,n+2,\dots,2n\) contain no such pair, because twice the smallest already exceeds \(2n\) . For \(n=5\) this says that any six numbers from \(1\) to \(10\) contain a pair with one dividing the other, while \(6,7,8,9,10\) do not.
The proof is nonconstructive in the sense of Chapter 1. It shows that a pair exists without saying which pair, and that is typical: the pigeonhole principle is the basic tool for existence proofs in finite mathematics.
5.7 Counting each object exactly once
A count is a claim that a certain description produces every object once and only once. Each half of that claim can fail. An undercount leaves objects out, usually by an oversight in the cases. An overcount produces some objects more than once, and it is harder to notice, because every individual step looks correct.
The test for both is the same and comes straight from the bijection rule. Given a finished object, can you reconstruct the sequence of choices that produced it, and is there only one such sequence? If some object can be produced by no sequence, the count is too small. If some object can be produced by two, the count is too large.
Example 5.12: At least one ace
How many \(5\) -card hands from a standard deck of \(52\) cards contain at least one ace?
A tempting count. “Choose an ace to guarantee the condition, in \(4\) ways. Then choose any \(4\) of the remaining \(51\) cards, in \(\binom{51}{4}=249900\) ways. Total: \(4\cdot 249900=999600\) .”
The test. Take a hand with two aces, say the aces of spades and hearts with three other cards. It is produced once with the ace of spades as the guaranteed ace and the ace of hearts among the other four, and once more with the roles exchanged. The choices cannot be recovered from the hand. A hand with \(j\) aces is counted \(j\) times.
A correct count. By the complement rule, subtract the hands with no ace from all hands:
The size of the error can be accounted for exactly. The number of hands with exactly \(j\) aces is \(\binom 4j\binom{48}{5-j}\) , which for \(j=1,2,3,4\) is \(778320\) , \(103776\) , \(4512\) , and \(48\) . These add up to \(886656\) , as they should. Counting each hand \(j\) times instead gives \(778320+2\cdot 103776+3\cdot 4512+4\cdot 48=999600\) , exactly the tempting answer.
Common mistake. Guaranteeing a condition by a preliminary choice and then choosing “the rest” freely. Whenever the free part of the choice can also satisfy the condition, the same object arises from several preliminary choices. Conditions of the form “at least one” are the usual setting. Count the complement, or sort the objects by exactly how many times the condition is met.
Common mistake. Using the product rule when the number of options depends on earlier choices, or dividing by \(k!\) when not every object has \(k!\) orderings. Example 5.2 shows the first and Example 5.8 the second. Before multiplying, check that each factor is the same whatever came before; before dividing, check that the map from ordered to unordered objects is exactly \(k\) -to-one.
Counting has now been reduced to a handful of rules, each of which is a statement about functions between finite sets. The next chapter studies a kind of object for which these rules give immediate structural results: networks of points and connections, in which the simplest count, of the ends of the connections, already forbids many configurations. A question to carry forward: at a gathering of nine people, can each person shake hands with exactly three of the others? Count the hands.
Exercises
-
Count each set, naming the rule you use: (a) strings of length \(6\) over the alphabet \(\{a,b,c\}\) ; (b) such strings in which no two adjacent letters are equal; (c) five-digit integers, from \(10000\) to \(99999\) , with five different digits; (d) five-digit integers that read the same forwards and backwards.
Answer
(a) \(3^{6}=729\) , by the product rule with \(3\) options at each position. (b) \(3\cdot 2^{5}=96\) : the first letter is free and each later letter must differ from its predecessor. (c) \(9\cdot 9\cdot 8\cdot 7\cdot 6=27216\) : the first digit is not \(0\) , and each later digit avoids those already used. (d) \(9\cdot 10\cdot 10=900\) : the first three digits determine the number.
-
How many integers from \(1000\) to \(9999\) contain the digit \(7\) at least once? Solve it by the complement rule, and explain why a direct count by the position of the first \(7\) is possible but longer.
Solution
There are \(9999-1000+1=9000\) integers in the range. An integer with no digit \(7\) is built by choosing a first digit from the \(8\) digits other than \(0\) and \(7\) , and each of the other three digits from the \(9\) digits other than \(7\) ; these numbers of options do not depend on earlier choices, so there are \(8\cdot 9\cdot 9\cdot 9=5832\) such integers. By the complement rule, \(9000-5832=3168\) integers contain at least one \(7\) .
A direct count must avoid counting an integer once for each \(7\) it contains. Sorting by the position of the first \(7\) does this, since every such integer has exactly one first \(7\) : first digit \(7\) gives \(10^{3}=1000\) ; first \(7\) in the second place gives \(8\cdot 10\cdot 10=800\) ; in the third place \(8\cdot 9\cdot 10=720\) ; in the fourth place \(8\cdot 9\cdot 9=648\) . The total \(1000+800+720+648=3168\) agrees, but it took four cases where the complement took one.
-
Let \(A\) have \(4\) elements and \(B\) have \(6\) . Find the number of functions from \(A\) to \(B\) , the number of injective functions from \(A\) to \(B\) , and, by inclusion and exclusion, the number of surjective functions from \(B\) to \(A\) .
Answer
Functions from \(A\) to \(B\) : \(6^{4}=1296\) . Injective functions: \(6\cdot 5\cdot 4\cdot 3=360\) . Surjective functions from \(B\) to \(A\) : \(4^{6}-\binom 41 3^{6}+\binom 42 2^{6}-\binom 43 1^{6}=4096-2916+384-4=1560\) .
-
A club has \(10\) women and \(8\) men. Count the committees of \(6\) members that (a) are unrestricted; (b) contain exactly \(3\) women; (c) contain at least one man; (d) contain more women than men.
Solution
(a) A committee is a \(6\) -element subset of the \(18\) members: \(\binom{18}{6}=18564\) .
(b) Choose the \(3\) women and then the \(3\) men: \(\binom{10}{3}\binom 83=120\cdot 56=6720\) .
(c) Use the complement. A committee with no man consists of \(6\) women, and there are \(\binom{10}{6}=210\) of those, so \(18564-210=18354\) committees contain at least one man.
(d) More women than men among \(6\) members means \(4\) , \(5\) , or \(6\) women. These cases are disjoint: \(\binom{10}{4}\binom 82=210\cdot 28=5880\) , \(\binom{10}{5}\binom 81=252\cdot 8=2016\) , and \(\binom{10}{6}=210\) . The total is \(5880+2016+210=8106\) .
In (c) the tempting shortcut “choose one man, then any five others”, \(8\cdot\binom{17}{5}\) , overcounts every committee with more than one man, for the reason explained in Example 5.12.
-
Find the number of different arrangements of the letters of MISSISSIPPI, and the number of those arrangements in which the two letters P are adjacent.
Answer
\(\frac{11!}{4!\,4!\,2!}=34650\) . With the two P’s adjacent, treat PP as a single symbol: there are then \(10\) symbols with four I’s and four S’s, giving \(\frac{10!}{4!\,4!}=6300\) .
-
Let \(n\ge 1\) . Give a bijective proof that \([n]\) has as many subsets of even size as of odd size, by describing an explicit function from even-sized subsets to odd-sized subsets and proving that it is a bijection.
Solution
Define \(f\) on all subsets of \([n]\) by toggling the element \(1\) : \(f(S)=S\setminus\{1\}\) if \(1\in S\) , and \(f(S)=S\cup\{1\}\) if \(1\notin S\) . This uses \(n\ge 1\) , so that the element \(1\) exists.
The set \(f(S)\) has one element fewer or one more than \(S\) , so its size has the opposite parity: \(f\) sends even-sized subsets to odd-sized ones and odd-sized subsets to even-sized ones. Toggling twice restores the set, so \(f(f(S))=S\) for every \(S\) .
Let \(g\) be the restriction of \(f\) to the even-sized subsets, regarded as a function into the odd-sized subsets, and let \(h\) be the restriction of \(f\) to the odd-sized subsets, a function into the even-sized ones. The identity \(f\circ f=\mathrm{id}\) says \(h\circ g\) and \(g\circ h\) are identity functions. So \(g\) has an inverse and is a bijection by Theorem 2.9. By the bijection rule the two collections have the same number of elements.
-
Prove by counting one set in two ways that \(\sum_{k=0}^{n}k\binom nk=n2^{n-1}\) for every \(n\ge 1\) . Describe the set, and explain what each side counts.
Solution
Let \(X\) be the set of pairs \((S,c)\) in which \(S\) is a subset of \([n]\) and \(c\) is an element of \(S\) : a committee together with a chair chosen from it.
First count. Sort the pairs by the size \(k\) of \(S\) . There are \(\binom nk\) sets of size \(k\) , and each has \(k\) possible chairs, so there are \(k\binom nk\) pairs with \(\lvert S\rvert=k\) . Summing over \(k\) from \(0\) to \(n\) gives the left side; the term \(k=0\) is zero, as it should be, since an empty committee has no chair.
Second count. Choose the chair \(c\) first, in \(n\) ways. The rest of the committee is an arbitrary subset of the other \(n-1\) elements, chosen in \(2^{n-1}\) ways whatever \(c\) is. The pair is recovered from these choices and conversely, so \(\lvert X\rvert=n2^{n-1}\) .
Both expressions equal \(\lvert X\rvert\) , so they are equal. For \(n=4\) : \(0+4+12+12+4=32=4\cdot 8\) .
-
Give a combinatorial proof that \(\binom rr+\binom{r+1}r+\dots+\binom nr=\binom{n+1}{r+1}\) for \(0\le r\le n\) , by sorting the \((r+1)\) -element subsets of \([n+1]\) according to their largest element.
Hint
An \((r+1)\) -element subset of \([n+1]\) has a largest element, say \(m+1\) , where \(r\le m\le n\) . Its other \(r\) elements form an \(r\) -element subset of \([m]\) . Count the subsets with each possible largest element and add.
-
Find the coefficient of \(x^{3}y^{5}\) in the expansion of \((2x-y)^{8}\) , and find the sum of all the coefficients in that expansion without expanding.
Answer
The term with \(x^{3}y^{5}\) is \(\binom 83(2x)^{3}(-y)^{5}\) , with coefficient \(56\cdot 8\cdot(-1)=-448\) . The sum of all coefficients is the value at \(x=y=1\) , namely \((2-1)^{8}=1\) .
-
Derive Pascal’s rule algebraically from the formula \(\binom nk=\frac{n!}{k!(n-k)!}\) by putting the two fractions over a common denominator. Then say what the combinatorial proof in Theorem 5.7 tells you that the algebraic one does not.
Hint
\(\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}=\frac{(n-1)!\,\bigl(k+(n-k)\bigr)}{k!(n-k)!}\) . The algebra confirms the identity; the combinatorial proof says why it holds, by showing what the two terms count.
-
For right-and-up paths from \((0,0)\) to \((5,5)\) , find (a) the total number; (b) the number passing through \((2,3)\) ; (c) the number avoiding \((2,3)\) ; (d) the number that never go above the diagonal line from \((0,0)\) to \((5,5)\) , using the labelling method of Figure 5.1 on the points on or below the diagonal.
Answer
(a) \(\binom{10}{5}=252\) . (b) \(\binom 52\cdot\binom 53=10\cdot 10=100\) . (c) \(252-100=152\) . (d) Labelling only the points \((i,j)\) with \(j\le i\) , each with the sum of its permitted neighbours to the left and below, gives \(42\) at \((5,5)\) .
-
Find the number of solutions of \(x_1+x_2+x_3+x_4=15\) (a) in natural numbers; (b) in positive integers; (c) in natural numbers with \(x_1\le 5\) .
Solution
(a) By Theorem 5.9 with \(n=15\) and \(k=4\) , the number of solutions in natural numbers is \(\binom{18}{3}=816\) .
(b) In positive integers the count is \(\binom{14}{3}=364\) , by the second part of the theorem.
(c) Count the complement within (a): solutions with \(x_1\ge 6\) . Substituting \(x_1=y_1+6\) gives \(y_1+x_2+x_3+x_4=9\) in natural numbers, which has \(\binom{12}{3}=220\) solutions, and the substitution is a bijection. So \(816-220=596\) solutions have \(x_1\le 5\) .
-
In how many ways can \(7\) books be given to \(3\) students if (a) the books are different; (b) the books are identical copies; (c) the books are different and every student must receive at least one? State which counting model applies in each case.
Solution
(a) The books are different, and a distribution assigns each book to a student: it is a function from the \(7\) books to the \(3\) students. There are \(3^{7}=2187\) .
(b) With identical books only the numbers received matter: a distribution is a solution of \(x_1+x_2+x_3=7\) in natural numbers. By stars and bars there are \(\binom 92=36\) .
(c) The books are different and every student receives at least one, so the function in (a) must be surjective. By inclusion and exclusion over the sets of functions missing each student, the number is
\[ 3^{7}-3\cdot 2^{7}+3\cdot 1^{7}=2187-384+3=1806 . \]The three answers differ by orders of magnitude, although the sentence describing the task is almost the same; what changes is whether the objects are distinguishable and whether a constraint is imposed.
-
Use inclusion and exclusion to find the number of derangements of \(\{1,2,3,4,5\}\) , and deduce the number of permutations of that set with exactly one fixed point.
Solution
Let \(A_i\) be the set of permutations of \(\{1,\dots,5\}\) fixing \(i\) . An intersection of \(j\) of these sets consists of the permutations fixing \(j\) given elements, and has \((5-j)!\) members; there are \(\binom 5j\) such intersections. By inclusion and exclusion the number of permutations with at least one fixed point is
\[ \binom 51 4!-\binom 52 3!+\binom 53 2!-\binom 54 1!+\binom 55 0!=120-60+20-5+1=76 . \]So there are \(120-76=44\) derangements.
A permutation with exactly one fixed point is determined by choosing the fixed point, in \(5\) ways, and then a derangement of the remaining four elements. Example 5.10 found \(9\) derangements of four elements, so there are \(5\cdot 9=45\) such permutations.
-
How many strings of six decimal digits contain each of the digits \(1\) , \(2\) , and \(3\) at least once?
Answer
Subtract from all \(10^{6}\) strings those missing at least one of the three digits: \(10^{6}-3\cdot 9^{6}+3\cdot 8^{6}-7^{6}=1000000-1594323+786432-117649=74460\) .
-
Use inclusion and exclusion over the primes \(2\) , \(3\) , \(5\) , \(7\) to count the integers from \(1\) to \(210\) that are coprime to \(210\) , and check that your answer equals \(210\cdot\frac12\cdot\frac23\cdot\frac45\cdot\frac67\) .
Hint
Multiples of a single prime: \(105+70+42+30=247\) . Of a product of two: \(35+21+15+14+10+6=101\) . Of three: \(7+5+3+2=17\) . Of all four: \(1\) . The union has \(247-101+17-1=162\) elements, leaving \(48\) .
-
Prove that among any \(6\) integers there are two whose difference is divisible by \(5\) , and that among any \(5\) integers there are three whose sum is divisible by \(3\) . Say what the pigeons and the boxes are in each argument.
Solution
Six integers. The pigeons are the \(6\) integers and the boxes are the \(5\) possible remainders on division by \(5\) . By the pigeonhole principle two of the integers have the same remainder, and by Theorem 4.11(b) their difference is divisible by \(5\) .
Five integers. The boxes are the \(3\) remainders on division by \(3\) . Suppose first that some remainder \(r\) occurs for at least three of the integers. Their sum is congruent to \(3r\equiv 0\pmod 3\) . Suppose instead that every remainder occurs at most twice. Two remainders could then account for at most \(4\) of the \(5\) integers, so all three remainders occur. Choose one integer with each remainder; their sum is congruent to \(0+1+2=3\equiv 0\pmod 3\) . In both cases three of the integers have a sum divisible by \(3\) . The first case is where the generalized pigeonhole principle would be invoked if only two boxes were occupied, since \(5>2\cdot 2\) .
-
In a group of \(n\ge 2\) people, some pairs are acquainted, and acquaintance is mutual. Prove that two people in the group have the same number of acquaintances within the group. Be careful about which numbers of acquaintances can occur together.
Solution
Each person has some number of acquaintances between \(0\) and \(n-1\) . That is \(n\) possible values for \(n\) people, so the pigeonhole principle does not apply directly. The extra observation is that the values \(0\) and \(n-1\) cannot both occur. If someone has \(n-1\) acquaintances, that person is acquainted with everyone else, and since acquaintance is mutual, everyone else has at least one acquaintance; so nobody has \(0\) .
Hence the numbers that actually occur lie either in \(\{0,1,\dots,n-2\}\) or in \(\{1,2,\dots,n-1\}\) . Each of these sets has \(n-1\) elements. The function sending each of the \(n\) people to their number of acquaintances therefore takes values in a set of size \(n-1\) , and by the pigeonhole principle it is not injective: two people have the same number of acquaintances.
-
Prove that an injective function from a finite set to itself is surjective, quoting the result of this chapter that applies, and show by an example from Chapter 2 that the statement fails for infinite sets.
Hint
Apply Corollary 5.12 with \(B=A\) . For an infinite counterexample use \(n\mapsto 2n+1\) on \(\mathbb Z\) from Example 2.3, or \(n\mapsto n+1\) on \(\mathbb N\) .
-
A student counts the ways to split \(6\) people into two teams of \(3\) as \(\binom 63=20\) , and the ways to split them into three pairs as \(\binom 62\binom 42\binom 22=90\) . Both answers are too large. Find the correct numbers, and explain the overcount in each case using the division rule.
Solution
Two teams of three. Choosing a \(3\) -element subset does determine a split, into that subset and its complement. But the function from \(3\) -element subsets to splits is two-to-one: a subset and its complement give the same split, because the teams carry no names. By the division rule there are \(20/2=10\) splits.
Three pairs. The product \(\binom 62\binom 42\binom 22=15\cdot 6\cdot 1=90\) counts ordered lists of three disjoint pairs: a first pair, a second, and a third. A split into three unlabelled pairs corresponds to exactly \(3!=6\) such lists, one for each order in which its pairs could be chosen. By the division rule there are \(90/6=15\) splits.
In both cases the count was correct for a more structured object, with the groups labelled or ordered, and the labels then had to be removed by dividing by the number of labellings of each object.
-
A hand of \(5\) cards has “two pairs” if it has two cards of one rank, two of another rank, and a fifth card of a third rank. A student counts: \(13\) ranks for the first pair and \(\binom 42\) ways to choose its suits, \(12\) ranks for the second pair and \(\binom 42\) ways, then \(44\) choices for the fifth card, total \(13\cdot 6\cdot 12\cdot 6\cdot 44\) . Find the error and the correct count.
Solution
The student’s procedure distinguishes a “first” pair from a “second” pair, but a hand does not. The hand with two kings, two fives, and a nine is produced once with kings chosen first and fives second, and again with fives first and kings second. Every two-pair hand is produced exactly twice, so the student’s total \(13\cdot 6\cdot 12\cdot 6\cdot 44=247104\) is twice the true count.
A correct count chooses the two ranks of the pairs together, as an unordered pair of ranks, in \(\binom{13}{2}=78\) ways; then the suits of each pair in \(\binom 42=6\) ways each; then the fifth card from the \(44\) cards of the other eleven ranks. The number of two-pair hands is \(78\cdot 6\cdot 6\cdot 44=123552\) . The test of Section 5.7 exposes the error: from a finished hand one cannot tell which pair was chosen first.
-
Three prizes are awarded among \(10\) contestants. Count the possible outcomes if (a) the prizes are different and nobody may win more than one; (b) the prizes are different and a contestant may win several; (c) the prizes are identical and nobody may win more than one; (d) the prizes are identical and a contestant may win several.
Answer
(a) \(10\cdot 9\cdot 8=720\) . (b) \(10^{3}=1000\) . (c) \(\binom{10}{3}=120\) . (d) \(\binom{12}{3}=220\) .