Lecture 29 — Introduction to Counting

lecture
discrete-math
counting

Counting the outcomes of a process without listing them. The multiplication rule handles a choice made in steps, the addition rule handles a count that splits into separate cases, and subtracting from the total handles “at least one”. Together they count permutations, first of a whole set and then with conditions on the first few positions. Pre-work: Video 037 (Introduction to Counting). The rules, why they work and where they go wrong are collected in counting-principles, and choosing elements without regard to order carries on in 2026-10-13-counting-selections.

Goals

  1. Learn how to solve simple counting problems.
  2. Learn how to count permutations when restrictions are added.
  3. Learn some counting techniques and understand why they work.

Two questions to keep in mind:

  • How do you count arrangements of only some of the elements, the \(r\)-permutations? A four-symbol number plate with no repeated symbol is one, in the number plates, part (b). The general count is in counting-principles.
  • When do you add and when do you multiply? Multiply across the steps of one choice, add across cases that cannot both happen. The summary at the end.

Worked: arranging \(1, 2, 3, 4, 5\)

How many permutations of \(\{1, 2, 3, 4, 5\}\) are there? Explain your reasoning.

Build the arrangement one position at a time. Any of the 5 numbers can go first. Whichever it was, 4 numbers are left for the second position, then 3 for the third and 2 for the fourth, and the last position takes the one number remaining. So there are

\[5 \times 4 \times 3 \times 2 \times 1 = 5! = 120\]

permutations.

Following one arrangement through shows what “4 left” means. Put 3 first. The second position can then take 1, 2, 4 or 5, which is 4 options. Put 4 there, and the third can take 1, 2 or 5. Put 2, and the fourth can take 1 or 5. Put 1, and the last must be 5. That builds \(3\,4\,2\,1\,5\). Starting with 1 instead of 3 leaves a different four for the second position, \(\{2, 3, 4, 5\}\), but still four of them. What the multiplication rule needs is that the number of options at each step is the same whatever was chosen before, even though the options themselves change. As a possibility tree, the start has 5 branches, each of those has 4, each of those 3, and so on, so there are \(5 \times 4 \times 3 \times 2 \times 1\) leaves, one per permutation.

Figure 1: Part of the possibility tree for arranging \({1, 2, 3, 4, 5}\), one position at a time. Only the path that builds \(3,4,2,1,5\) is followed; every grey node branches in the same way. At each level every node has the same number of branches, 5, then 4, 3, 2 and 1, whichever numbers have been used, so the tree has \(5 \times 4 \times 3 \times 2 \times 1 = 120\) leaves, one for each permutation.

The complete tree for three elements, small enough to draw in full, is in counting-principles.

Worked: one odd and one even

How many ways are there to choose two of the numbers \(1, 2, 3, 4, 5, 6, 7, 8, 9\) if one of the chosen numbers is odd and the other is even?

Sort the nine numbers by parity:

\[D = \{1, 3, 5, 7, 9\}, \qquad E = \{2, 4, 6, 8\}.\]

There are five odd numbers to choose from and four even ones. Every odd number goes with every even number, so the valid choices fill a grid with one row per odd number and one column per even number:

\(2\) \(4\) \(6\) \(8\)
\(\mathbf{1}\) 1 and 2 1 and 4 1 and 6 1 and 8
\(\mathbf{3}\) 3 and 2 3 and 4 3 and 6 3 and 8
\(\mathbf{5}\) 5 and 2 5 and 4 5 and 6 5 and 8
\(\mathbf{7}\) 7 and 2 7 and 4 7 and 6 7 and 8
\(\mathbf{9}\) 9 and 2 9 and 4 9 and 6 9 and 8

For each of the 5 choices of odd number there are 4 choices of even number, so there are \(5 \times 4 = 20\) ways. In set terms the grid is the Cartesian product \(D \times E\), the ordered pairs \((a, b)\) with \(a\) odd and \(b\) even, and

\[|D \times E| = |D| \times |E| = 5 \times 4 = 20\]

(sets-and-set-notation).

The order of choosing does not matter. Choosing 1 and 2 is the same as choosing 2 and 1. Even so, the ordered pairs count the unordered choices exactly: every valid choice has exactly one odd member, so writing the odd one first turns each choice into exactly one pair \((a, b) \in D \times E\), and each pair comes from exactly one choice. That matching is a bijection, and matched finite sets have the same size (cardinality). Each choice appears once in the grid, in the row of its odd number. Counting “first number picked, then second” instead gives \(5 \times 4 + 4 \times 5 = 40\), which counts every pair twice.

