← 🎲 Combinatorics & Recurrences
Subtopic 1 of 7

3.1Counting basics: permutations and combinations

The idea

Counting rests on two rules: the sum rule (either-or: add) and the product rule (and-then: multiply). Permutations count ordered selections, combinations count unordered ones.

Think of it like this: A menu: 3 starters and 4 mains give 12 meals (product); a choice between a starter or a dessert is a sum.

Why it exists

Nearly every counting question starts with "does order matter?"; getting that right is most of the battle.

How it works

  1. P(n, r) = n!/(n−r)!: choose r from n in order.
  2. C(n, r) = n!/(r!(n−r)!): choose r from n, order ignored.
  3. C(n, r) = C(n, n−r), and Σ C(n, r) = 2ⁿ.
  4. Arrangements with repeats: n!/(k₁! k₂! …). Circular arrangements of n: (n−1)!.

Worked example: Rearranging the letters of MISSISSIPPI

11 letters with M×1, I×4, S×4, P×2: 11!/(4!·4!·2!) = 34 650.

Now play with it

  • →Change n and r and compare P(n, r) with C(n, r): they differ by r!.
  • →Check that the circular count is the linear count divided by n.
P(n, r) = n!/(n−r)! (ordered, no repetition)336
C(n, r) = n!/(r!(n−r)!) (unordered)56
Arrangements of all n: n!40320
Circular arrangements of n: (n−1)!5040

Words from "MISSISSIPPI" rearranged: 11!/(4!·4!·2!) = 34650. Divide by k! for every letter repeated k times.

Counting problemFormulaExample
Choose r of n, order matters, no repeatsn!/(n−r)!P(5,2) = 20
Choose r of n, order ignoredC(n, r)C(5,2) = 10
Strings of length r, n symbolsnʳ2⁸ = 256
Multisets of size r from n kindsC(n+r−1, r)C(7,3) = 35
Anagrams of MISSISSIPPI11!/(4!4!2!)34 650
Circular seating of n(n−1)!5 people: 24

Ask three questions: is order important? may items repeat? are the objects (and boxes) distinguishable?

Check yourself

In how many ways can 3 distinct prizes be given to 10 people (one each)?

Remember: Order matters: P(n,r). Order ignored: C(n,r). Repeats: divide by k!.
Exam notes (the dense version)

Sum rule (either-or) adds, product rule (and-then) multiplies. P(n,r) = n!/(n−r)! counts ordered selections; C(n,r) = n!/(r!(n−r)!) counts unordered. C(n,r) = C(n,n−r), Pascal C(n,r) = C(n−1,r−1) + C(n−1,r), Σ C(n,r) = 2ⁿ. Arrangements of n objects with repeats: n!/(k₁!k₂!…). Circular arrangements: (n−1)!.

Previous year questions: Combinatorics & Recurrences (17)

PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.