COMP233 · Chapter 9 Interactive Companion

Counting & Probability

Sample spaces and equally likely probability, counting the elements of a list, possibility trees, the multiplication rule, and permutations. Sections 9.1–9.2.
Back to COMP233

About these sections

Almost every probability question reduces to one skill: counting carefully. If every outcome is equally likely, the probability of an event is just how many outcomes you want over how many there are — so the real work is the counting, and that is what these two sections build, from the ground up.

The thread. Section 9.1 sets the language — a sample space of outcomes, an event as a subset, the equally-likely probability formula and its basic laws — plus the simplest counting fact, how many integers lie in a range. Section 9.2 gives the two engines of counting: the multiplication rule (drawn as a possibility tree) and permutations for ordered arrangements.

Section 9.1The basics of counting & probability

Definitions · sample space, event, probability
A random process has a sample space S = the set of all possible outcomes. An event E is any subset E ⊆ S. When the outcomes are equally likely,
P(E) = N(E) / N(S) = (outcomes in E) / (all outcomes).

Four consequences are worth holding onto — they catch most mistakes before they happen:

RANGE0 ≤ P(E) ≤ 1 always — an event has between none and all of the outcomes.
CERTAIN / IMPOSSIBLEP(S) = 1 (something happens), P(∅) = 0 (nothing can).
COMPLEMENTP(not E) = 1 − P(E) — often far easier to count the opposite.
DISJOINT ADDIf E, F can’t both happen, P(E or F) = P(E) + P(F).
The formula needs equally likely outcomes
“Sum of two dice” is not equally likely — a 7 is six times as common as a 2. To use N(E)/N(S) you must count the equally-likely pairs (all 36), not the 11 sums. The 9.1.2 grid shows exactly why.
Counting a list (Theorem 9.1.1)
The number of integers from m through n inclusive is n − m + 1. The “+1” is the off-by-one guard: from 5 through 12 there are 12 − 5 + 1 = 8 numbers, not 7.

9.1.1 Equally-likely probability calculator

Enter favourable outcomes N(E) and the total N(S). The tool reduces the fraction, gives the decimal and percentage, and the complement probability P(not E) = 1 − P(E).

9.1.2 Two-dice explorer — why we count the grid

Two fair dice give 36 equally-likely outcomes, the cells of this grid (row = first die, column = second). Choose an event and the tool highlights and counts the favourable cells, then computes the probability. The sums are not equally likely — but the 36 pairs are, which is the whole point.

9.1.3 Counting a list — the n − m + 1 rule

How many integers from m through n, and how many are multiples of k? The multiples count is a favourite building block (“how many three-digit numbers are divisible by 7?”): it equals ⌊n/k⌋ − ⌊(m−1)/k⌋.

Practice exercises · Section 9.1

Epp, 4th ed. §9.1: recommended 2, 3, 8, 9, 12, 13, 15. Try each on paper first.
Exercise 9.1 A
Two fair dice are rolled. Find P(sum = 7), P(sum = 11), and P(sum = 7 or 11).
N(S) = 36. Sum 7: (1,6),(2,5),(3,4),(4,3),(5,2),(6,1) = 6, so P = 6/36 = 1/6. Sum 11: (5,6),(6,5) = 2, P = 1/18. Disjoint, so add: 6/36 + 2/36 = 8/36 = 2/9.
Exercise 9.1 B
How many integers from 100 through 999 are there, and how many are divisible by 5? What is the probability a random three-digit number is divisible by 5?
List: 999 − 100 + 1 = 900. Divisible by 5: ⌊999/5⌋ − ⌊99/5⌋ = 199 − 19 = 180. Probability = 180/900 = 1/5. (Check: multiples run 100,105,…,995 = (995−100)/5 + 1 = 180.)

Section 9.2Possibility trees and the multiplication rule

The multiplication rule (Theorem 9.2.1)
If an operation is a sequence of k steps, with step 1 done in n₁ ways, step 2 in n₂ ways (whatever step 1 was), …, step k in nₖ ways, the whole operation can be done in
n₁ · n₂ · … · nₖ ways.