Choosing from \(\{1, \dots, 8\}\): prime, composite or neither

Let \(X = \{1, 2, 3, 4, 5, 6, 7, 8\}\), so \(|X| = 8\). Every element of \(X\) is in exactly one of

\[P = \{2, 3, 5, 7\}\ \text{(prime)}, \qquad C = \{4, 6, 8\}\ \text{(composite)}, \qquad \{1\}\ \text{(neither)}.\]

1 is neither prime nor composite, and both questions turn on it.

Worked: one prime and one composite

How many ways are there to choose two numbers from \(X\) such that one is prime and the other is composite?

A. 7 \(\quad\) B. 12 \(\quad\) C. 15 \(\quad\) D. 24

B, 12. As with odd and even, a valid choice has exactly one prime member and one composite member, so it matches exactly one ordered pair in \(P \times C\):

\[|P \times C| = |P| \times |C| = 4 \times 3 = 12.\]

The other options each make a recognisable mistake. 24 counts every pair twice, once in each order. 7 is \(4 + 3\), adding where both choices are made and so the counts multiply. 15 is \(5 \times 3\), which treats 1 as a prime.

Worked: prime or composite

How many ways are there to choose one number from \(X\) such that it is prime or composite?

A. 3 \(\quad\) B. 7 \(\quad\) C. 8 \(\quad\) D. 12

B, 7. Every element of \(X\) except 1 is prime or composite, so the count is

\[|X - \{1\}| = 8 - 1 = 7.\]

That counts by the complement: take everything and remove what is excluded. Counting the wanted numbers directly gives the same. No number is both prime and composite, so \(P\) and \(C\) are disjoint, and by the addition rule \(|P \cup C| = |P| + |C| = 4 + 3 = 7\). Only one number is chosen, and it is a prime or a composite, so the counts add. 12 multiplies as if two numbers were chosen, 8 forgets to leave out 1, and 3 counts only the composites.

The two counts use the same sets and the same sizes, 4 and 3, and differ only in how many numbers are chosen. One number from either of two disjoint sets adds their sizes. One number from each of them multiplies.

Figure 2: \(X = {1, \dots, 8}\) split into the primes \(P\), the composites \(C\), and 1, which is neither. Left: one number that is prime or composite is a single choice from the shaded part of \(X\). No number is in both \(P\) and \(C\), so the shaded part has \(4 + 3 = 7\) elements. Right: one prime and one composite is a choice from each part. Every prime can go with every composite, so the choices fill a grid with a row for each prime and a column for each composite, \(4 \times 3 = 12\) cells, the pairs of \(P \times C\). A choice from either part adds the sizes; a choice from each part multiplies them. 1 is in neither count.

Permutations

A permutation of a set of objects is an arrangement of the objects into an order.

How many permutations of \(\{1, 2, 3, 4\}\) are there? For each of the four choices for the first number, there are three ways to choose the second. Once the first two are chosen there are two ways to choose the third, and then the fourth is forced. So there are \(4 \times 3 \times 2 \times 1 = 24\) permutations. Listed in dictionary order they fall into blocks, and the sizes of the blocks are the factors of the product.

Figure 3: The 24 permutations of \({1, 2, 3, 4}\) in dictionary order, as nested blocks. The first number picks the column, 4 ways. Inside a column the second number picks one of 3 boxes, since one number is already used. Inside a box the third number picks one of 2 rows, and the fourth number is whatever is left. Each level splits every block into the same number of pieces, so the total is \(4 \times 3 \times 2 \times 1 = 4! = 24\).

The same reasoning works for any number of objects.

The number of permutations of a set of \(n\) distinct objects is \[n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!\]

\(n!\) is read “\(n\) factorial”, or “\(n\) bang”. As a product, \(n! = \prod_{i=1}^{n} i\) for \(n \in \mathbb{Z}^{+}\), and \(0! = 1\) by definition (recursive-definitions). The values grow very fast:

\(n\) 1 2 3 4 5 6 7
\(n!\) 1 2 6 24 120 720 5040

A bijection from \(\{1, \dots, n\}\) to itself is fixed by listing \(f(1), f(2), \dots, f(n)\), which is a permutation of \(\{1, \dots, n\}\). So the symmetric group \(S_n\) has \(n!\) elements, and \(S_3\) has the six of symmetric-group.

Worked: starting with an even number

How many permutations of the numbers 1, 2, 3, 4, 5 start with an even number?

