5.1.2 Counting | SigmaField

The multiplication rule

When a choice is made in steps, multiply the number of ways at each step. A café offers 3 drinks and 4 cakes. Each drink goes with each cake, so there are $3 \times 4 = 12$ orders.

Lesson 5.1.1's two dice work the same way: 6 faces for the red die, then 6 for the blue, $6 \times 6 = 36$ outcomes. A 4-digit PIN has $10 \times 10 \times 10 \times 10 = 10{,}000$ possibilities.

Rule: Multiplication rule

m \times n

A first step can go $m$ ways. If a second step can then go $n$ ways, whatever the first was, the two together can go $m \times n$ ways. More steps multiply on.

The options at the second step may depend on the first, but their number must not. Four runners race for gold and silver. Whoever wins gold, 3 runners are left for silver, so there are $4 \times 3 = 12$ results.

10^4

from itertools import permutations, product orders = list(product(["tea", "coffee", "juice"], ["scone", "tart", "bun", "cake"])) print(len(orders), orders[:2]) print(10**4) medals = list(permutations("ABCD", 2)) print(len(medals), medals[:4])

⌘/Ctrl + Enter runs the cell

Order matters: arrangements

Put 4 books on a shelf. The first place has 4 choices, the second 3, the third 2 and the last 1: $4 \times 3 \times 2 \times 1 = 24$ orders. This product is written $4!$ , read "4 factorial". In general $n! = n \times (n - 1) \times \cdots \times 1$ counts the orders of $n$ different things.

Factorials grow fast. $10! = 3{,}628{,}800$ , and a deck of 52 cards can be shuffled into $52! \approx 8.07 \times 10^{67}$ orders. By agreement $0! = 1$ : there is one way to arrange nothing.

Often only some of the $n$ things are placed. A club of 10 chooses a chair, a secretary and a treasurer, three different people: $10 \times 9 \times 8 = 720$ ways. That is $10!$ with the last $7!$ cancelled, $\frac{10!}{7!}$ .

Rule: Ordered choices

\begin{gathered} n(n - 1)\cdots(n - k + 1) = \frac{n!}{(n - k)!} \\ n^k \text{ if repeats are allowed} \end{gathered}

The number of ordered lists of $k$ things from $n$ , each used at most once: a permutation of $k$ from $n$ , math.perm(n, k). If a thing may be used again, as a digit in a PIN, each place has all $n$ choices.

From the 5 letters A to E, 3-letter codes number $5^3 = 125$ when letters may repeat, and $5 \times 4 \times 3 = 60$ when they may not. Repeats allowed is also called drawing with replacement: the letter goes back before the next draw.

Try it math.factorial and math.perm give the counts above. Listing all the codes with product and permutations confirms 125 and 60.

