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.
Try it
- Three stages with 3, 2 and 2 options. Different outfits reads 12, which is 3 × 2 × 2.
- Press 4 under Shirts to choose from. The last column grows to 16, not 13.
- Press Trace one outfit. One path lights up from the root to one leaf.
- Press Remove a stage. The tree loses a column and the total divides.
- Press Add a stage to bring it back. Three stages is the most the tree draws.
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.
Try it
- Items to choose from, n is 4 and Items chosen, k is 2. The list shows all 6 choices.
- Press Order matters. Each choice fans into 2 orders and the list grows to 12.
- Compare Combinations C(n, k), Orders per choice, k! and Permutations P(n, k). The first two multiply to the third.
- Press 8 for n and 4 for k. The list is cut at 120 rows but the counts stay exact.
- Lower n and the k buttons past it disappear. You cannot choose more items than you have.