Counting Principles

definitions
discrete-math
counting

The rules for counting the outcomes of a process without listing them. The multiplication rule counts outcomes built in steps. The addition rule counts something that splits into cases that cannot happen together. Subtracting from the total counts what you want by counting what you don’t. Applied to putting objects in order they give permutations, \(n!\) arrangements of \(n\) objects, and \(r\)-permutations, the \(\frac{n!}{(n-r)!}\) ordered selections of \(r\) of them. Selections where order does not matter, and the other kinds of selection, are in counting-selections. First met in 2026-10-12-introduction-to-counting.

The multiplication rule

The multiplication rule. Suppose each outcome is built by \(k\) steps carried out one after another, and that step \(i\) can always be done in \(n_i\) ways, whatever was chosen at the earlier steps. Then the number of outcomes is \[n_1 \times n_2 \times \cdots \times n_k.\]

Each outcome needs exactly one choice at every step, which is why the counts multiply. If step 1 has \(n_1\) options and each of them can be followed by \(n_2\) options at step 2, there are \(n_1\) groups of \(n_2\), which is \(n_1 \times n_2\) two-step beginnings.

“Whatever was chosen at the earlier steps” is the condition to check. It is the number of options that must not depend on earlier choices. The options themselves may change. Arranging \(1, 2, 3, 4, 5\): if 3 goes first, the second position can take 1, 2, 4 or 5, and if 1 goes first it can take 2, 3, 4 or 5. Those are different sets of options, but there are four of them either way, so the rule applies and gives \(5 \times 4 \times 3 \times 2 \times 1 = 120\). When the number of options does change, split into cases first (below).

With two steps, one choice from a set \(A\) and one from a set \(B\), the outcomes are the ordered pairs of \(A \times B\), and the rule is the familiar \(|A \times B| = |A| \times |B|\) (sets-and-set-notation). Choosing one odd and one even number from \(1, \dots, 9\) is \(|D \times E| = 5 \times 4 = 20\), where \(D\) is the odd numbers and \(E\) the even ones. The order the two numbers are picked in does not matter there, but each choice still matches exactly one pair (odd, even), so the count is right (2026-10-12-introduction-to-counting).

Possibility trees

A possibility tree draws a stepwise process. Each level is a step, each branch is one option at that step, and each path from the start to a leaf is one complete outcome. Counting outcomes is counting leaves.

Figure 1: The possibility tree for arranging \({1, 2, 3}\), built one position at a time. Every node at the first level has 2 branches and every node at the second has 1, whichever numbers were used. Because each level splits evenly, the number of leaves is the product of the branch counts, \(3 \times 2 \times 1 = 6\), one for each permutation. If the branch counts at a level differed, the leaves would have to be added up branch by branch.

A tree is worth drawing for a small case even when it is too big to finish, because it shows whether every node at a level has the same number of branches. If it does, multiply. If it doesn’t, as for a permutation of \(\{1, \dots, 7\}\) that starts with a prime followed by an odd number, the leaves have to be added branch by branch (2026-10-12-introduction-to-counting).

Worked: casting two roles

From practice-problems, Q1. Six people audition for Romeo, and eight other people audition for Juliet. How many ways can the lead couple be cast?

Step 1, choose Romeo: 6 ways. Step 2, choose Juliet: 8 ways, whoever was cast as Romeo, because nobody is in both groups. So there are \(6 \times 8 = 48\) ways. If the same person could audition for both roles, step 2’s count would depend on step 1 and the rule could not be used as it stands.

The addition rule

The addition rule. If a finite set \(A\) is the union of mutually disjoint subsets \(A_1, A_2, \dots, A_k\), then \[|A| = |A_1| + |A_2| + \cdots + |A_k|.\]

In counting terms: when every outcome falls into exactly one of several cases, count each case and add. “Mutually disjoint” is the condition of a partition (equivalence-classes-and-partitions): no outcome is in two cases. “Union is \(A\)” means no outcome is left out.

  • One number from \(\{1, \dots, 8\}\) that is prime or composite. The primes \(\{2, 3, 5, 7\}\) and the composites \(\{4, 6, 8\}\) are disjoint, because no number is both, so there are \(4 + 3 = 7\).
  • Number plates of four, five or six symbols. Every plate has exactly one length, so the counts for the three lengths add (2026-10-12-introduction-to-counting).
  • The symbols themselves. 26 letters and 10 digits make \(26 + 10 = 36\) symbols, since no symbol is both.

The cases must not overlap. Count the permutations of \(\{1, \dots, 60\}\) with at least one even number in the first two positions as “first is even” plus “second is even”, and the permutations whose first two numbers are both even are counted twice.

When the sets do overlap, the sum can be corrected rather than abandoned. Adding \(|A|\) and \(|B|\) counts each element of \(A \cap B\) twice, so subtracting it once gives

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

