Permutations and Combinations

The Fundamental Principle of Counting is the foundation of this chapter. It lets us count arrangements without listing every single possibility.

Multiplication Principle: If an event can occur in m different ways, and following it, a second event can occur in n different ways, then the two events together can occur in m × n different ways. This extends to any number of events: if k events can occur in n₁, n₂, ..., n_k ways respectively, the total number of ways all of them can occur in order is n₁ × n₂ × ... × n_k.

Addition Principle: If an event can occur in m ways and a second, mutually exclusive event (the two cannot happen together) can occur in n ways, then either of the two events can occur in m + n ways.

Worked Example: A restaurant menu has 5 starters, 4 main courses and 3 desserts. In how many ways can a customer choose one starter, one main course and one dessert?

Choosing the starter can be done in 5 ways, the main course in 4 ways, and the dessert in 3 ways. Since these are independent, successive choices, by the multiplication principle the total number of ways is 5 × 4 × 3 = 60.

Now suppose the customer instead wants only ONE item — either a starter OR a dessert (not both) as a quick snack. Since these are mutually exclusive alternatives, by the addition principle the number of ways is 5 + 3 = 8.

Factorial notation gives a compact way of writing the product of the first n natural numbers, and it is central to every permutation and combination formula.

For a positive integer n, n! = n × (n − 1) × (n − 2) × ... × 3 × 2 × 1. By convention, 0! = 1. Factorial is defined only for whole numbers (0, 1, 2, 3, ...); it is not defined for negative integers or fractions.

A useful recurrence relation is n! = n × (n − 1)!, which lets us simplify ratios of factorials without expanding them fully.

Worked Example: Solve for n: (n + 1)! = 12 × (n − 1)!.

Using the recurrence relation, (n + 1)! = (n + 1) × n × (n − 1)!. Substituting:

(n + 1) × n × (n − 1)! = 12 × (n − 1)!

Dividing both sides by (n − 1)! (which is never zero): (n + 1)(n) = 12, i.e., n² + n − 12 = 0.

Factorising: (n + 4)(n − 3) = 0, so n = −4 or n = 3. Since n must be a non-negative integer, n = 3.

A permutation is an arrangement of objects in a definite order. Order matters — AB and BA are different permutations of the same two letters.

The number of permutations of n distinct objects taken r at a time (r ≤ n), without repetition, is denoted ⁿP_r and equals n!/(n − r)!. When r = n, this simplifies to ⁿP_n = n!, the number of ways to arrange all n objects.

If repetition of objects IS allowed while forming an arrangement of length r from n available objects, each of the r positions can independently be filled in n ways, so the total number of arrangements is n^r.

Worked Example: Using the digits 1, 2, 3, 4, 5, 6 (each digit used at most once), find (i) how many 4-digit numbers can be formed, and (ii) how many of these are even.

(i) We are arranging 4 digits out of 6 distinct digits, order matters, no repetition: ⁶P₄ = 6!/(6−4)! = 6 × 5 × 4 × 3 = 360.

(ii) For the number to be even, the units digit must be 2, 4 or 6 — that is 3 choices. After fixing the units digit, the remaining 3 places are filled from the remaining 5 digits without repetition: ⁵P₃ = 5 × 4 × 3 = 60 ways. By the multiplication principle, the total number of even 4-digit numbers is 3 × 60 = 180.

If all n objects were distinct, there would be n! arrangements. But when some objects are identical, swapping two identical objects does not create a new arrangement — so we must divide out the repeated internal orderings.

If, out of n objects, p₁ are alike of one kind, p₂ are alike of a second kind, ..., and p_k are alike of a k-th kind (with p₁ + p₂ + ... + p_k = n), then the number of distinct permutations of all n objects is n!/(p₁! p₂! ... p_k!).

Worked Example: Find the number of distinct arrangements of the letters of the word 'MATHEMATICS'.

The word MATHEMATICS has 11 letters in total. Counting repetitions: M occurs 2 times, A occurs 2 times, T occurs 2 times, and H, E, I, C, S occur once each (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 11, check).

Number of distinct arrangements = 11!/(2! × 2! × 2!) = 39916800/(2 × 2 × 2) = 39916800/8 = 4989600.

Second Example: Find the number of arrangements of the letters of 'MISSISSIPPI'.

MISSISSIPPI has 11 letters: M occurs once, I occurs 4 times, S occurs 4 times, P occurs 2 times (1 + 4 + 4 + 2 = 11, check).

Number of distinct arrangements = 11!/(4! × 4! × 2!) = 39916800/(24 × 24 × 2) = 39916800/1152 = 34650.

A combination is a selection of objects where the order of selection is irrelevant — choosing {A, B} is the same as choosing {B, A}. This is the key difference from a permutation.

The number of ways of selecting r objects from n distinct objects (0 ≤ r ≤ n) is denoted ⁿC_r and is given by ⁿC_r = n!/(r!(n − r)!).

Two useful properties: ⁿC_r = ⁿC_n−r (choosing r objects to include is the same as choosing n − r objects to leave out), and ⁿC₀ = ⁿC_n = 1. Also, Pascal's rule states ⁿC_r + ⁿC_r−1 = ⁿ⁺¹C_r.

Worked Example: A committee of 5 members is to be formed consisting of exactly 3 men and 2 women, chosen from 6 men and 4 women. In how many ways can this be done?

Order of selection does not matter within the committee, so this is a combinations problem. Choose 3 men from 6: ⁶C₃ = 6!/(3!3!) = 20. Choose 2 women from 4: ⁴C₂ = 4!/(2!2!) = 6. By the multiplication principle, the committee can be formed in 20 × 6 = 120 ways.

Second Example: Find the number of diagonals of a hexagon (6-sided polygon).

A diagonal joins any two non-adjacent vertices. The total number of ways to join any 2 of the 6 vertices (giving all sides plus diagonals) is ⁶C₂ = 15. Of these, 6 are the sides of the hexagon itself. So the number of diagonals = 15 − 6 = 9.

Permutations and combinations are closely linked: every permutation of r objects out of n can be thought of as a two-step process — first select r objects (ignoring order), then arrange the selected r objects in every possible order.

Selecting r objects from n can be done in ⁿC_r ways. Each such selection of r objects can then be arranged among themselves in r! ways. So ⁿP_r = ⁿC_r × r!, which also gives ⁿC_r = ⁿP_r / r!.

This relationship is often used to solve equations that mix nPr and nCr, or to find an unknown n or r from a given combinatorial equation.

Worked Example: If ⁿC₉ = ⁿC₇, find n.

Using the property ⁿC_r = ⁿC_n−r: since ⁿC₉ = ⁿC₇, and 9 ≠ 7, the two lower indices must add up to n. So n = 9 + 7 = 16.

Second Example: Find n if ⁿP₄ = 360.

ⁿP₄ = n(n − 1)(n − 2)(n − 3) = 360. Testing n = 6: 6 × 5 × 4 × 3 = 360, which matches. So n = 6.