Home / Courses / Probability / Unit 1

Probability Unit 1: Counting and Combinatorics

Counting methods let you find the size of a sample space and of events without listing outcomes. Classical probability, poker hands and many exam problems depend on counting correctly.

Covers: Multiplication principle, Permutations, Combinations, Arrangements with repeated objects, Stars and bars, Inclusion–exclusion counting, Binomial theorem

Study guide

The basic tool is the multiplication principle: if a procedure has several steps and step i can be done in nᵢ ways no matter how earlier steps went, the whole procedure can be done in n₁ × n₂ × ··· ways. A 3-letter, 4-digit license plate with repetition allowed has 26³ × 10⁴ possibilities. The addition rule is its partner: if you must pick one option from several non-overlapping lists, add the list sizes. Most counting errors come from using one rule when the situation calls for the other, so always ask whether you are making a sequence of choices or a single choice from separate cases.

A permutation is an ordered arrangement. The number of ways to arrange n distinct objects is n!, and the number of ordered selections of k from n is P(n, k) = n!/(n − k)!. A combination is an unordered selection, counted by C(n, k) = n!/(k!(n − k)!), because each unordered group of k appears k! times among the ordered selections. The key question is whether swapping two chosen items gives a different outcome. Offices such as president and treasurer, rankings and seat orders depend on order; committees, poker hands and lottery picks do not. Circular arrangements of n people count as (n − 1)! when rotations are considered the same.

When objects repeat, divide out the orderings that look identical. The letters of MISSISSIPPI can be arranged in 11!/(4! 4! 2!) ways. The same multinomial coefficient n!/(n₁! n₂! ··· n_k!) counts the ways to split n people into labeled groups of sizes n₁, …, n_k. To distribute n identical items into k distinct boxes, use stars and bars: there are C(n + k − 1, k − 1) ways if boxes may be empty and C(n − 1, k − 1) if each box needs at least one. Identical versus distinct objects and boxes changes the answer completely, so decide that before writing a formula.

Inclusion–exclusion corrects for overlap: |A ∪ B| = |A| + |B| − |A ∩ B|, and for three sets you add back the triple intersection. It counts integers divisible by 2 or 5, derangements (no object in its own place), onto functions, and distributions with upper limits. For 'at least one' questions, the complement is often faster: count everything, then subtract the outcomes with none. Finally, the binomial theorem (x + y)ⁿ = Σ C(n, k)xᵏyⁿ⁻ᵏ links counting to algebra; it explains why a set of n elements has 2ⁿ subsets and gives coefficients such as C(6, 2) × 2² for x²y⁴ in (2x + y)⁶.

Key ideas

• Multiply for a sequence of choices; add for one choice among non-overlapping cases.
• Use permutations when order matters and combinations when it does not.
• Divide by the factorial of each repeat count when identical objects are arranged.
• Stars and bars counts ways to place identical items into distinct boxes.
• Inclusion–exclusion fixes double counting when categories overlap.
• For 'at least one' counts, total minus 'none' is usually easiest.
• Break hard counts into disjoint cases (such as suit patterns) so nothing is counted twice.

Formulas and rules

Common mistakes

• Using permutations for committees or hands where order does not matter, which overcounts by k!.
• Counting 'one of each, then anything' for 'at least one' problems, which counts the same outcome several times.
• Forgetting to divide by the factorial of a repeated letter or group size.
• Mixing up the nonnegative and positive versions of stars and bars.
• Adding overlapping cases without subtracting their intersection.

Before the test, make sure you can

• Decide whether order matters and choose permutations or combinations.
• Calculate counts with the multiplication principle, including license-plate and PIN problems.
• Count arrangements with repeated letters using the multinomial coefficient.
• Apply stars and bars for identical items, with and without empty boxes.
• Use inclusion–exclusion for unions, derangements and onto functions.
• Count poker hands such as full houses and 'exactly k of a suit'.
• Find binomial expansion coefficients, including constants inside the binomial.

Words to know

Multiplication principle

If step 1 has m outcomes and step 2 has n for each, the two steps together have mn outcomes.

Addition rule

If a choice comes from one of several disjoint lists, the number of options is the sum of the list sizes.

Factorial

n! = n(n − 1)···1, the number of orderings of n distinct objects; 0! = 1.

Permutation

An ordered arrangement; P(n, k) = n!/(n − k)! ordered selections of k from n.

Combination

An unordered selection; C(n, k) = n!/(k!(n − k)!).

Circular permutation

Arrangement around a circle where rotations are the same; (n − 1)! for n objects.

Multinomial coefficient

n!/(n₁!···n_k!), the number of ways to arrange n objects with repeats or split n into labeled groups.

Stars and bars

Method that counts placements of n identical items into k distinct boxes as C(n + k − 1, k − 1).

Inclusion–exclusion

Count a union by adding single sets, subtracting pairwise overlaps, adding triple overlaps, and so on.

Complement counting

Count the outcomes you want by subtracting the unwanted ones from the total.

Derangement

A permutation in which no object stays in its original position; D₄ = 9.

Binomial theorem

(x + y)ⁿ = Σ C(n, k)xᵏyⁿ⁻ᵏ.

Pascal's rule

C(n, k) = C(n − 1, k − 1) + C(n − 1, k), the rule that builds Pascal's triangle.

Power set size

A set with n elements has 2ⁿ subsets.

Onto function

A function in which every element of the codomain is the image of at least one input.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.