Permutations & Combinations

Permutations & Combinations

The art of counting without listing. Get one question right first — does order matter? — and the rest follows.

The two engines

• Fundamental rule: stages with $m$ then $n$ choices give $m\times n$ (AND ⇒ multiply); mutually exclusive cases add (OR).
• Permutations (order matters): $^nP_r=\dfrac{n!}{(n-r)!}$.
• Combinations (order doesn't): $^nC_r=\dfrac{n!}{r!\,(n-r)!}$, with $^nC_r={}^nC_{n-r}$.
• Arrangements with repetition: $n$ items where one repeats $p$ times, another $q$ times $\to\dfrac{n!}{p!\,q!}$.
• Circular arrangements of $n$ distinct items: $(n-1)!$.

A worked example

How many distinct arrangements can be made from the letters of BANANA?

Six letters, but with repeats: A appears 3 times, N twice, B once. Divide out the indistinguishable swaps:

$\frac{6!}{3!\,2!\,1!}=\frac{720}{6\cdot2}=\mathbf{60}.$

Selection idioms

• "At least one" → easier as total $-$ "none."
• "Exactly $k$" → $^nC_k$ times the ways to fill the rest.
• "Items together" → glue them into one block, then arrange the block internally.

Common traps

• Permutation where a combination is meant. Selecting a team of 3 from 8 is $^8C_3=56$, not $^8P_3$.
• Over-counting identical objects. Divide by the factorials of repeats.
• Circular double-count. Fix one seat to remove rotations; if reflections are identical, halve again.

Checklist

• First ask: does order matter?
• AND ⇒ multiply, OR ⇒ add
• Divide by repeat-factorials for identical items
• Use total − none for "at least one"