which is the addition rule when \(A \cap B = \emptyset\). For the permutations, in multiples of \(58!\), that is \(1770 + 1770 - 870 = 2670\), the right answer. This is inclusion/exclusion, which extends to three or more sets in inclusion-exclusion.

Figure 2: Why the addition rule needs disjoint cases. Each cell counts the permutations of \({1, \dots, 60}\) whose first two numbers have the given parities, as a multiple of \(58!\). The blue band, first number even, and the orange band, second number even, overlap in the cell EE. Adding the two bands counts EE twice and gets \(3540\), every permutation, although the 870 in OO have no even number in front. Disjoint cases, EE, EO and OE, give the right answer, \(2670\).

When to add and when to multiply

Multiply Add
Shape One outcome is built in steps, and every outcome makes one choice at every step. The outcomes split into cases, and every outcome is in exactly one case.
Signals “followed by”, “then”, “one from each”, positions in an arrangement an “or” between alternatives that exclude each other; “of length 4, 5 or 6”
Check Is the number of options at each step the same whatever came before? Do the cases overlap? Do they cover everything?
Example one odd and one even from \(1, \dots, 9\): \(5 \times 4 = 20\) one number from \(\{1, \dots, 8\}\) that is prime or composite: \(4 + 3 = 7\)

Most problems use both: multiply within each case, add across the cases. The plates with exactly one digit are an example. Within a length, choose the digit’s position, then the digit, then the letters, and multiply. Across the three lengths, add.

Splitting into cases

The multiplication rule fails when the number of options at a step depends on what was chosen earlier. The fix is to split on that earlier choice, so that inside each case the counts are fixed.

  1. Find the step whose count varies, and the earlier choice it depends on.
  2. Split the outcomes into cases according to that choice. The cases must be disjoint and cover everything.
  3. Apply the multiplication rule inside each case.
  4. Add the cases.

Worked: a prime followed by an odd number. Permutations of \(\{1, \dots, 7\}\). The primes are \(2, 3, 5, 7\) and the odd numbers \(1, 3, 5, 7\). The number of odd numbers left for position 2 depends on whether the prime in position 1 was odd.

  • First number 2: \(1 \times 4 \times 5!\), since all four odd numbers remain.
  • First number 3, 5 or 7: \(3 \times 3 \times 5!\), since the first number used up an odd number.

Total \((4 + 9) \times 5! = 1560\). Multiplying straight through, \(4 \times 4 \times 5! = 1920\), overcounts.

Worked: an even number followed by a multiple of 3. Permutations of \(\{1, \dots, 60\}\). There are 30 even numbers and 20 multiples of 3, and 10 of the even numbers, the multiples of 6, are also multiples of 3.

  • First number a multiple of 6: \(10 \times 19 \times 58!\), since it used up a multiple of 3.
  • First number even but not a multiple of 3: \(20 \times 20 \times 58!\).

Total \((190 + 400) \times 58! = 590 \times 58!\) (2026-10-12-introduction-to-counting).

In both, the split comes from an overlap. A first choice that also belongs to the set the second choice is drawn from uses up one of its options, so it goes in one case, and a first choice outside that set goes in the other.

Counting the complement

If \(A\) is a finite set and \(B \subseteq A\), then \[|A - B| = |A| - |B|.\]

This is the addition rule turned round. \(A\) is the union of the disjoint sets \(B\) and \(A - B\), so \(|A| = |B| + |A - B|\). It is sometimes called the difference rule.

To count the outcomes with some property, count all outcomes and subtract those without it. It pays off whenever the unwanted outcomes are simpler than the wanted ones, which is typical of “at least one”: the opposite of “at least one” is “none”, a single case.

  • Prime or composite from \(\{1, \dots, 8\}\). Only 1 is neither: \(|X - \{1\}| = 8 - 1 = 7\).
  • At least one even number in the first two positions of a permutation of \(\{1, \dots, 60\}\). The opposite is “both odd”: \(60! - 30 \times 29 \times 58! = 2670 \times 58!\). Counting EE, EO and OE separately gives the same, with three cases instead of one.
  • Number plates with at least one repeated symbol. The opposite is “no repeats”, so subtract the plates with no repeats from all plates: \(2\,238\,928\,128 - 1\,449\,063\,000 = 789\,865\,128\).

Subtract inside the same universe. \(B\) has to be a subset of \(A\), counted under the same conditions. For the plates, both counts use lengths 4, 5 and 6 and the same 36 symbols. Subtracting the no-repeat four-symbol plates from all plates of every length would be meaningless.

Permutations

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

Theorem. 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!.\]

Why. Fill the positions in turn. The first can hold any of the \(n\) objects. Whatever went there, \(n - 1\) objects remain for the second, then \(n - 2\) for the third, and so on until 1 object remains for the last position. Every step’s count is independent of what was chosen, so the multiplication rule gives \(n!\).

\(n!\) is “\(n\) factorial”, also read “\(n\) bang”:

