Counting without listing

Many questions in mathematics and computing ask how many, and listing the answers stops being possible almost at once: there are more subsets of a forty element set than there are stars in the Milky Way.

This lesson collects the four tools that count without listing. Two of them, the sum and product rules, build a count from smaller counts. The third counts a set by pairing it perfectly with a set that is easier to count. The fourth, the pigeonhole principle, does something stranger: it uses a count to prove that an object exists without ever producing it. The lesson assumes only sets and functions, and it recalls what a bijection is where it is needed.

The sum rule

If a set splits into pieces that do not overlap, its size is the sum of the sizes of the pieces. Written with sets, if $A$ and $B$ are disjoint then $| A \cup B | = | A | + | B |$ , and the same holds for any finite number of pairwise disjoint pieces. The proof is hardly a proof: counting every element of the union once is the same as counting the elements of $A$ and then carrying on through $B$ , and disjointness guarantees that nothing is met twice.

The rule is almost too obvious to state, and its value lies in what it permits. A hard count can be broken into cases, each case counted by whatever method suits it, and the answers added. The one condition is that the cases must not overlap, and a case analysis that quietly double counts is the most common error in the subject. When the pieces do overlap, the sum overcounts by exactly the elements that are shared, and correcting for that exactly is the business of a later lesson on inclusion and exclusion.

A close relative is counting by complement. If $A$ sits inside a universe $U$ , then $A$ and its complement $U ∖ A$ split $U$ into two disjoint pieces, so $| A | = | U | - | U ∖ A |$ . This is the sum rule read backwards, and it is the right move whenever a condition says "at least one": the complement says "none", which is usually far easier to count. How many integers from $1$ to $999$ contain at least one digit $7$ ? Pad each with leading zeros to three digits; the strings with no $7$ anywhere number $9 \times 9 \times 9 = 729$ , which includes $000$ , so $728$ of the integers from $1$ to $999$ avoid the digit, and the remaining $999 - 728 = 271$ contain it.

That last count already used a multiplication, and the rule behind it deserves its own section.

The product rule

The probability course derives the product rule from a grid of choices: if a first choice can be made in $a$ ways and, whatever it was, a second in $b$ ways, the pair can be made in $a b$ ways. With $k$ stages it becomes a product of $k$ factors. The proof is the sum rule in disguise: group the outcomes by the first choice, so that there are $a$ disjoint groups of $b$ each, and add.

That grouping also shows exactly what the rule needs. The later stages may depend on the earlier ones in which options they offer, but not in how many. Consider four digit PINs in which no two adjacent digits are equal. The first digit has $10$ options. The second must differ from the first, and whichever the first was, that leaves $9$ . The third must differ from the second, again $9$ , and the fourth $9$ more, giving $10 \times 9^{3} = 7290$ . The set of allowed digits changes at every stage, but its size does not, and size is all the rule looks at.

Two real systems show the rule at work. The Dartmouth BASIC of 1964 allowed a variable name to be a single letter or a letter followed by one digit. Those two kinds of name are disjoint, so the sum rule adds them, and the product rule counts the second kind: $26 + 26 \times 10 = 286$ variables in all. The genetic code reads DNA, an alphabet of four bases, in words called codons that specify twenty amino acids and a stop signal. Words of two bases would give only $4^{2} = 16$ possibilities, too few for twenty one meanings; words of three give $4^{3} = 64$ , which is enough with room to spare, and the real code is indeed read in triplets, most amino acids having several codons.

Example. How many integers from $1$ to $9999$ contain no digit $0$ ?

Split by the number of digits, since integers of different lengths form disjoint sets and the sum rule will add them. An integer with $d$ digits and no zero has each of its $d$ digits chosen from $1$ to $9$ , so by the product rule there are $9^{d}$ of them. The total is $9 + 81 + 729 + 6561 = 7380$ . Padding with leading zeros would not have worked directly here, because the padded zeros are exactly what the condition forbids, which is why the cases were needed.