import math from itertools import permutations, product print(math.factorial(4), math.factorial(10), math.factorial(0)) print(f"{math.factorial(52):.3e}") print(math.perm(10, 3), math.factorial(10) // math.factorial(7)) print(len(list(product("ABCDE", repeat=3))), len(list(permutations("ABCDE", 3))))

⌘/Ctrl + Enter runs the cell

Order does not matter: combinations

Now the club picks a committee of 3, with no roles. The 720 ordered choices count each committee several times: once for each way to hand out the three roles, $3! = 6$ ways. So there are $720 \div 6 = 120$ committees.

The picture shows the same idea with 4 runners and 2 medals. There are 12 orders, and each pair of medal winners appears twice.

Gold has 4 ways and silver 3, so $4 \times 3 = 12$ orders. As pairs, $\{A, B\}$ comes from "A then B" and from "B then A", so there are $12 \div 2 = 6$ pairs.

Rule: Combinations

\binom{n}{k} = \frac{n!}{k!\,(n - k)!}

The number of ways to choose $k$ things from $n$ when order does not matter: the subsets of size $k$ . Read " $n$ choose $k$ ", also written $C(n, k)$ ; math.comb(n, k). It is the ordered count divided by the $k!$ orders of each choice.

Four cases are worth knowing.

Nothing or everything. $\binom{n}{0} = \binom{n}{n} = 1$ : one way to choose no one, one way to choose everyone.
Choosing who stays out. $\binom{n}{k} = \binom{n}{n - k}$ . Picking 3 of 10 to serve is picking 7 to stay home: both give 120.
Too many. If $k > n$ there is no way, and $\binom{n}{k} = 0$ .
All sizes together. For $n = 5$ , the counts for $k = 0, \ldots, 5$ are 1, 5, 10, 10, 5, 1. They add up to $32 = 2^5$ , every subset, since each of the 5 things is either in or out.

Lesson 5.2.2 uses these numbers for the binomial distribution.

n = 5

import math from itertools import combinations pairs = list(combinations("ABCDE", 2)) print(len(pairs), pairs[:4]) print(math.comb(10, 3), math.perm(10, 3) // math.factorial(3), math.comb(10, 7)) row = [math.comb(5, k) for k in range(6)] print(row, sum(row), math.comb(4, 5))

⌘/Ctrl + Enter runs the cell

Probabilities by counting

With equally likely outcomes, $P(A) = \frac{|A|}{|\Omega|}$ (lesson 5.1.1), and both counts come from the rules above. Count the event and the sample space the same way: both ordered, or both unordered.

Six rolls of a die. The $6^6 = 46{,}656$ ordered sequences of faces are equally likely. Of them, $5^6 = 15{,}625$ contain no six. So $P(\text{at least one six}) = 1 - \frac{15{,}625}{46{,}656} \approx 0.6651$ , not the $6 \times \frac{1}{6} = 1$ that adding gives.

Cards. A standard deck has 52 cards: 13 ranks (2 to 10, jack, queen, king, ace) in each of 4 suits (hearts, diamonds, clubs, spades). A 5-card hand from a well-shuffled deck is one of $\binom{52}{5} = 2{,}598{,}960$ equally likely hands.

All hearts: $\binom{13}{5} = 1287$ hands, so $P \approx 0.000495$ . Five cards of any one suit: $4 \times 1287 = 5148$ hands, $P \approx 0.00198$ .
Exactly two aces: choose the 2 aces from 4, $\binom{4}{2} = 6$ ways, then the other 3 cards from the 48 that are not aces, $\binom{48}{3} = 17{,}296$ . The multiplication rule gives $103{,}776$ hands, $P \approx 0.0399$ .
At least one ace: the complement, no ace, has $\binom{48}{5}$ hands, so $P = 1 - 0.6588 = 0.3412$ .

A committee. A club of 10 has 6 juniors and 4 seniors, and a committee of 3 is picked at random from the 120. All juniors: $\binom{6}{3} = 20$ committees, so $P = \frac{1}{6}$ . Exactly two juniors: $\binom{6}{2}\binom{4}{1} = 15 \times 4 = 60$ , so $P = \frac{1}{2}$ .

Counting in order gives the same answer if the top is ordered too. Three juniors one after another: $\frac{6 \times 5 \times 4}{10 \times 9 \times 8} = \frac{120}{720} = \frac{1}{6}$ .

Try it The cell works out each probability above. Fraction gives the committee answers exactly.

import math from fractions import Fraction print(round(1 - 5**6 / 6**6, 4)) hands = math.comb(52, 5) print(hands, round(math.comb(13, 5) / hands, 6), round(4 * math.comb(13, 5) / hands, 5)) two_aces = math.comb(4, 2) * math.comb(48, 3) print(two_aces, round(two_aces / hands, 4), round(1 - math.comb(48, 5) / hands, 4)) print(Fraction(math.comb(6, 3), math.comb(10, 3)), Fraction(math.comb(6, 2) * 4, 120)) print(Fraction(6 * 5 * 4, 10 * 9 * 8))

⌘/Ctrl + Enter runs the cell

A lottery

A lottery draws 6 different numbers from 1 to 49, and a ticket picks 6. There are $\binom{49}{6} = 13{,}983{,}816$ equally likely draws, so the jackpot has probability about $7.15 \times 10^{-8}$ .

To match exactly 3 of your numbers, the draw takes 3 of your 6, in $\binom{6}{3} = 20$ ways. Its other 3 come from the 43 numbers you did not pick, in $\binom{43}{3} = 12{,}341$ ways. That is $246{,}820$ draws, a probability of about 0.01765. Every number of matches works the same way:

matches $k$	0	1	2	3	4	5	6
draws $\binom{6}{k}\binom{43}{6 - k}$	6,096,454	5,775,588	1,851,150	246,820	13,545	258	1
probability	0.436	0.413	0.1324	0.01765	0.0009686	$1.845 \times 10^{-5}$	$7.151 \times 10^{-8}$

The draws add up to all 13,983,816, so the probabilities add up to 1. At least 3 matches has probability about 0.01864.

The same pattern answers every question of this kind. Draw $n$ things from $N$ , of which $K$ are special. Exactly $k$ special ones turn up in $\binom{K}{k}\binom{N - K}{n - k}$ of the $\binom{N}{n}$ equally likely draws.

For two aces in a hand, $N = 52$ , $K = 4$ , $n = 5$ and $k = 2$ .

Try it The loop builds the table and checks the total. The rest simulates, with fixed seeds: 100,000 shuffled decks, keeping the first 5 cards, and 100,000 lottery draws. rng.random((n, 52)).argsort(axis=1) puts the 52 cards in a random order in each row. Cards 0 to 3 stand for the aces, and numbers 0 to 5 for your ticket.

import math import numpy as np total = math.comb(49, 6) for k in range(7): ways = math.comb(6, k) * math.comb(43, 6 - k) print(k, ways, f"{ways / total:.4g}") print(sum(math.comb(6, k) * math.comb(43, 6 - k) for k in range(7)) == total) print(round(sum(math.comb(6, k) * math.comb(43, 6 - k) for k in range(3, 7)) / total, 5)) hands = np.random.default_rng(2).random((100_000, 52)).argsort(axis=1)[:, :5] aces = (hands < 4).sum(axis=1) print(round((aces == 2).mean(), 4), round((aces >= 1).mean(), 4)) draws = np.random.default_rng(3).random((100_000, 49)).argsort(axis=1)[:, :6] matches = (draws < 6).sum(axis=1) print(round((matches == 3).mean(), 4)) p = math.comb(4, 2) * math.comb(48, 3) / math.comb(52, 5) print(round(math.sqrt(p * (1 - p) / 100_000), 4))

⌘/Ctrl + Enter runs the cell

In this seeded run, 0.0389 of the hands had exactly two aces, against the exact 0.0399, and 0.3402 had at least one, against 0.3412. Case study 4.7.5's standard error, $\sqrt{p(1 - p)/N}$ , is 0.0006 here: the size of a typical miss. The lottery run gives 0.0181 for exactly 3 matches, against 0.01765.

Which count to use

Two questions decide: does the order matter, and can a thing be chosen twice? Swap two of your choices: if the result changes, order matters.

example	order matters?	repeats?	count
a PIN, dice rolled in turn	yes	yes	$n^k$
medals, officers, a shelf	yes	no	$\frac{n!}{(n - k)!}$
a committee, a card hand, a lottery draw	no	no	$\binom{n}{k}$

An urn holds 3 red and 2 blue balls; draw 2. Without replacement, the 2 balls form one of $\binom{5}{2} = 10$ pairs, and $\binom{3}{2} = 3$ are both red: $P = \frac{3}{10}$ . With replacement, the 25 ordered draws are equally likely and 9 are red twice: $P = \frac{9}{25} = 0.36$ .

Lesson 5.1.3 gets both answers from conditional probabilities.

Common mistakes

Order or not. A committee of 3 from 10 has 120 choices; three officers have 720. Ask whether swapping two choices gives a different result.
Count the top and the bottom the same way. An ordered count of the event over an unordered count of the sample space is wrong by a factor $k!$ .
"Exactly" means the rest are not of that kind. For exactly two aces the other 3 cards come from the 48 non-aces. Taking them from the 50 cards left gives 0.0452, counting hands with 3 or 4 aces.
"At least one" by adding counts twice. Two-card hands with an ace number $\binom{52}{2} - \binom{48}{2} = 198$ , not $4 \times 51 = 204$ , which counts the 6 hands with two aces twice.
Unordered choices with repeats are not equally likely. Like the sums of two dice, count the ordered draws instead.
Big factorials in NumPy overflow. Python's integers are exact, so math.factorial(21) is right. NumPy's np.prod(np.arange(1, 22, dtype=np.int64)) silently gives a negative number, because its 64-bit integers stop near $9.2 \times 10^{18}$ .

21!

import math import numpy as np hands = math.comb(52, 5) print(round(math.comb(4, 2) * math.comb(48, 3) / hands, 4), round(math.comb(4, 2) * math.comb(50, 3) / hands, 4)) print(math.comb(52, 2) - math.comb(48, 2), 4 * 51) print(math.factorial(21), np.prod(np.arange(1, 22, dtype=np.int64)), f"{np.iinfo(np.int64).max:.2e}")

⌘/Ctrl + Enter runs the cell

Counting

0 of 12 correct

1.
A café has 4 drinks and 5 cakes. How many drink-and-cake orders are there?
2.
How many 3-letter codes can be made from 26 letters if letters may repeat?
3.
In how many orders can 5 different books stand on a shelf?
4.
Eight runners race. In how many ways can gold, silver and bronze be given?
5.
In how many ways can a committee of 3 be chosen from 8 people?
6.
Find $\binom{20}{18}$
7.
A die is rolled 3 times. Find the probability of at least one six
8.
Two cards are dealt from a shuffled deck. Find the probability that both are aces
9.
A club of 6 juniors and 4 seniors picks a committee of 3 at random. Find the probability that all three are seniors
10.
In the 6-from-49 lottery, how many draws match exactly 5 of your 6 numbers?
11.
An urn has 3 red and 2 blue balls. Two are drawn with replacement. Find the probability that both are blue
12.
How many 2-card hands from a 52-card deck contain at least one ace?

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

m

Counting

The multiplication rule

Rule: Multiplication rule

Order matters: arrangements

Rule: Ordered choices

Order does not matter: combinations

Rule: Combinations

Probabilities by counting

A lottery

Which count to use

Common mistakes

Counting

Summary card

Free further reading