Permutations and Combinations

Permutations and combinations is about counting without listing. It is a smaller topic in the exam (a multiple choice question or a short Section II part), but the counting ideas reappear in the binomial theorem and the binomial distribution, and the hardest questions test careful reasoning rather than formulas. It builds on the probability you met in the Advanced focus area Probability and Data.

• Factorials: $n!=n\times (n-1)!$ and $0!=1$.
• Multiplication principle: $m$ ways then $n$ ways gives $mn$ ways; $n$ distinct objects in a line can be ordered in $n!$ ways.
• Permutations: ordered selections, ${}^n{P}_r$; arrangements with identical objects; restrictions on position.
• Circular arrangements: $(n-1)!$ arrangements of $n$ distinct objects, with or without restrictions.
• Combinations: unordered selections, ${}^n{C}_r$ or $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, the symmetry and Pascal identities, selections with restrictions.
• Mixed problems: problems that need both permutations and combinations, often split into cases, including probabilities found by counting.

The pigeonhole principle was in the old syllabus but is not in the 2024 syllabus.

$n!$ ("$n$ factorial") is $n\times (n-1)\times \cdots \times 2\times 1$, and $0!=1$ by convention. Simplify factorial expressions by cancelling, for example $\frac{(n+1)!}{(n-1)!}=(n+1)n$.

Multiplication principle: if one choice can be made in $m$ ways and then a second in $n$ ways, the pair can be made in $m\times n$ ways. Filling $n$ positions in a line from $n$ distinct objects gives $n\times (n-1)\times \cdots \times 1=n!$ arrangements.

A good habit is to draw boxes for the positions and fill in the number of choices for each, starting with the most restricted position.

A permutation is an ordered selection. The number of ways to arrange $r$ objects chosen from $n$ distinct objects is

with ${}^n{P}_n=n!$ and ${}^n{P}_0=1$.

Identical objects

If $n$ objects include $p$ that are identical of one kind, $q$ of another, and so on, the number of distinct arrangements is

Dividing by $p!$ removes the arrangements that only swap identical objects.

Restrictions

• Objects together: glue them into one block, arrange the blocks, then arrange the objects inside the block.
• Objects apart: count all arrangements, then subtract those where they are together. Alternatively, arrange the others first and place the restricted objects in the gaps.
• Fixed positions: fill the restricted positions first.

Worked example 1: identical letters with a restriction

How many arrangements of the letters of PEPPER are there, and in how many are the two Es together?

PEPPER has 6 letters: three Ps, two Es and one R.

For the Es together, treat EE as a single block. Now arrange 5 items (EE, P, P, P, R), three of which are identical. The two Es are identical, so swapping them inside the block gives nothing new:

So the Es are apart in $60-20=40$ arrangements.

Around a circle only relative positions matter, so rotating an arrangement does not make a new one. Fix one person's seat to remove the rotations, then arrange the rest in a line: $n$ distinct objects can be arranged in a circle in $(n-1)!$ ways.

Worked example 2: a group together at a round table

Eight people sit at a round table. In how many ways can they sit if three particular friends must sit together?

Treat the three friends as one block. There are now 6 units around the table, which can be arranged in $(6-1)!=120$ ways. The friends can be arranged within the block in $3!=6$ ways.

A combination is a selection where order does not matter. The number of ways to choose $r$ objects from $n$ distinct objects is

Facts you should know and be able to explain:

• $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$ and $\left(\genfrac{}{}{0ex}{}{n}{1}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)=n$.
• Symmetry: $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-r}\right)$, because choosing $r$ objects to include is the same as choosing $n-r$ to leave out.
• Pascal's identity: $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ for $1\le r\le n-1$.

The combinatorial proof of Pascal's identity: fix one particular object. Selections of $r$ either include it (choose the other $r-1$ from the remaining $n-1$) or exclude it (choose all $r$ from the remaining $n-1$). These two cases do not overlap and cover everything.

Algebraically, put the two terms over the common denominator $r!(n-r)!$:

Permutation or combination?

Ask: would swapping two chosen objects give a different outcome? If yes (positions, roles, a password), order matters: use permutations. If no (a committee, a hand of cards), use combinations.

Worked example 3: case analysis and probability

A committee of 5 is chosen from 7 teachers and 6 students. How many committees have at least 2 teachers and at least 2 students? If the committee is chosen at random, what is the probability of this?

With 5 people and at least 2 of each group, the only cases are 2 teachers and 3 students, or 3 teachers and 2 students:

The cases do not overlap, so add them: $420+525=945$ committees.

The total number of committees is $\left(\genfrac{}{}{0ex}{}{13}{5}\right)=1287$, each equally likely, so

A tempting wrong method is "choose 2 teachers, 2 students, then any 1 of the remaining 9": $21\times 15\times 9=2835$. This counts each committee more than once, because the "extra" person could have been chosen in the first stage instead. Splitting into non-overlapping cases avoids double counting.

• Using permutations when order does not matter (or the reverse).
• Forgetting to divide by the factorials of identical objects, or forgetting to arrange the objects inside a "together" block.
• Using $n!$ instead of $(n-1)!$ for a circular arrangement, or $(n-1)!$ when the seats are labelled (numbered seats are a line problem, not a circle).
• Double counting in "at least" questions by choosing the minimum first and then filling up from everyone.
• Adding when you should multiply: "and then" (stages) means multiply; "or" (separate cases) means add.
• For probability, using a numerator counted with order and a denominator counted without order. Count both the same way.

• Write a short sentence or expression for each stage, for example "arrange the block: $3!$". Markers can then award method marks even if the final number is wrong.
• For "at least" or "at most", consider the complement (all minus the cases you do not want) when it has fewer cases.
• Leave answers as products such as $5!\times 3!$ until the end, then evaluate. In probability questions simplify the fraction or give a decimal as asked.
• Check reasonableness with a tiny case (2 or 3 objects) that you can list by hand.
• Show that or prove an identity combinatorially: describe one counting situation and count it in two different ways, explaining each count in words.

• Advanced, Probability and Data: equally likely outcomes, complementary events and the multiplication rule for probabilities.
• The binomial theorem (ME11-BT): the coefficients in the expansion of $(x+y{)}^n$ are the combinations $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, and Pascal's identity builds Pascal's triangle.
• Proof by mathematical induction (ME12-PI): factorial and $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ expressions often appear in induction proofs.
• The binomial distribution (ME12-BS): $P(X=r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)p^r(1-p{)}^{n-r}$ uses $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ to count the ways of placing $r$ successes among $n$ trials.