Now you. How many integers from $1$ to $999$ have all their digits different?

Answer

Split by length again. One digit integers: $9$ . Two digits: the first from $1$ to $9$ , the second any of the $9$ digits other than the first, so $81$ . Three digits: $9 \times 9 \times 8 = 648$ , since the third must avoid two digits already used. The total is $9 + 81 + 648 = 738$ .

Counting one set by counting another

A bijection from $A$ to $B$ is a function that pairs every element of $A$ with exactly one element of $B$ and leaves nothing in $B$ unpaired. For finite sets that is the definition of having the same size, so $| A | = | B |$ as soon as a bijection exists, and the second set may be much easier to count than the first. Much of combinatorics consists of finding the right $B$ .

The cleanest illustration is a knockout tournament. The Wimbledon singles draw has $128$ players; how many matches are played? One could count rounds: $64$ in the first, then $32$ , $16$ , $8$ , $4$ , $2$ and the final, totalling $127$ . The bijection argument is shorter and more general. Every match produces exactly one loser, and every player except the champion loses exactly once, since a loss ends their tournament. So matches pair off perfectly with the players who are not the champion, and there are $128 - 1 = 127$ of them. The same argument works for a draw of $100$ players with byes, where counting by rounds becomes awkward: $99$ matches, whatever the arrangement of the byes.

A bijection is a claim that has to be checked in both directions. It must be a function (each element of $A$ goes somewhere definite), it must be one to one (different elements go to different places), and it must be onto (everything in $B$ is hit). The usual way to settle the last two at once is to write down the inverse: a rule taking each element of $B$ back to the element of $A$ it came from. In the tournament, the inverse takes a non-champion to the match they lost, which is plainly well defined.

Divisors give a more arithmetical example. Every positive integer factors into primes in exactly one way, a fact proved in a later lesson, so $720 = 2^{4} \times 3^{2} \times 5$ . A divisor of $720$ can only use these primes, and no more of each than $720$ has, so it is $2^{a} 3^{b} 5^{c}$ with $0 \leq a \leq 4$ , $0 \leq b \leq 2$ and $0 \leq c \leq 1$ . Uniqueness of factorisation makes the map from exponent triples to divisors a bijection, and the triples are counted by the product rule.

Example. How many positive divisors does $720$ have?

By the bijection just described, the divisors correspond to triples $(a, b, c)$ with $a$ one of the $5$ values $0$ to $4$ , $b$ one of the $3$ values $0$ to $2$ , and $c$ one of the $2$ values $0$ or $1$ . The product rule gives $5 \times 3 \times 2 = 30$ . In general, a number whose factorisation has exponents $e_{1}, e_{2}, \dots, e_{r}$ has $(e_{1} + 1) (e_{2} + 1) \dots (e_{r} + 1)$ divisors, the $+ 1$ in each factor accounting for the option of leaving that prime out.

Now you. How many positive divisors does $1 000 000$ have, and how many of them are perfect squares?

Answer

$1 000 000 = 2^{6} \times 5^{6}$ , so there are $7 \times 7 = 49$ divisors. A divisor $2^{a} 5^{b}$ is a perfect square exactly when both exponents are even, which allows $a$ and $b$ each to be $0$ , $2$ , $4$ or $6$ , giving $4 \times 4 = 16$ square divisors.

Subsets and bit strings

How many subsets does a set of $n$ elements have? List the elements in some fixed order, $x_{1}, x_{2}, \dots, x_{n}$ , and send each subset $S$ to the string of $n$ bits whose $i$ th bit is $1$ if $x_{i} \in S$ and $0$ if not. The subset ${x_{1}, x_{3}}$ of a four element set becomes $1010$ , the empty set becomes $0000$ and the whole set $1111$ . The inverse reads the string and collects the positions holding a $1$ , so this is a bijection, and the bit strings are counted by the product rule: each of the $n$ positions has $2$ options, giving $2^{n}$ .

