Difficulty: Intermediate | Prerequisites: Basic factorial and permutation notation, modular arithmetic awareness helpful.
Tags: counting, combinatorics, permutations, complementary counting, inclusion-exclusion, binomial coefficient, probability, binomial distribution, sample space, modular arithmetic, Z/pZ, CS 182, Purdue
Counting and probability are the tools you reach for whenever a problem asks "how many?" or "how likely?" They underpin algorithm analysis (how many operations?), cryptography (how many keys?), and randomised algorithms (what is the chance of failure?). This material ties together the counting techniques from combinatorics with the probability fundamentals the course introduces. You should already be comfortable with factorial notation and the idea that order sometimes matters and sometimes does not.
Most exam counting problems reduce to choosing whether order matters, whether repetition is allowed, and whether constraints force you to subtract forbidden cases. Complementary counting (total minus bad) is the single most useful trick. For probability, the key is identifying the sample space, then computing the ratio of favourable outcomes to total outcomes, or applying the binomial distribution where appropriate.
Permutation
An arrangement of objects where order matters. The number of permutations of n distinct objects is n!. The number of ways to arrange k objects chosen from n is P(n, k) = n! / (n − k)!. Think of it as lining people up in a row: who stands where matters.
Combination (binomial coefficient)
A selection of objects where order does not matter. C(n, k) = n! / (k!(n − k)!), often written as "n choose k." Think of it as picking a committee: who is on it matters, but not the order they were chosen.
Complementary counting
A technique where you count the total number of outcomes and subtract the ones you do not want. Often far easier than counting the desired outcomes directly. In simple terms: "everything minus the bad stuff."
Modular arithmetic set (Z/pZ)
The set {0, 1, 2, ..., p − 1} with arithmetic performed modulo p. In counting problems, elements "wrap around," so 0 and p − 1 are adjacent.
Binomial distribution
The probability of getting exactly k successes in n independent trials, each with success probability p: P(X = k) = C(n, k) · p^k · (1 − p)^{n−k}. Think of it as "how likely is exactly this many heads in this many coin flips?"
Sample space
The set of all possible outcomes of an experiment. Every probability is a ratio of a subset of the sample space to the full sample space (assuming equally likely outcomes).
Problem: how many ways are there to stack 7 differently coloured boxes if the red box cannot be directly on top of the blue box?
The strategy here is complementary counting:
Total arrangements without any constraint: 7! = 5040.
Forbidden arrangements (red directly on blue): treat the red-blue pair as a single fused unit. You now have 6 units to arrange, giving 6! = 720 arrangements.
Valid arrangements: 7! − 6! = 5040 − 720 = 4320.
The key insight is that fusing two items into one reduces the problem by one position. This technique generalises: whenever a constraint says "A must not be immediately next to B" or "A must not be directly above B," compute the total and subtract the cases where the forbidden configuration occurs.
Problem: in Z/pZ = {0, 1, ..., p − 1}, how many unordered pairs {a, b} satisfy |a − b| > 1?
This is a two-case argument:
Case 1, endpoint elements (0 or p − 1 chosen first): each has p − 2 valid partners (exclude itself and the one adjacent element). This gives 2(p − 2) ordered pairs.
Case 2, middle elements (1 through p − 2 chosen first): each has p − 3 valid partners (exclude itself and both adjacent elements). There are p − 2 middle elements, giving (p − 2)(p − 3) ordered pairs.
Total ordered pairs: 2(p − 2) + (p − 2)(p − 3).
Since order does not matter, divide by 2!:
Unordered pairs = [2(p − 2) + (p − 2)(p − 3)] / 2.
The lesson: when a circular or modular structure is involved, separate endpoint cases from interior cases, because the number of excluded neighbours differs.
A common exam format gives several random experiments and asks which has the lowest (or highest) probability. The approach:
Identify the sample space for each experiment.
Compute the probability using the appropriate formula.
Compare.
Worked examples:
9 heads in 10 fair coin flips: use the binomial distribution. P = C(10, 9) · (1/2)^9 · (1/2)^1 = 10/1024 ≈ 0.00977.
Three dice summing to 18: the only way is all sixes (6 + 6 + 6). P = (1/6)^3 = 1/216 ≈ 0.00463.
Drawing the king of hearts from a standard 52-card deck: P = 1/52 ≈ 0.01923.
Comparison: 0.00463 < 0.00977 < 0.01923, so rolling three sixes is the least likely.
Order matters, no repetition: permutations, P(n, k) = n!/(n − k)!.
Order does not matter, no repetition: combinations, C(n, k).
Order matters, repetition allowed: n^k (k choices from n options with replacement).
Order does not matter, repetition allowed: C(n + k − 1, k) (stars and bars).
Exactly k successes in n trials: binomial distribution.
Constraint says "not X": consider complementary counting (total minus forbidden).
Scenario | Formula |
|---|---|
Permutations of n objects | n! |
k-permutations from n | n! / (n − k)! |
Combinations (n choose k) | n! / (k!(n − k)!) |
Arrangements with repetition | n^k |
Stars and bars | C(n + k − 1, k) |
Binomial probability | C(n, k) · p^k · (1 − p)^{n−k} |
Complementary count | Total − Forbidden |
Complementary counting is the backbone of inclusion-exclusion algorithms used in database query optimisation: instead of computing complex intersections directly, systems often compute the complement. The binomial distribution appears everywhere from quality control in manufacturing (how many defective items in a batch?) to A/B testing in tech (did the new feature actually change the click rate, or was it chance?).
Students frequently forget to divide by k! when order does not matter. If the problem says "pick a set" or "choose a group," you need combinations, not permutations.
In complementary counting, students sometimes subtract the wrong quantity. Make sure the "forbidden" set you are subtracting matches the constraint exactly. For the box problem, the forbidden set is "red directly on top of blue," not "red and blue adjacent in any order."
When computing binomial probabilities, students often forget the C(n, k) coefficient and just write p^k · (1 − p)^{n−k}. The coefficient counts the number of ways the k successes can be distributed across the n trials.
In modular-arithmetic counting, students treat endpoints the same as interior elements. On a line (or in Z/pZ without wraparound), endpoints have fewer neighbours, so the case split matters.
⚠️ Complementary counting is tested frequently. If a problem says "how many arrangements avoid condition X," your first instinct should be total minus cases-with-X.
⚠️ Probability comparison problems require careful arithmetic. Compute each probability fully before comparing; do not estimate.
⚠️ Know the binomial distribution formula and be able to apply it to small cases (n ≤ 10 or so) by hand.
⚠️ Questions involving Z/pZ or circular arrangements require splitting into endpoint and interior cases. Forgetting the case split is a common source of wrong answers.
True or false: C(10, 3) = C(10, 7).
Fill in the blank: the probability of rolling three sixes on three fair dice is ______.
True or false: to count arrangements where event X does not occur, compute (total arrangements) + (arrangements where X occurs).
Fill in the blank: in the binomial distribution, the coefficient C(n, k) accounts for ______.
True or false: in Z/pZ, element 0 has two adjacent elements (1 and p − 1).
Answers: (1) True, by the symmetry of binomial coefficients. (2) (1/6)^3 = 1/216. (3) False, you subtract, not add. (4) The number of ways to arrange k successes among n trials. (5) True (if we consider circular adjacency), but in the linear distance interpretation used in the practice problem, 0 is an endpoint with only one neighbour (1), so context matters. Read the problem carefully.
Q: How many ways can 7 distinct boxes be stacked if the red box must not be directly on top of the blue box?
A: 7! − 6! = 5040 − 720 = 4320. We subtract the arrangements where the red-blue pair is fused into one unit.
Q: In Z/pZ = {0, 1, ..., p − 1} with p > 2, how many unordered pairs {a, b} satisfy |a − b| > 1?
A: [2(p − 2) + (p − 2)(p − 3)] / 2. The numerator counts ordered pairs (endpoints contribute 2(p − 2), interior elements contribute (p − 2)(p − 3)), and we divide by 2 because order does not matter.
Q: Which is less likely: getting exactly 9 heads in 10 fair coin tosses, or rolling three dice that sum to 18?
A: Rolling three dice that sum to 18 is less likely. P(three sixes) = (1/6)^3 ≈ 0.00463, while P(9 heads in 10 flips) = C(10,9) · (1/2)^{10} ≈ 0.00977.
Q: A student computes the probability of 9 heads in 10 flips as (1/2)^9 · (1/2)^1 = 1/1024 ≈ 0.000977. What did they get wrong?
A: They omitted the binomial coefficient C(10, 9) = 10. The 9 heads can occur on any 9 of the 10 tosses, so the correct probability is 10/1024 ≈ 0.00977, roughly ten times larger.
Complementary counting extends to the inclusion-exclusion principle, which handles problems with multiple overlapping constraints and appears in probability theory and number theory (Euler's totient, sieve of Eratosthenes).
The binomial distribution is the starting point for statistics. It generalises to the multinomial distribution and connects to the normal distribution via the Central Limit Theorem.
Counting in Z/pZ relates to number theory and cryptography, where modular arithmetic is foundational. Counting valid key pairs in cryptographic protocols often involves exactly this kind of constrained selection.
counting, combinatorics, permutation, combination, binomial coefficient, n choose k, factorial, complementary counting, inclusion-exclusion, modular arithmetic, Z mod p, residues, binomial distribution, Bernoulli trial, sample space, probability, equally likely outcomes, stars and bars, arrangements with constraints, CS 182, Purdue, foundations of computer science