Chapter 14 · Advanced Concepts
Counting
Multiplying choices, and telling permutations from combinations.
14.1 The multiplication rule
Pick a shirt, then trousers, then shoes. If the choices do not constrain each other, the number of complete outfits is the product of the choices,
\[n_1 \times n_2 \times \cdots \times n_k.\]
The tree shows why. Adding a stage with \(n\) options does not add \(n\) paths. It replaces every path that already existed with \(n\) copies of itself. Three shirts and two pairs of trousers give six half-outfits, and two pairs of shoes turn each of those into two, so twelve. Change a count and watch the last column grow by a factor, never by an amount. Most counting problems are this rule applied carefully, and the harder ones only look different because the stages are less obvious.
Reading: this section is beyond the OpenStax text. See any discrete mathematics introduction on the multiplication principle.
14.2 Permutations and combinations
Choosing three people for a committee is not the same as choosing three for first, second and third place. A permutation counts arrangements, where the order is part of the answer. A combination counts selections, where it is not.
\[P(n, k) = \frac{n!}{(n-k)!}, \qquad C(n, k) = \frac{n!}{k!\,(n-k)!}.\]
The two differ by exactly \(k!\), the number of orders any one selection can be written in. Press “Order matters” and every row in the list fans out into \(k!\) rows, which is that division running backwards. The list is real. Count the rows and you get the formula's answer, until it grows too long to print.
Reading: this section is beyond the OpenStax text. See any discrete mathematics introduction on permutations and combinations.