\[n! = \prod_{i=1}^{n} i \quad\text{for } n \in \mathbb{Z}^{+}, \qquad 0! = 1.\]

\(0! = 1\) is a definition, and it is the one that makes \(n! = n \times (n-1)!\) true at \(n = 1\) (recursive-definitions). The values grow faster than any power: \(5! = 120\), \(6! = 720\), \(10! = 3\,628\,800\), and \(58!\) has 79 digits. Answers to permutation problems are usually left in factorial form for that reason.

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

A bijection \(f\) from \(\{1, \dots, n\}\) to itself is the same thing as the arrangement \(f(1), f(2), \dots, f(n)\), so the symmetric group \(S_n\) has \(n!\) elements (symmetric-group).

Restricted positions: fill them first

When some positions have conditions on them and the rest are free, choose for the restricted positions first. Each later position then has one fewer object than the last, whatever was chosen, and the \(n - k\) free positions are an arrangement of the \(n - k\) objects left: \((n - k)!\) ways.

Permutations of that Count
\(\{1, \dots, 5\}\) start with an even number \(2 \times 4! = 48\)
\(\{1, \dots, 7\}\) start with a prime \(4 \times 6! = 2880\)
\(\{1, \dots, 7\}\) start with a prime followed by a composite \(4 \times 2 \times 5! = 960\)
\(\{1, \dots, 15\}\) start with an odd number \(8 \times 14!\)

The last line is Q3(a) of practice-problems: \(\{1, \dots, 15\}\) has 8 odd numbers.

Why the restricted position goes first. Filling a free position first makes the count for the restricted one depend on what was used. In “starts with an even number”, if position 2 were filled first, position 1 would have 2 options or only 1, depending on whether position 2 took an even number. Filling position 1 first keeps every count fixed. The second row of the table, \(4 \times 6!\), also shows the most common slip: \(4 \times 6\) forgets that the remaining positions have to be filled too.

\(r\)-permutations

An \(r\)-permutation of a set of \(n\) elements is an ordered selection of \(r\) of the elements, with no element used more than once.

The number of \(r\)-permutations of a set of \(n\) elements, for \(0 \leq r \leq n\), is \[n \times (n-1) \times \cdots \times (n - r + 1) = \frac{n!}{(n-r)!}.\]

Why. It is the permutation count stopped after \(r\) positions. The first position has \(n\) options, the second \(n - 1\), and the \(r\)th has \(n - r + 1\), so there are \(r\) factors. Multiplying top and bottom by the missing factors \((n - r) \times \cdots \times 1 = (n - r)!\) gives the fraction. With \(r = n\) it is \(\frac{n!}{0!} = n!\), the permutations of the whole set, which is one place \(0! = 1\) is needed.

If repetition is allowed, every position has all \(n\) options and the count is \(n^r\). Which of the two applies is the first thing to settle.

Worked: a four-symbol plate. The symbols are the 26 letters and 10 digits, 36 in all.

Figure 3: A four-symbol plate filled one position at a time, from 36 symbols. With repetition allowed, every position has all 36 symbols available, giving \(36^4\). Without repetition, each symbol placed is unavailable afterwards, so each position has one option fewer than the one before. That is a 4-permutation of the 36 symbols, \(36 \times 35 \times 34 \times 33 = \frac{36!}{32!}\).

Over all three lengths these give \(36^4 + 36^5 + 36^6\) plates with repetition and \(\frac{36!}{32!} + \frac{36!}{31!} + \frac{36!}{30!}\) without (2026-10-12-introduction-to-counting). Unordered selections, where only which elements are chosen matters, are counted in counting-selections.

Common mistakes

  • Adding steps, or multiplying cases. One prime and one composite is \(4 \times 3 = 12\). One number that is prime or composite is \(4 + 3 = 7\). Getting these the wrong way round gives 7 and 12, swapped.
  • Multiplying when a count depends on an earlier choice. “A prime followed by an odd number” is not \(4 \times 4 \times 5!\). After an odd prime only three odd numbers are left. Split into cases.
  • Treating an unordered choice as ordered. Choosing one odd and one even number from \(1, \dots, 9\) is 20 ways. Counting “first pick, second pick” gives \(5 \times 4 + 4 \times 5 = 40\), each pair twice.
  • Cases that overlap or leave something out. “First is even” plus “second is even” counts the EE permutations twice. Check that each outcome is in exactly one case.
  • Forgetting the free positions. Permutations of \(\{1, \dots, 7\}\) starting with a prime are \(4 \times 6!\), not \(4 \times 6\). The other six positions still have to be arranged.
  • Mixing up \(n^r\) and \(\frac{n!}{(n-r)!}\). The first allows repeats, the second doesn’t. Read the question for which.
  • Subtracting across different universes. The complement has to be counted under the same conditions as the total.
  • Counting 1 as a prime or a composite. It is neither, and several of the questions above turn on it.

See also