Combinations and Permutations

Pick 6 from 49 in a lottery. Count arrangements instead of subsets and you get a number 720 times too large, because $P(6,6) = 6! = 720$ orderings map to the same ticket.

If a procedure has $k$ sequential stages with $n_1, n_2, \ldots, n_k$ choices respectively, the total number of outcomes is:

$$n_1 \times n_2 \times \cdots \times n_k$$

This applies whenever choices at each stage are independent of earlier choices.

A permutation is an ordered arrangement. Choose $r$ objects from $n$ distinct objects:

$$P(n,r) = \frac{n!}{(n-r)!}$$

Special case: arrange all $n$ objects, that gives $n!$.

When $n$ objects include groups of identical items ($n_1$ of type 1, $n_2$ of type 2,..., $n_k$ of type $k$) the distinct arrangements form the multinomial coefficient:

$$\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$$

MISSISSIPPI has 11 letters: 1 M, 4 I's, 4 S's, 2 P's. Distinct arrangements: $11!/(1! \cdot 4! \cdot 4! \cdot 2!) = 34{,}650$.

Common mistakes

• Using permutations when combinations are needed. Choosing 3 engineers from 7 with $P(7,3) = 210$ overcounts by $3! = 6$. Trap: 210 instead of 35.
• Forgetting to divide by repeated elements. Arrangements of MISSISSIPPI as $11! = 39{,}916{,}800$ instead of $34{,}650$. Trap: 39,916,800.
• Missing cases in "at least" problems. Computing only "exactly 1 green" and forgetting "exactly 2 green." Trap: 120 instead of 150.

Bottom line

• Fundamental counting principle: multiply the number of choices at each stage; it underlies every permutation and combination formula.
• Permutations (order matters): $P(n,r) = n!/(n-r)!$. Combinations (order doesn't): $\binom{n}{r} = n!/(r!(n-r)!)$; they differ by a factor of $r!$.
• Key question: does rearranging the selected objects create a different outcome? Yes is a permutation, no is a combination.
• Multinomial coefficient: $n!/(n_1! \cdot n_2! \cdots n_k!)$ arranges objects with repeated identical copies (MISSISSIPPI gives 34,650).

Exam shortcut

When stuck, translate the problem into a physical process: "I am pulling 4 balls, do I care about the order I pull them?" This forces the permutation vs. combination decision before you write a formula. "Combinations are permutations with the ordering divided out." $\binom{n}{r} = P(n,r)/r!$. If you accidentally compute a permutation, dividing by $r!$ recovers the combination.

The full lesson (about 2,618 words, 17 min read) adds 3 worked examples, all 7 common mistakes, a self-check, free in the app.

Learning objectives

• 1b

Browse all free Exam P lessons or jump into free Exam P practice questions.