Fill the restricted position first. The first number must be 2 or 4, so there are 2 choices. Whichever it is, the other four numbers fill the remaining four positions in any order, in \(4! = 24\) ways. So the answer is

\[2 \times 4! = 2 \times 24 = 48.\]

Position by position that is \(2 \times 4 \times 3 \times 2 \times 1\). If 2 goes first, the second position can take any of 1, 3, 4, 5, and 4 is still among them: the even number not chosen is free to go anywhere else.

A check: each of the five numbers starts the same number of permutations, \(4!\) each, and two of the five are even, so the answer is \(\frac{2}{5}\) of the \(5! = 120\) permutations, which is 48.

Worked: starting with a prime

How many permutations of \(\{1, 2, 3, 4, 5, 6, 7\}\) start with a prime number?

A. \(4 \times 6 = 24\) \(\quad\) B. \(4! \times 3! = 144\) \(\quad\) C. \(4 \times 6! = 2880\) \(\quad\) D. \(5 \times 6! = 3600\)

C, 2880. Let \(N = \{1, 2, 3, 4, 5, 6, 7\}\) and \(P = \{2, 3, 5, 7\}\). The first position has \(|P| = 4\) choices. Once it is filled, any of the \(|N| - 1 = 6\) remaining numbers can go second, any of the \(|N| - 2 = 5\) still remaining can go third, and so on down to 1 for the last position:

\[|P| \times (|N| - 1)! = 4 \times 6! = 4 \times 720 = 2880.\]

If 5 goes first, for instance, the other six positions are filled from \(\{1, 2, 3, 4, 6, 7\}\). That includes the primes 2, 3 and 7. Only the first position is restricted, and the rest is an unrestricted arrangement of what is left.

Figure 4: Counting the permutations of \({1, \dots, 7}\) that start with a prime, one position at a time. The restricted position is filled first, from the 4 primes. Each later position has one fewer number available than the one before, whatever was placed earlier, so the last six positions are an arrangement of the six numbers left: \(6!\) ways. The multiplication rule gives \(4 \times 6! = 2880\).

Each wrong option is a different mistake:

  • A, \(4 \times 6\), fills the first two positions and forgets the other five.
  • B, \(4! \times 3!\), arranges the four primes among themselves and the three non-primes among themselves. That counts the permutations with all four primes at the front, a much stronger condition.
  • D, \(5 \times 6!\), counts 1 as a prime.

Worked: what comes second

  1. How many permutations of \(\{1, 2, 3, 4, 5, 6, 7\}\) start with a prime number followed by a composite number?
  2. How many permutations of \(\{1, 2, 3, 4, 5, 6, 7\}\) start with a prime number followed by an odd number?

The sets involved, inside \(N = \{1, 2, 3, 4, 5, 6, 7\}\):

\[P = \{2, 3, 5, 7\}, \qquad C = \{4, 6\}, \qquad D = \{1, 3, 5, 7\}\ \text{(odd)}.\]

(a) Position 1 is a prime, 4 choices. Position 2 is a composite, 2 choices, however position 1 was filled: no prime is composite, so the first choice never uses up a composite. Positions 3 to 7 hold the 5 numbers left, in any order. So

\[|P| \times |C| \times (|N| - 2)! = 4 \times 2 \times 5! = 8 \times 120 = 960.\]

(b) The same approach stalls at position 2. How many odd numbers are left depends on which prime went first. If it was 2, all four odd numbers are still available. If it was 3, 5 or 7, an odd number has been used and only three remain. The multiplication rule needs the count at each step to be the same whatever came before, so split into cases on the first number, and within each case it is the same every time.

  • Case 1: the first number is even, so it is 2. One choice for position 1, then \(|D| = 4\) for position 2, then \(5!\) for the rest: \(1 \times 4 \times 5!\).
  • Case 2: the first number is odd, so it is 3, 5 or 7. That is \(|P| - 1 = 3\) choices for position 1, then \(|D| - 1 = 3\) for position 2, since the first number used up an odd number, then \(5!\) for the rest: \(3 \times 3 \times 5!\).

Every qualifying permutation is in exactly one case, because its first number either is 2 or is not. So the addition rule adds them:

\[1 \times 4 \times 5! + 3 \times 3 \times 5! = (4 + 9) \times 5! = 13 \times 120 = 1560.\]

Multiplying straight through, \(4 \times 4 \times 5! = 1920\), is wrong: it allows four odd numbers in position 2 after an odd prime, when only three are left.

