The fundamental principle of counting
If one event can happen in m ways, and after it a second event can happen in n ways, then the two together can happen in m × n ways.
This extends to any number of events.
Example. A girl has 3 shirts and 4 skirts. She can make 3 × 4 = 12 different outfits.
Example. How many 3-digit numbers can be formed from the digits 1, 2, 3, 4, 5 if no digit is repeated? There are 5 choices for the first digit, 4 for the second and 3 for the third: 5 × 4 × 3 = 60.
If repetition is allowed: 5 × 5 × 5 = 125.
The addition principle is used for "or": if an event can happen in m ways or (separately) in n ways, it can happen in m + n ways.
Factorial
n! = n × (n − 1) × (n − 2) × … × 2 × 1, and 0! = 1
5! = 120, 6! = 720. A useful relation is n! = n × (n − 1)!.
Permutations: arrangements where order matters
The number of ways to arrange r objects chosen from n distinct objects is
ⁿPᵣ = n! / (n − r)!
All n objects can be arranged in ⁿPₙ = n! ways.
Example. In how many ways can a president, a secretary and a treasurer be chosen from 10 people? The roles are different, so order matters: ¹⁰P₃ = 10 × 9 × 8 = 720.
Arrangements with repeated objects
If n objects include p alike of one kind, q alike of another kind, and so on, the number of distinct arrangements is
n! / (p! q! …)
Example. How many distinct arrangements are there of the letters of ALLAHABAD?
There are 9 letters: A appears 4 times, L 2 times, and H, B, D once each. So the number is 9! / (4! × 2!) = 362 880 / 48 = 7560.
Objects that must stay together
Treat the group as a single unit, then arrange within the unit.
Example. In how many ways can 5 boys and 3 girls sit in a row if all the girls sit together? Treat the 3 girls as one block, so there are 6 units: 6! ways. The girls can arrange themselves within the block in 3! ways. Total = 720 × 6 = 4320.
Combinations: selections where order does not matter
The number of ways to choose r objects from n distinct objects is
ⁿCᵣ = n! / [r! (n − r)!] = ⁿPᵣ / r!
Dividing by r! removes the different orders of the same selection.
Useful properties:
ⁿCᵣ = ⁿCₙ₋ᵣ. Choosing r to include is the same as choosing n − r to leave out.
ⁿC₀ = ⁿCₙ = 1.
ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ.
Example. A committee of 3 is chosen from 10 people. Now the roles are the same, so order does not matter: ¹⁰C₃ = 720 / 6 = 120.
Example. A team of 5 must have 3 men and 2 women, chosen from 6 men and 4 women. ⁶C₃ × ⁴C₂ = 20 × 6 = 120 ways.
Example. How many diagonals does a hexagon have? Any 2 of the 6 vertices give a line, which is ⁶C₂ = 15 lines. Of these, 6 are sides. So there are 15 − 6 = 9 diagonals.
Permutation or combination?
Ask yourself | If yes |
|---|---|
Does swapping two chosen items give a different outcome? | Permutation (arrangement) |
Is it only about which items are chosen? | Combination (selection) |
Words such as arrange, order, rank, digits, seating suggest permutations. Words such as select, choose, committee, team, group suggest combinations.