Permutations and Combinations: Arrangements & Selections
These formulas are required for Paper 5 – Probability & Statistics 1 of the Cambridge International AS & A Level Mathematics (9709) syllabus. They also appear in the “Series”, “Probability notation” and “Multiplication rule” topics, so a solid grasp is essential for the whole course.
1. Factorial Notation
- For a non‑negative integer n:
\[
n! = n\,(n-1)\,(n-2)\dotsm2\cdot1,\qquad 0! = 1 .
\]
- Interpretation: the number of ways to arrange n distinct objects in a straight line.
2. Permutations – Ordered Arrangements
2.1 All \(n\) Distinct Objects (No Repetition)
Every position can be filled by any remaining object, giving
\[
P(n)=n!
\]
2.2 Permutations of a Subset (No Repetition)
Choose and order r objects from n distinct objects:
\[
P(n,r)=n\,(n-1)\dotsm (n-r+1)=\frac{n!}{(n-r)!}.
\]
Example: Order 3 of 5 books
\[
P(5,3)=\frac{5!}{2!}=60\text{ ways}.
\]
2.3 Permutations with Repetition (k choices for each of n positions)
\[
k^{\,n}
\]
Example: 4‑digit PIN using digits 0–9
\(10^{4}=10\,000\) possibilities.
2.4 Permutations of Repeated (Identical) Objects – Multiset Permutations
If a set contains \(n_1\) objects of type 1, \(n_2\) of type 2, …, \(n_k\) of type k ( \(\sum n_i=n\) ), the number of distinct linear arrangements is
\[
\frac{n!}{n_1!\,n_2!\dotsm n_k!}.
\]
Example: The word LEVEL (5 letters, L×2, E×2, V×1)
\[
\frac{5!}{2!\,2!}=30\text{ arrangements}.
\]
2.5 Circular Permutations (Rotations considered identical)
- For n distinct objects round a circle:
\[
(n-1)! .
\]
- Reason: fix one object as a reference point; the remaining \(n-1\) can be ordered freely.
- If a block of objects must stay together, treat the block as a single item, apply the circular formula, then multiply by the internal arrangements of the block.
3. Combinations – Unordered Selections
3.1 Combinations of Distinct Objects (No Repetition)
\[
\binom{n}{r}= \frac{n!}{r!\,(n-r)!}.
\]
Example: Choose 3 committee members from 8 people
\(\displaystyle \binom{8}{3}=56\) committees.
3.2 Combinations with Repetition (Stars & Bars)
Unlimited copies of each of \(k\) distinct objects, select \(r\) of them:
\[
\binom{r+k-1}{r}= \frac{(r+k-1)!}{r!\,(k-1)!}.
\]
Example: Distribute 5 identical balls into 3 distinct boxes
\(\displaystyle \binom{5+3-1}{5}= \binom{7}{5}=21\) ways.
3.3 Multinomial Coefficients
When a selection is split into more than two groups:
\[
\binom{n}{n_1,n_2,\dots ,n_k}= \frac{n!}{n_1!\,n_2!\dotsm n_k!},
\qquad\text{with } \sum_{i=1}^{k} n_i=n .
\]
Useful for words with several repeated letters (e.g. “MATHEMATICS”).
4. Links to Probability
- Sample‑space size \(|S|\): obtained by a permutation/combination count.
- Multiplication rule: If an experiment consists of independent stages, total outcomes = product of the outcomes of each stage.
- Probability notation (assumed knowledge):
\[
P(A)=\frac{\text{favourable outcomes}}{|S|},\quad
P(A\cup B)=P(A)+P(B)-P(A\cap B),\quad
P(A\mid B)=\frac{P(A\cap B)}{P(B)} .
\]
- Series connection: Binomial coefficients appear in the expansion
\[
(1+x)^n=\sum_{r=0}^{n}\binom{n}{r}x^{r}.
\]
5. Inclusion–Exclusion Principle (Brief)
When several restrictions overlap, the number of admissible arrangements is
\[
|A_1\cup\cdots\cup A_m|
= \sum_i |A_i|
- \sum_{i
Typical use: “no two particular books are together”.
6. Summary Table of Key Formulas
| Situation |
Formula |
Result |
| All \(n\) distinct objects (linear) |
\(n!\) |
\(n!\) |
| Arrange \(r\) of \(n\) distinct objects (no repetition) |
\(\displaystyle\frac{n!}{(n-r)!}\) |
\(P(n,r)\) |
| Arrange \(n\) positions with \(k\) choices each (repetition allowed) |
\(k^{\,n}\) |
\(k^{\,n}\) |
| Arrange \(n\) objects with repeats \(n_1,n_2,\dots ,n_k\) |
\(\displaystyle\frac{n!}{n_1!\,n_2!\dotsm n_k!}\) |
Multiset permutation |
| Circular arrangement of \(n\) distinct objects |
\((n-1)!\) |
Rotations identified |
| Select \(r\) of \(n\) distinct objects (order ignored) |
\(\displaystyle\binom{n}{r}\) |
\(\displaystyle\frac{n!}{r!\,(n-r)!}\) |
| Select \(r\) objects from \(k\) types (unlimited supply) |
\(\displaystyle\binom{r+k-1}{r}\) |
\(\displaystyle\frac{(r+k-1)!}{r!\,(k-1)!}\) |
| Multinomial selection \((n_1,n_2,\dots ,n_k)\) |
\(\displaystyle\binom{n}{n_1,n_2,\dots ,n_k}\) |
\(\displaystyle\frac{n!}{n_1!\,n_2!\dotsm n_k!}\) |
7. Worked Example (Combining Several Ideas)
Problem: A password consists of 3 distinct letters followed by 2 digits (digits may repeat). How many such passwords are possible?
- Choose and order the letters: \(P(26,3)=\dfrac{26!}{23!}=26\times25\times24=15\,600\).
- Choose the two digits (repetition allowed): \(10^{2}=100\).
- Apply the multiplication rule:
\[
15\,600 \times 100 = 1\,560\,000
\]
possible passwords.
8. Common Pitfalls
- Order vs. No order: Use permutations when the arrangement matters; use combinations when it does not.
- Repeated objects: Always divide by the factorial of each group of identical items.
- Stars and bars: The objects must truly be identical and the containers distinct; otherwise the formula is invalid.
- Circular arrangements: Forgetting to fix one position (i.e., dividing by \(n\)) leads to double‑counting.
- Inclusion–exclusion: Omitting the subtraction of intersections gives a count that is too large.
9. Practice Questions
- How many ways can 4 different books be placed on a shelf if two particular books must not be together?
- From a group of 12 students, in how many ways can a president, a secretary, and a treasurer be elected?
- How many 5‑digit numbers can be formed using the digits \(1,2,3,4,5\) if repetition is allowed but the first digit cannot be \(0\)?
- In how many ways can 8 identical candies be distributed among 4 children if each child must receive at least one candy?
- How many distinct arrangements are there of the letters in the word “MATHEMATICS”?
- Four people sit round a circular table. In how many different orders can they be seated?
- Eight people are to be seated round a table, but two particular people must sit together. How many seatings are possible?
10. Answers to Practice Questions
- Total linear arrangements: \(4!=24\).
Treat the two particular books as a single block → block + other two books = \(3!\) ways.
Inside the block the two books can be ordered in \(2!\) ways.
Forbidden arrangements = \(3!\times2!=12\).
Allowed arrangements = \(24-12=12\).
- Ordered selection of 3 distinct positions from 12:
\[
P(12,3)=\frac{12!}{9!}=12\times11\times10=1\,320\text{ ways}.
\]
- First digit: 5 choices (cannot be 0).
Remaining four positions: \(5^{4}=625\) choices.
Total = \(5\times625=3\,125\) numbers.
- Give each child one candy first (uses 4 candies).
Remaining \(8-4=4\) candies are free to distribute:
\[
\binom{4+4-1}{4}= \binom{7}{4}=35\text{ ways}.
\]
- “MATHEMATICS” has 13 letters with repeats:
M×2, A×2, T×2, I×2, C×1, H×1, E×1, S×1.
\[
\frac{13!}{2!\,2!\,2!\,2!}= \frac{13!}{(2!)^{4}}
=\frac{6\,227\,020\,800}{16}=389\,188\,800\text{ arrangements}.
\]
- Circular permutations of 4 distinct people: \((4-1)!=6\) seatings.
- Treat the two particular people as a block.
The block + the other six people give 7 items round a circle: \((7-1)!=720\).
Inside the block the two can switch places: \(2!\) ways.
Total = \(720\times2=1\,440\) seatings.
11. Extensions (Beyond the Core Syllabus)
Multinomial Coefficients
Used when more than two types of repeated objects occur. Example: arranging “LEVEL” (already covered) or “MATHEMATICS”.
Circular Permutations with Restrictions
When certain people must sit together, treat the group as a single entity, apply \((n-1)!\) to the reduced set, then multiply by the internal permutations of the group.
Inclusion–Exclusion in Probability
For events \(A,B,C\):
\[
P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C).
\]
Combine with counting formulas to obtain required probabilities.
12. Quick Reference Cheat‑Sheet
- Factorial: \(n! = n\,(n-1)\dots 1\), \(0! = 1\).
- Permutation (all): \(n!\).
- Permutation (subset): \(P(n,r)=\dfrac{n!}{(n-r)!}\).
- Permutation with repetition: \(k^{\,n}\).
- Permutation of repeated objects: \(\dfrac{n!}{n_1!\,n_2!\dotsm n_k!}\).
- Circular permutation: \((n-1)!\).
- Combination (no repetition): \(\displaystyle\binom{n}{r}= \dfrac{n!}{r!\,(n-r)!}\).
- Combination with repetition (Stars & Bars): \(\displaystyle\binom{r+k-1}{r}= \dfrac{(r+k-1)!}{r!\,(k-1)!}\).
- Multinomial coefficient: \(\displaystyle\binom{n}{n_1,\dots ,n_k}= \dfrac{n!}{n_1!\dotsm n_k!}\).
- Inclusion–Exclusion (2 sets): \(|A\cup B|=|A|+|B|-|A\cap B|\).
- Multiplication rule: If stages are independent, total outcomes = product of outcomes for each stage.