The possibility tree is the picture: step 1 fans into n₁ branches, each into n₂, and so on; the leaves are the outcomes, n₁ · n₂ · … of them. The one condition to check: the number of choices at each step must not depend on the earlier choices (the choices themselves may differ).

With repetition vs without — the decision you make first
A 3-letter code from 26 letters with repetition: 26 · 26 · 26 = 26³. Without repetition (no letter reused): each step loses one option, 26 · 25 · 24 — a permutation P(26, 3). Deciding which model the problem wants is half the battle.

9.2.1 Possibility-tree visualiser

Enter the stages of a process: separate stages with ; and options with ,. The tool draws the tree with each branch labelled and every outcome written at its leaf, and counts the leaves — the multiplication rule in action. Try H,T ; H,T ; H,T for three coin flips.

9.2.2 Multiplication-rule calculator

Enter the number of choices at each step as a comma list, e.g. 26, 26, 10, 10 for two letters then two digits. The tool draws the product as boxes and keeps the result exact.
Definition · permutations (Theorem 9.2.2–9.2.3)
A permutation is an ordered arrangement. The number of ways to order all n distinct objects is n! (“n factorial” = n · (n−1) · … · 1, with 0! = 1). The number of ordered arrangements of r objects chosen from n is the r-permutation
P(n, r) = n! / (n − r)! = n · (n−1) · … · (n − r + 1)  (r falling factors).

The product form is the multiplication rule: n ways to fill the first position, n−1 for the second (one is used up), down to n−r+1 for the r-th. Order matters, repetition is not allowed — that is what “permutation” means. The 9.2.4 slots picture makes the falling product visible.

9.2.3 Permutation calculator

Enter n and r. The tool computes P(n, r) as n!/(n−r)! and as the falling product, and for contrast the with-repetition count nᵇ. Set r = n to get the full ordering n!.

9.2.4 Permutation slots — watch the choices fall

This draws the r positions as boxes. The first box has n choices, the next n−1 (one object is now used), and so on — the falling product n · (n−1) · … you multiply to get P(n, r). Compare it with the with-repetition row, where every box keeps all n choices.

9.2.5 Strings & PINs — choosing the right model

Count strings of a given length over an alphabet of a given size, under both models. With repetition a symbol may reappear (sizeᵇ); without repetition none repeats (P(size, length)). The gap between them is the cost of forbidding repeats.

Practice exercises · Section 9.2

Epp, 4th ed. §9.2: recommended 3, 4, 9, 10, 13, 16, 19, 22. More in Taught solutions.
Exercise 9.2 A
A password is 2 letters (A–Z) then 3 digits (0–9). How many if repetition is allowed? How many if no character repeats?
With repetition: 26 · 26 · 10 · 10 · 10 = 676,000. No repeats (letters distinct, digits distinct): (26 · 25) · (10 · 9 · 8) = 650 · 720 = 468,000.
Exercise 9.2 B
In how many ways can 6 people line up? In how many ways can a president and a vice-president be chosen from the 6?
Line up: 6! = 720. President + VP: ordered, no repeat: P(6,2) = 6 · 5 = 30.

WorkedTaught solutions to recommended exercises