The same picture explains why computers store sets this way. A subset of a $64$ element set fits exactly in one $64$ bit machine word, union becomes bitwise OR, and intersection becomes bitwise AND. It also shows how fast subsets multiply: a thirty element set has $2^{30} = 1 073 741 824$ of them, so an algorithm that checks every subset of its input is hopeless well before the input reaches a hundred items.

Bijections can also compare two sets without counting either. Among the subsets of ${1, 2, \dots, n}$ , with $n \geq 1$ , which are more numerous, those of even size or those of odd size? Pair each subset with the one obtained by toggling the element $1$ : add it if absent, remove it if present. Toggling twice returns the original subset, so the map is its own inverse and therefore a bijection, and it changes the size by exactly one, so it pairs every even subset with an odd one. The two kinds are equal in number, $2^{n - 1}$ each, and no formula for the number of subsets of a given size was needed to see it.

The pigeonhole principle

If more than $k$ objects are placed in $k$ boxes, some box holds at least two. The proof is by contradiction: if every box held at most one, there would be at most $k$ objects. What makes the principle powerful is what it does not say. It names no box and no pair, so it proves existence without construction, and the art is entirely in choosing the boxes.

A counting fact about files shows the flavour. No lossless compressor can shorten every file. There are $2^{n}$ files of exactly $n$ bits, but only $2^{0} + 2^{1} + \dots + 2^{n - 1} = 2^{n} - 1$ files shorter than that. If every $n$ bit file were sent to a shorter one, two would land on the same output, and decompression could not tell them apart. Every compressor that shrinks some files must lengthen others.

Example. Prove that any $11$ integers chosen from $1$ to $20$ include two of which one divides the other.

Write each integer as $2^{a} m$ with $m$ odd; $m$ is its odd part. The odd parts of numbers from $1$ to $20$ lie among the ten odd numbers $1, 3, \dots, 19$ , so these are the boxes. Eleven integers in ten boxes put two, say $2^{a} m$ and $2^{b} m$ with $a < b$ , in the same box, and then the first divides the second. The bound is sharp: the ten integers $11$ to $20$ contain no such pair, since the smallest multiple of $11$ beyond itself is $22$ . This is a result of Paul Erdős, stated for $n + 1$ integers from $1$ to $2 n$ .

Now you. Prove that any $6$ integers chosen from $1$ to $10$ include two that sum to $11$ .

Answer

Use as boxes the five pairs ${1, 10}$ , ${2, 9}$ , ${3, 8}$ , ${4, 7}$ and ${5, 6}$ , each summing to $11$ and together covering $1$ to $10$ . Six integers in five boxes put two in the same pair, and they sum to $11$ . Five integers are not enough: $1$ to $5$ contains no such pair.

The generalised form

If $N$ objects go into $k$ boxes, some box holds at least $⌈ N / k ⌉$ of them, the ceiling meaning $N / k$ rounded up. Again by contradiction: if every box held at most $⌈ N / k ⌉ - 1$ , which is less than $N / k$ , the total would be less than $k \times N / k = N$ .

The 2021 census counted $8 799 800$ people in London. A human scalp carries around a hundred thousand hairs, and certainly nobody has a million, so the possible hair counts are $0$ to $999 999$ , a million boxes. Some hair count is therefore shared by at least $⌈ 8 799 800 / 1 000 000 ⌉ = 9$ Londoners. Nobody will ever find them, and the argument does not need to.

Read the other way, the principle gives thresholds. To guarantee that three people share a birth month, $2 \times 12 + 1 = 25$ people are needed: twenty four could be spread two per month.

What the rules leave open

The sum and product rules, bijections and the pigeonhole principle count anything whose structure can be described, and the structures that turn up most often are arrangements and selections. How many orders can ten runners finish in, or how many committees of three can ten people form? The product rule answers the first and, with a correction for order, the second, but the same reasoning recurs so often that it deserves formulas of its own. The next lesson derives them, and extends them to selections in which repetition is allowed.