Figure 5: The possibility tree for the first two positions of a permutation of \({1, \dots, 7}\) that starts with a prime followed by an odd number. The tree is lopsided: after 2 there are four odd numbers to follow, but after 3, 5 or 7 there are only three, because the first number used one of them up. So the multiplication rule cannot be applied in one go. Splitting on the first number gives two cases that are each regular, \(1 \times 4\) and \(3 \times 3\) starts. They add to 13, and each start is completed by arranging the other five numbers.

Worked: permutations of \(\{1, \dots, 60\}\)

  1. How many permutations of \(\{1, 2, \dots, 60\}\) start with an even number followed by a number that is divisible by 3?
  2. How many permutations of \(\{1, 2, \dots, 60\}\) have at least one even number in the first two positions?

Let \(N = \{1, 2, \dots, 60\}\), so \(|N| = 60\), and

\[E = \{n \in N : n \text{ is even}\}, \qquad T = \{n \in N : 3 \mid n\}.\]

Then \(|E| = 30\) and \(|T| = 20\). The numbers in both are the multiples of 6, so \(|E \cap T| = 10\), and \(|E - T| = 30 - 10 = 20\).

(a) This is the difficulty of prime followed by odd again. An even first number that is also a multiple of 3 uses up one of the multiples of 3, and one that is not leaves all 20 of them. So split on whether the first number is divisible by 3.

  • Case 1: the first number is divisible by 3. It is in \(E \cap T\), 10 choices. Position 2 takes any of the other \(|T| - 1 = 19\) multiples of 3. The remaining 58 numbers go in any order: \(10 \times 19 \times 58!\).
  • Case 2: the first number is not divisible by 3. It is in \(E - T\), 20 choices. Position 2 takes any of the \(|T| = 20\) multiples of 3. Then \(58!\) for the rest: \(20 \times 20 \times 58!\).

\[\text{total} = 10 \times 19 \times 58! + 20 \times 20 \times 58! = (190 + 400) \times 58! = 590 \times 58!.\]

That is about \(1.39 \times 10^{81}\), and the factorial form is the sensible way to leave it.

Figure 6: The even numbers \(E\) and the multiples of 3, \(T\), in \({1, \dots, 60}\), with the size of each region. The two cases of part (a) are the two parts of \(E\). If the first number comes from the overlap, the multiples of 6, it is itself a multiple of 3 and leaves only 19 for the second position. If it comes from the rest of \(E\), all 20 multiples of 3 are still available.

(b) “At least one even number in the first two positions” happens in three ways, writing E for even and O for odd: EE, EO and OE. Each is a regular count.

  • EE: 30 even numbers for position 1, then 29 for position 2: \(30 \times 29 \times 58!\).
  • EO: 30 even, then 30 odd: \(30 \times 30 \times 58!\).
  • OE: 30 odd, then 30 even: \(30 \times 30 \times 58!\).

\[(30 \times 29 + 30 \times 30 + 30 \times 30) \times 58! = (870 + 900 + 900) \times 58! = 2670 \times 58!.\]

Or count the complement. The only way to fail is OO, both odd. So

