The Lumenary · Grades 6–8

Counting principles

Name: ______________________

Date: ______________________

You will learn to

Apply the addition and multiplication principles to count outcomes, and explain why each works
Count arrangements of $n$ objects ( $n!$ ) and ordered selections of $k$ objects from $n$ ( $\tfrac{n!}{(n-k)!}$ )
Use complementary counting, for example to count passwords containing at least one digit
Correct for overlapping cases with $|A \cup B| = |A| + |B| - |A \cap B|$

1.
Kofi has $4$ shirts, $3$ pairs of trousers and $2$ pairs of shoes. An outfit is one shirt, one pair of trousers and one pair of shoes. How many different outfits can he make?
2.
A school library in Quito has $12$ novels and $8$ comics on a display shelf. Ana may borrow one book from the shelf. In how many ways can she choose?
- A. $20$
- B. $96$
- C. $12$
- D. $4$
3.
In how many different orders can $6$ different books be arranged on a shelf?
4.
Ten swimmers race in a final. In how many ways can the gold, silver and bronze medals be awarded? (No ties.)
5.
How many 4-digit PINs (from $0000$ to $9999$ ) contain at least one repeated digit?
6.
How many of the whole numbers from $1$ to $100$ are divisible by $3$ or by $5$ (or both)?
7.
Which of these are good reasons for defining $0! = 1$ ? (Choose all that apply.)
- A.There is exactly one way to arrange no objects: the empty arrangement
- B.It makes $P(n, n) = \tfrac{n!}{(n - n)!} = n!$ true
- C.It keeps the rule $n! = n \times (n - 1)!$ true for $n = 1$
- D.Because zero times anything is zero
8.
A code has $3$ symbols, each a capital letter ( $26$ choices) or a digit ( $10$ choices). How many codes contain at least one letter and at least one digit?
9.
In the Lean file, perm n k is $P(n, k)$ and fact n is $n!$ . Which statement correctly formalises $P(n, k) = \tfrac{n!}{(n - k)!}$ ?
- A.∀ n k : Nat, k ≤ n → perm n k * fact (n - k) = fact n
- B.∀ n k : Nat, perm n k * fact (n - k) = fact n
- C.∀ n k : Nat, k ≤ n → perm n k = fact n / fact k
- D.∀ n k : Nat, k ≤ n → perm n k = fact n * fact (n - k)
10.
Write a recursive function arrangements(items) that returns a list of all orderings of the list items (each ordering a list), without using itertools. Idea: for each item, put it first and follow it by every arrangement of the remaining items. Then check that $4$ items give $4! = 24$ different arrangements.
Computational — Practice

Answer key — Counting principles

1.
By the multiplication principle, $4 \times 3 \times 2 = 24$ outfits.
2.
One choice from two disjoint groups: by the addition principle there are $12 + 8 = 20$ ways.
3.
$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ (Theorem 4).
4.
$10$ choices for gold, then $9$ for silver, then $8$ for bronze: $10 \times 9 \times 8 = 720 = \tfrac{10!}{7!}$ .
5.
All PINs: $10^4 = 10\,000$ . No repeated digit: $10 \times 9 \times 8 \times 7 = 5040$ . So at least one repeat: $10\,000 - 5040 = 4960$ (complementary counting).
6.
$33$ multiples of $3$ , $20$ multiples of $5$ , $6$ multiples of $15$ (counted in both). By the overlap rule, $33 + 20 - 6 = 47$ .
7.
All of the first three: $0! = 1$ counts the one empty arrangement, keeps $n! = n \times (n-1)!$ working at $n = 1$ , and makes $P(n, n) = n!$ . The product of no numbers at all is $1$ , just as the sum of no numbers is $0$ .
8.
All codes: $36^3 = 46\,656$ . The codes that break the rule are all letters ( $26^3 = 17\,576$ ) or all digits ( $10^3 = 1000$ ), and no code is both. So $46\,656 - 17\,576 - 1000 = 28\,080$ .
9.
∀ n k : Nat, k ≤ n → perm n k * fact (n - k) = fact n. Without k ≤ n it is false (for $k > n$ the left side is $0$ ), and the other two have the wrong formula.
10.
```
def arrangements(items):
    if not items:
        return [[]]
    result = []
    for i in range(len(items)):
        first = items[i]
        rest = items[:i] + items[i + 1:]
        for r in arrangements(rest):
            result.append([first] + r)
    return result
```
This is the proof of Theorem 4 as a program: $n$ choices for the first item, each followed by all $(n - 1)!$ arrangements of the rest, giving $n \times (n-1)! = n!$ . (The Lean file builds arrangements the other way round, inserting the first item into every position; both give $n!$ .)