Permutations and Combinations

In this chapter: the fundamental principle of counting, factorial notation, permutations of distinct objects with and without repetition, permutations when some objects are alike, combinations and the properties of ⁿC_r, and mixed problems on words, digits and committees.

Fundamental principle of counting

Multiplication principle: if one event can occur in m different ways, and following it a second event can occur in n different ways, then the two events in succession can occur in m × n ways. It extends to any number of events done one after another.

With 3 shirts and 2 pairs of trousers you can dress in 3 × 2 = 6 ways. The tree diagram below lists them, but the point of the principle is that you never need to draw the tree.

Addition principle: if a job can be done in one of two alternative ways that cannot happen together, the first in m ways and the second in n ways, the job can be done in m + n ways. Use "and then" → multiply; "or" → add.

Worked example: How many 3-digit numbers can be formed from the digits 1, 2, 3, 4, 5 (a) if repetition is allowed, (b) if it is not?
Solution: Fill three places: hundreds, tens, units. (a) Each place has 5 choices, so 5 × 5 × 5 = 125. (b) The hundreds place has 5 choices, the tens place 4 (one digit used), the units place 3, giving 5 × 4 × 3 = 60.

A habit that saves marks: when a place has a restriction (the number must be even, the first digit cannot be 0), fill that place first.

Factorial notation

For a natural number n, n! = 1 × 2 × 3 × ... × n, and by definition 0! = 1. Useful facts: n! = n × (n − 1)!, and 5! = 120, 6! = 720, 7! = 5040. Factorials of negative numbers or fractions are not defined in this chapter.

Permutations

A permutation is an arrangement of objects in a definite order. The number of permutations of n different objects taken r at a time, where 0 ≤ r ≤ n and repetition is not allowed, is

For example, 4-letter arrangements of the letters of MONDAY, with no letter repeated, number ⁶P₄ = 6 × 5 × 4 × 3 = 360.

When some objects are alike

If n objects include p₁ of one kind, p₂ of a second kind, ..., p_k of a k-th kind (the rest all different), the number of distinct arrangements of all n is

Swapping two identical A's gives the same word, so we divide out those repeated counts. ALLAHABAD has 9 letters with A four times and L twice, giving 9!/(4! 2!) = 362880/48 = 7560 arrangements.

Worked example: In how many ways can the letters of INDEPENDENCE be arranged? In how many of these do all the vowels come together?
Solution: The 12 letters are I (1), N (3), D (2), E (4), P (1), C (1). Total arrangements: 12!/(3! 2! 4!) = 479001600/288 = 1663200.
For the vowels together, tie the 5 vowels (E, E, E, E, I) into one block. Then we arrange 8 objects: the block, N, N, N, D, D, P, C, in 8!/(3! 2!) = 40320/12 = 3360 ways. Inside the block the vowels can be arranged in 5!/4! = 5 ways. Answer: 3360 × 5 = 16800.

A related result you may see in MHT‑CET: n different objects arranged around a circle can be seated in (n − 1)! ways, because rotating everyone by one seat gives the same circular arrangement.

Combinations

A combination is a selection in which order does not matter. Choosing r objects from n different objects can be done in

The second line says each selection of r objects can be arranged in r! ways, which is exactly the difference between an arrangement and a selection. Choosing a captain and vice-captain from 11 players is a permutation (¹¹P₂ = 110); choosing 2 players to open the batting, with no distinction between them, is a combination (¹¹C₂ = 55).

Properties of ⁿC_r

The second property is also a calculation shortcut: ⁵⁰C₄₈ = ⁵⁰C₂ = 1225. And if ⁿC₉ = ⁿC₈, then n = 17, so ⁿC₁₇ = 1.

Standard counts from geometry and selection

• Lines through n points, no three collinear: ⁿC₂. Triangles: ⁿC₃.
• Diagonals of an n-sided polygon: ⁿC₂ − n = n(n − 3)/2.
• Selecting at least one object from n different objects: 2ⁿ − 1.

Worked example: A committee of 3 is to be chosen from 5 men and 4 women. In how many ways can this be done if it must contain at least one woman?
Solution: All committees: ⁹C₃ = 84. Committees with no woman: ⁵C₃ = 10. So the answer is 84 − 10 = 74. Check by cases: 1 woman and 2 men, 4 × 10 = 40; 2 women and 1 man, 6 × 5 = 30; 3 women, 4. Total 40 + 30 + 4 = 74.

"At least one" problems are almost always quicker as (total) minus (none). When you do split into cases, make sure the cases do not overlap.

Common mistakes: (1) Using ⁿP_r for a selection or ⁿC_r for an arrangement; ask whether swapping two chosen objects gives a new outcome. (2) Forgetting that a number cannot start with 0 when 0 is among the digits. (3) Not dividing by the factorials of repeated letters. (4) In "together" problems, forgetting to arrange the objects inside the block. (5) Taking 0! = 0; it is 1. (6) Counting a committee twice by first choosing "one woman compulsorily" and then "any two from the rest"; this double-counts committees with more than one woman.

Exam focus

• Forming numbers from given digits under conditions: even, divisible by 5, greater than a value, with or without repetition.
• Arrangements of letters of a word with repeated letters, with vowels together or never together.
• Committee and team selection with "at least" and "at most" conditions.
• Using ⁿC_r = ⁿC_n−r and Pascal's rule ⁿC_r + ⁿC_r−1 = ⁿ⁺¹C_r to find n or simplify sums.
• Geometry counts: lines, triangles and diagonals from given points.

Practice questions