\[\#\text{permutations} = (\text{all permutations, no restriction}) - (\text{permutations starting odd, odd}) = 60! - 30 \times 29 \times 58!.\]

The two answers agree: \(60! = 60 \times 59 \times 58! = 3540 \times 58!\), and \(3540 - 870 = 2670\). The complement is one case to count instead of three, which is why it is the natural tool for “at least one”.

Figure 7: Every permutation of \({1, \dots, 60}\) falls in exactly one cell, according to the parity of its first two numbers; each count shown is then multiplied by \(58!\) for the other positions. A diagonal cell is \(30 \times 29\) because the second number has the same parity as the first and one of them is used up. The three shaded green cells are the permutations with at least one even number in the first two positions. They can be added cell by cell, or found as everything, \(60 \times 59 = 3540\), minus the one red cell where both are odd. Both give \(2670 \times 58!\).

Worked: number plates

In a certain state, number plates consist of four, five or six symbols chosen from the 26 letters of the alphabet together with the ten digits \(0, 1, \dots, 9\).
(a) How many distinct number plates are possible if repetition of symbols is allowed?
(b) How many distinct number plates are possible if repetition of symbols is not allowed?
(c) How many distinct number plates contain at least one repeated symbol?
(d) How many distinct number plates contain exactly one digit?

The symbols form a set \(S\) of \(|S| = 26 + 10 = 36\), adding because no symbol is both a letter and a digit. A plate is ordered: \(\mathtt{AB12}\) and \(\mathtt{21BA}\) are different plates. So a plate of length \(k\) is a sequence of \(k\) symbols. Every plate has exactly one length, so in each part the plates split into three cases, of length 4, 5 and 6, which add.

(a) Repetition allowed. Each position can be any of the 36 symbols, whatever is in the other positions. A four-symbol plate can be made in \(36 \times 36 \times 36 \times 36 = 36^4\) ways, and in general a \(k\)-symbol plate in \(36^k\) ways.

\[36^4 + 36^5 + 36^6 = 1\,679\,616 + 60\,466\,176 + 2\,176\,782\,336 = 2\,238\,928\,128.\]

(b) Repetition not allowed. Each symbol placed leaves one fewer for the positions after it. A four-symbol plate can be made in

\[36 \times 35 \times 34 \times 33 = \frac{36!}{32!} = \frac{36!}{(36 - 4)!}\]

ways. It is an ordered selection of 4 of the 36 symbols, a 4-permutation of \(S\) (counting-principles).

\[\begin{aligned} &36 \times 35 \times 34 \times 33 \\ +\ &36 \times 35 \times 34 \times 33 \times 32 \\ +\ &36 \times 35 \times 34 \times 33 \times 32 \times 31 \end{aligned} \;=\; 1\,413\,720 + 45\,239\,040 + 1\,402\,410\,240 \;=\; 1\,449\,063\,000.\]

(c) At least one repeated symbol. A plate has at least one repeated symbol exactly when it is not a plate with no repeats. The plates in (b) are among the plates in (a), with the same lengths, so subtract:

\[\text{part (a)} - \text{part (b)} = 2\,238\,928\,128 - 1\,449\,063\,000 = 789\,865\,128.\]

Counted directly, “at least one repeat” would need cases for which symbol repeats, where and how often. The complement avoids all of that.

(d) Exactly one digit. Repetition is allowed here, as in (a): the letters may repeat, and with only one digit the digit cannot. Write \(D = \{0, 1, \dots, 9\}\) and \(L = \{\mathtt{A}, \mathtt{B}, \dots, \mathtt{Z}\}\). For a four-symbol plate with its digit first, the positions hold a digit, a letter, a letter and a letter:

\[|D| \times |L| \times |L| \times |L| = 10 \times 26^3.\]

The digit can be in any of the 4 positions, and those are 4 disjoint cases of the same size, so a four-symbol plate with exactly one digit can be made in \(4 \times 10 \times 26^3\) ways. Equivalently, choose the digit’s position (4 ways), then the digit (10), then the three letters (\(26^3\)). Doing the same for each length and adding,

\[4 \times 10 \times 26^3 + 5 \times 10 \times 26^4 + 6 \times 10 \times 26^5 = 703\,040 + 22\,848\,800 + 712\,882\,560 = 736\,434\,400.\]

If repetition were not allowed, only the letters would change: \(26 \times 25 \times 24\) in place of \(26^3\), and so on.

Figure 8: Plates with exactly one digit, \(D\), and letters, \(L\), everywhere else. A four-symbol plate has its digit in one of four positions, and each of those four disjoint cases is filled in \(10 \times 26^3\) ways, so the four rows together give \(4 \times 10 \times 26^3\). Five- and six-symbol plates work the same way, with 5 and 6 positions for the digit. Within a length the rule is multiply; across the three lengths, which no plate can share, it is add.

When to add and when to multiply

Every question above used one or more of three moves.

Move When Examples here
Multiply One outcome is built in steps, and the number of options at each step is the same whatever was chosen before. \(5!\) arrangements; one odd and one even, \(5 \times 4\); prime then composite, \(4 \times 2 \times 5!\)
Add The outcomes split into cases that cannot happen together, and every outcome is in one of them. prime or composite, \(4 + 3\); prime then odd, \((4 + 9) \times 5!\); plates of length 4, 5 or 6
Subtract What is not wanted is easier to count than what is. \(\lvert X - \{1\} \rvert = 8 - 1\); \(60! - 30 \times 29 \times 58!\); plates with a repeat, (a) \(-\) (b)

“Followed by” and “one from each” are steps, so they multiply. An “or” between alternatives that exclude each other is a case split, so it adds. When a step’s count does depend on an earlier choice, split on that choice: inside each case the count is fixed, so the cases multiply out separately and then add. The rules, with the reasons and the common traps, are in counting-principles.

See also