Combinatorics

Combinatorics

Spec 5.7 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Multiplicative principle: successive independent stages multiply, m×n×…m\times n\times\dots
  • Permutations (order matters): nPr=n!(n−r)!^nP_r=\frac{n!}{(n-r)!}. Combinations (order does not): (nr)=n!r!(n−r)!\binom nr=\frac{n!}{r!(n-r)!}.
  • A set with nn elements has 2n2^n subsets, including the empty set.
  • Addition principle: exclusive cases add. For "at least one", use total minus none.
  • Join the principles: choose first, then arrange.

The multiplicative principle

Multiply the number of ways of each stage.

If a task is done in stages, with mm ways to do the first, nn ways to do the second (whatever the first choice), and so on, the total number of ways is m×n×…m\times n\times\dots This is the multiplicative principle.

A four-digit PIN where each digit is 00 to 99 and repeats are allowed has 104=10 00010^4=10\,000 possibilities.

Where earlier choices reduce later ones, multiply the reduced numbers: four different digits gives 10×9×8×7=504010\times9\times8\times7=5040.

  1. 1

    1st digit

    10 choices

  2. 2

    2nd digit

    9 choices left

  3. 3

    3rd digit

    8 choices left

  4. 4

    4th digit

    7 choices left

  5. 5

    Multiply

    10×9×8×7=504010\times9\times8\times7=5040

Counting four different digits.

A code has 3 letters chosen from A, B, C, D, E with no letter repeated. How many codes are there?

Permutations and combinations

Use permutations when order matters and combinations when it does not.

A permutation is an arrangement where order matters. Choosing and arranging rr items from nn gives nPr=n!(n−r)!^nP_r=\frac{n!}{(n-r)!}.

A combination is a selection where order does not matter: (nr)=n!r!(n−r)!\binom nr=\frac{n!}{r!(n-r)!}.

Always nPr=r!×(nr)^nP_r=r!\times\binom nr.

Decide by asking: would swapping two chosen items give a different outcome? If yes, use nPr^nP_r.

Permutation

Order matters?:
Yes
Formula:
nPr=n!(n−r)!^nP_r=\frac{n!}{(n-r)!}
Four from a committee of 12:
four posts: 12P4=11 880^{12}P_4=11\,880

Combination

Order matters?:
No
Formula:
(nr)=n!r!(n−r)!\binom nr=\frac{n!}{r!(n-r)!}
Four from a committee of 12:
no roles: (124)=495\binom{12}{4}=495

A prize draw picks 3 winners from 10 people. Each wins the same prize. How many outcomes?

Subsets of a set

A set with nn elements has 2n2^n subsets, because each element is either in or out.

A set with nn elements has 2n2^n subsets, including the empty set and the set itself.

The number of subsets with exactly rr elements is (nr)\binom nr. Excluding the empty set leaves 2n−12^n-1.

A group chosen from 1010 athletes has 210−1=10232^{10}-1=1023 possibilities if it must be non-empty.

Forgetting that 2n2^n includes the empty set is a common slip, as it is often not allowed.

  • All subsets of nn elements2n2^n
  • Non-empty subsets2n−12^n-1

How many subsets does {a, b, c, d} have that contain at least one element?

Addition and subtraction principles

Add the counts of exclusive cases; for "at least one", subtract the opposite case from the total.

If a task can be done in one of several ways that cannot happen together, add the numbers (the addition principle).

For "at least" questions it is often easier to subtract the opposite case from the total.

PINs with at least one 77: 104−94=343910^4-9^4=3439.

Teams of 1111 from 22 goalkeepers and 1919 outfield players with at least one goalkeeper: (2111)−(1911)=352 716−75 582=277 134\binom{21}{11}-\binom{19}{11}=352\,716-75\,582=277\,134.

  • At least onetotal −- none

Worked example

How many positive integers less than 1000 contain the digit 3 at least once?

How many 3-digit strings (000 to 999) contain at least one 5?

Combined counting problems

Choose first, then arrange; for "at least kk", split into cases and add.

Many problems join the principles: choose first, then arrange.

For "at least kk" of a type, make a case split (exactly kk, exactly k+1k+1, and so on) and add.

At least 33 girls in a training group chosen from 44 girls and 66 boys, where any number of boys may join: choose 33 or 44 girls and any subset of the boys, so (43)26+(44)26=320\binom43 2^6+\binom44 2^6=320.

Split into non-overlapping cases; counting the same selection twice is a common mistake.

  1. 1

    Choose

    use combinations for each group

  2. 2

    Multiply

    the choices for each group

  3. 3

    Arrange

    multiply by the orders if order matters

A combined count.

Worked example

A relay team of 4 is chosen from 4 girls and 6 boys with exactly 2 girls. How many teams can be made, with the order of running counted?

Choose 3 people from 5 men and 4 women with exactly 1 woman. How many ways?

Try an exam question

A committee of 4 is chosen from 5 men and 6 women. Find the number of committees that contain at least one man.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

In how many ways can a committee of 4 members, with no special roles, be chosen?

1 mark, marked against the mark scheme

Revision notes