A selection from Epp’s recommended problems (4th ed.), solved in the style used in lecture. Attempt each on paper first.
§9.1 · a card draw
One card is drawn from a 52-card deck. Find P(king), P(heart), P(face card).
N(S)=52. (a) 4 kings: 4/52 = 1/13. (b) 13 hearts: 13/52 = 1/4. (c) face cards 3×4 = 12: 12/52 = 3/13.
§9.1 · counting a sublist
How many integers from 1 through 1000 are multiples of 6? Of both 6 and 9?
Multiples of 6: ⌊1000/6⌋ = 166. “Both 6 and 9” = multiples of lcm(6,9) = 18: ⌊1000/18⌋ = 55. (Not 54 = 6·9 — the combiner is the lcm.)
§9.2 · multiplication rule
A menu offers 3 starters, 4 mains, 2 desserts. How many three-course meals?
3 · 4 · 2 = 24 meals — the tree fans 3, then 4, then 2, giving 24 leaves. (Paste a,b,c ; a,b,c,d ; a,b into 9.2.1.)
§9.2 · full permutation
How many arrangements of the letters of COMPUTE (7 distinct letters)?
All distinct: 7! = 5040. (Repeated letters, as in LETTER, would divide by each repeat’s factorial — that is §9.5, beyond these sections.)
§9.2 · r-permutation
From 10 runners, how many ways to award gold, silver, bronze (no ties)?
Order matters, no repeats: P(10,3) = 10 · 9 · 8 = 720 = 10!/7!.
§9.2 · with vs without repetition
How many 4-digit PINs? How many have all four digits different?
Any PIN: 10⁴ = 10,000. All different: P(10,4) = 10 · 9 · 8 · 7 = 5040. So P(all different) = 5040/10000 = 0.504.
§9.2 · tree reasoning
A coin is tossed 3 times. How many outcomes, and what is the probability of exactly two heads?
Outcomes: 2 · 2 · 2 = 8 (the tree H,T ; H,T ; H,T). Exactly two heads: HHT, HTH, THH = 3 leaves. P = 3/8. The eight leaves are equally likely, so we just count favourable ones.

HarderChallenge problems — and how to crack them

Tougher problems that reward real understanding. Each solution shows the idea first, then the steps.
Challenge 1 count the complement
How many 4-letter strings over {A–Z} contain at least one vowel (A, E, I, O, U)?
Idea: “at least one” is hard head-on — count the opposite (no vowels) and subtract. Total 26⁴ = 456,976; no-vowel (21 consonants) 21⁴ = 194,481. At least one vowel = 456,976 − 194,481 = 262,495. (Check with 9.2.2 on 26,26,26,26 and 21,21,21,21.)
Challenge 2 a constraint per position
How many 3-digit numbers (100–999) have no repeated digit?
Idea: multiplication rule position by position, honouring “no leading zero” and “no repeat”. Hundreds: 9 (1–9). Tens: 9 (0–9 minus the one used — 0 is back in play). Units: 8. Total 9 · 9 · 8 = 648. The subtlety: the tens box still has 9 options — it loses the hundreds digit but regains 0.
Challenge 3 probability via permutations
Five people sit in a random row. What is the probability that Sara and Omar are next to each other?
Idea: favourable orderings over all orderings. Total 5! = 120. Glue Sara&Omar into one block: 4! arrangements × 2! internal orders = 48. P = 48/120 = 2/5. The “glue the block” trick turns adjacency into a plain permutation.
Challenge 4 all different
Three fair dice are rolled. Probability all three show different faces?
Idea: total with repetition, favourable without. Total 6³ = 216; all different P(6,3) = 6 · 5 · 4 = 120. P = 120/216 = 5/9 ≈ 0.556. Or: 2nd avoids 1st (5/6), 3rd avoids both (4/6) ⇒ 5/9.
Challenge 5 two routes, one answer
From the digits {1,2,3,4,5}, how many 3-digit numbers with distinct digits are even?
Idea: when one position is constrained, fill the constrained position first. Units must be even: 2 choices (2 or 4). Then hundreds: 4 remaining. Then tens: 3 remaining. Total 2 · 4 · 3 = 24. (Filling the unconstrained positions first traps you, because the count of even units left would then vary — always settle the restricted slot first.)

Recap — sections 9.1 and 9.2

  • 9.1 — sample space, event, and for equally-likely outcomes P(E)=N(E)/N(S) with 0 ≤ P ≤ 1, P(not E)=1−P(E). Count a list with n−m+1, multiples with floors. Only use the formula when outcomes really are equally likely.
  • 9.2 — the multiplication rule multiplies the choices at each step (the tree’s leaves). Permutations count ordered, no-repeat arrangements: n! for all, P(n,r)=n!/(n−r)! for r; with repetition it is nᵇ.
  • Three reflexes: count the complement for “at least one”; decide with/without repetition first; fill any constrained position first.
The link forward. When order does not matter, an r-permutation overcounts each group by r! — dividing it out gives the combination C(n,r) = P(n,r)/r! of the next section, for counting unordered selections.