Combinations (DP IB Analysis & Approaches (AA): HL): Revision Note

Combinations

What is a combination?

• A combination is the number of ways to select $r$ objects out of $n$ different objects, where the order does not matter

  • e.g. selecting Ravi, Euan and Jess out of 10 possible students to work together in a small group is a combination

    • The order of ' Ravi / Euan / Jess' does not matter

What is the difference between a combination and a permutation?

• In a permutation the order matters

  • but in a combination, the order does not matter

• e.g. selecting 4 paints out of 9 different paints to mix together and form a new colour is an example of a combination

  • the order of the 4 paints does not matter

    • as they all get mixed together

• However selecting 4 paints out of 9 different paints to colour four different regions on a flag is an example of a permutation

  • the order matters

    • e.g. a flag starting with red looks different to a flag starting with blue

What is  ${}_{\mathit{ }}{}^{\mathit{n}}{\mathbf{C}}_r$?

• ${}_{ }{}^n{\mathrm{C}}_r$ stands for the number of ways to select $r$ objects out of $n$ different objects when order does not matter

  • and where $0\le r\le n$

• The formula is ${}_{ }{}^n{\mathrm{C}}_r=\frac{n!}{r!\left(n-r\right)!}$

  • Note that it is not possible to select repeated objects when using ${}_{ }{}^n{\mathrm{C}}_r$

• e.g. how many teams of 4 people can be made out of 12 people?

  • Each of the 12 people are different

  • You are selecting $r=4$ out of $n=12$

  • Order does not matter

    • A team with X, Y and Z in it is the same as a team with Z, Y and X in it

  • so ${}_{ }{}^{12}{\mathrm{C}}_4=\frac{12!}{4!\left(12-4\right)!}=\frac{12!}{4!8!}$

  • This can be simplified by cancelling

    • $\frac{12\times 11\times 10\times 9\times \cancel{8\times 7\times ...}}{4\times 3\times 2\times 1\times \cancel{8\times 7\times ...}}=...=495$

What properties of ${}_{\mathit{ }}{}^{\mathit{n}}{\mathbf{C}}_r$ do I need to know?

• Useful properties of ${}_{ }{}^n{\mathrm{C}}_r$ to know are

  • $0\le r\le n$

  • ${}_{ }{}^n{\mathrm{C}}_0=1$

    • note that $0!=1$

  • ${}_{ }{}^n{\mathrm{C}}_n=1$

  • The numbers ${}_{ }{}^n{\mathrm{C}}_0,{}_{ }{}^n{\mathrm{C}}_1,{}_{ }{}^n{\mathrm{C}}_2,...,{}_{ }{}^n{\mathrm{C}}_{n-2},{}_{ }{}^n{\mathrm{C}}_{n-1},{}_{ }{}^n{\mathrm{C}}_n$ are symmetric

    • i.e. ${}_{ }{}^n{\mathrm{C}}_r={}_{ }{}^n{\mathrm{C}}_{n-r}$

How is the ${}_{\mathit{ }}{}^{\mathit{n}}{\mathbf{P}}_r$ formula related to the ${}_{\mathit{ }}{}^{\mathit{n}}{\mathbf{C}}_r$ formula?

• ${}_{ }{}^n{\mathrm{P}}_r=\frac{n!}{\left(n-r\right)!}$ and ${}_{ }{}^n{\mathrm{C}}_r=\frac{n!}{r!\left(n-r\right)!}$

  • so ${}_{ }{}^n{\mathrm{P}}_r=r!\times {}_{ }{}^n{\mathrm{C}}_r$

• This means ${}_{ }{}^n{\mathrm{P}}_r$ is $r!$ times bigger than ${}_{ }{}^n{\mathrm{C}}_r$

• This is true because ${}_{ }{}^n{\mathrm{P}}_r$ is the number of ways to select $r$ objects out of $n$ different objects where order matters

  • i.e. after you select $r$ objects out of $n$

    • i.e. ${}_{ }{}^n{\mathrm{C}}_r$

  • you then find all the possible rearrangements of those $r$ objects

    • i.e. multiply by $r!$ rearrangements

When do I multiply  ${}_{\mathit{ }}{}^{\mathit{n}}{\mathbf{C}}_r$ values together?

• If asked to find combinations out of subgroups of the $n$ different objects, multiply together the ${}_{ }{}^n{\mathrm{C}}_r$ values

• e.g. in a class of 20 students, 5 students are left-handed and the rest are right-handed. How many ways can a team of 6 students be formed in which 2 are left-handed?

  • Out of the 5 left-handed students, select 2

    • ${}_{ }{}^5{\mathrm{C}}_2$

  • Out of the 15 right-handed students, select 4

    • ${}_{ }{}^{15}{\mathrm{C}}_4$

  • Multiply these values together

    • ${}_{ }{}^5{\mathrm{C}}_2\times {}_{ }{}^{15}{\mathrm{C}}_4$ ways