CombinatoricsEdexcel A-Level Further Maths: Revision notes

If a task is done in stages, with $m$ ways to do the first, $n$ ways to do the second (whatever the first choice), and so on, the total number of ways is $m\times n\times\dots$ This is the multiplicative principle. Example: a four-digit PIN where each digit is one of $0$ to $9$ and repeats are allowed has $10\times10\times10\times10=10^4=10\,000$ possibilities. Where earlier choices reduce later ones, multiply the reduced numbers: four different digits gives $10\times9\times8\times7=5040$.

A permutation is an arrangement where order matters: the number of ways to choose and arrange $r$ items from $n$ is $^nP_r=\frac{n!}{(n-r)!}$. A combination is a selection where order does not matter: $\binom nr={}^nC_r=\frac{n!}{r!(n-r)!}$. Always $^nP_r=r!\times\binom nr$. Example: from a committee of $12$, choosing $4$ with no roles gives $\binom{12}{4}=495$; choosing $4$ for four different posts gives $^{12}P_4=11\,880$. Decide which applies by asking: would swapping two chosen items give a different outcome? If yes, use $^nP_r$.

A set with $n$ elements has $2^n$ subsets, including the empty set and the set itself, because each element is either in or out. The number of subsets with exactly $r$ elements is $\binom nr$. Excluding the empty set leaves $2^n-1$. Example: a group chosen from $10$ athletes has $2^{10}-1=1023$ possibilities if it must be non-empty.

If a task can be done in one of several ways that cannot happen together, add the numbers (addition principle). For 'at least' questions it is often easier to subtract the opposite case from the total. Example: the number of PINs with at least one $7$ is $10^4-9^4=3439$. Example: teams of $11$ from $2$ goalkeepers and $19$ outfield players that include at least one goalkeeper: $\binom{21}{11}-\binom{19}{11}=352\,716-75\,582=277\,134$. To count positive integers less than $1000$ containing the digit $3$ at least once: strings $000$ to $999$ with no $3$ number $9^3=729$, which includes $000$, so $728$ positive integers have no $3$, and $999-728=271$ contain a $3.$.

Many problems join the principles: choose first, then arrange. For a relay team of $4$ from $4$ girls and $6$ boys with exactly $2$ girls: choose $\binom42\binom62=90$, then arrange in $4!=24$ orders to get $2160$. For 'at least $k$' of a type, split into cases (exactly $k$, exactly $k+1$, ...) and add: at least $3$ girls in a training group: $\binom43\,2^6+\binom44\,2^6=320$.