Combinatorics (Advanced)

Counting without listing: multiply for choices made one after another, add for choices that exclude each other, and use ⁿPᵣ or ⁿCᵣ.

Key ideas

AND (one choice after another): multiply. OR (choices that cannot happen together): add.
Use permutations when the order matters (seats, ranks, numbers, words) and combinations when it does not (teams, committees, lines, triangles).
Fill a restricted place first, such as a first digit that cannot be 0 or a last digit that must be even.
Objects that must stay together: treat them as one block, then multiply by the ways to arrange the block inside.
"At least" problems: add the cases one by one, or take the unwanted cases away from the total.
With m of n points on one line, those m give only 1 line and no triangles.

Factorial	n! = n × (n − 1) × … × 2 × 1; 0! = 1
Permutations	ⁿPᵣ = n! ÷ (n − r)!; with repetition: nʳ
Combinations	ⁿCᵣ = n! ÷ (r!(n − r)!); ⁿCᵣ = ⁿC_n−ᵣ
Lines and triangles, m of n points on a line	ⁿC₂ − ᵐC₂ + 1 lines; ⁿC₃ − ᵐC₃ triangles
Diagonals of an n-sided polygon	ⁿC₂ − n = n(n − 3)/2
A telescoping sum	1 × 1! + 2 × 2! + … + n × n! = (n + 1)! − 1

In how many ways can the letters of MOTHER be arranged so that (a) all the vowels come together (b) the vowels do not all come together?

Working: (a) 4 consonants + 1 vowel block: 5! × 2!; (b) 6! − (a) = 720 − 240

Answer: (a) 240; (b) 480