Combinations

 

Combinations (Unordered Selections)

A combination of n objects taken r at a time is a selection which does not take into account the arrangement of the objects. That is, the order is not important.

Example 1

Consider the selection of a set of 4 different letters from the English alphabet.

Suppose

• David selected A, E, R, T;
• Karen selected D, E, N, Q; and
• John selected R, E, A, T

Note: David and John selected the same set of letters, even though they selected them in different order. Hence, these 3 people have selected only 2 different sets of 4 letters (not 3 sets!!).

Question: How many different sets of 4 letters can be selected from the alphabet?

We will use permutations from the previous section to see what is going on.

There are $\displaystyle{{P}_{{4}}^{{26}}}$ ways of arranging any $\displaystyle{4}$ letters chosen from the alphabet (where the order is important):

$\displaystyle{{P}_{{4}}^{{26}}}$ $\displaystyle=\frac{{{26}!}}{{{\left({26}-{4}\right)}!}}$ $\displaystyle=\frac{{{26}!}}{{{22}!}}$ $\displaystyle={358800}$

But in this question, the order is not important. Any set of $\displaystyle{4}$ letters chosen can be arranged in $\displaystyle{4}!$ ways.

Hence, the number of different sets of $\displaystyle{4}$ letters is

$\displaystyle\frac{{{{P}_{{4}}^{{26}}}}}{{{4}!}}$ $\displaystyle=\frac{358800}{{24}}$ $\displaystyle={14950}$

Number of Combinations

The number of ways (or combinations) in which r objects can be selected from a set of n objects, where repetition is not allowed, is denoted by:

$\displaystyle{{C}_{{r}}^{{n}}}=\frac{{{n}!}}{{{r}!{\left({n}-{r}\right)}!}}$

Notes

(a) $\displaystyle{{C}_{{r}}^{{n}}}=\frac{{{{P}_{{r}}^{{n}}}}}{{{r}!}}$

(b) $\displaystyle{{C}_{{0}}^{{n}}}={1}$

(c) $\displaystyle{{C}_{{n}}^{{n}}}={1}$

(d) $\displaystyle{{C}_{{r}}^{{n}}}={{C}_{{{n}-{r}}}^{{n}}}$

Expand each one out from their definitions to understand why they work.

In our example above, the number of different sets of $\displaystyle{4}$ letters which can be chosen from the alphabet is

$\displaystyle{{C}_{{4}}^{{26}}}$ $\displaystyle=\frac{{{26}!}}{{{4}!{\left({26}-{4}\right)}!}}$ $\displaystyle=\frac{{{26}!}}{{{4}!{22}!}}$ $\displaystyle={14950}$

Example 2

Find the number of ways in which $\displaystyle{3}$ components can be selected from a batch of $\displaystyle{20}$different components.

ANSWER

$C_3^{20}$ $\displaystyle=\frac{{{20}!}}{{{3}!{\left({20}-{3}\right)}!}}$ $\displaystyle=\frac{{{20}!}}{{{3}!{17}!}}$ $\displaystyle={1140}$

Example 3

In how many ways can a group of $\displaystyle{4}$ boys be selected from $\displaystyle{10}$ if

(a) the eldest boy is included in each group?

(b) the eldest boy is excluded?

(c) What proportion of all possible groups contain the eldest boy?

ANSWER

(a) Choose $\displaystyle{3}$ from $\displaystyle{9}$, since the eldest boy is fixed:

$\displaystyle{{C}_{{3}}^{{9}}}$ $\displaystyle={\frac{{{9}!}}{{{3}!{\left({9}-{3}\right)}!}}}$ $\displaystyle={\frac{{{9}!}}{{{3}!\times{6}!}}}$ $\displaystyle={84}$

(b) If the eldest boy is excluded, it is actually choose $\displaystyle{4}$ boys from $\displaystyle{9}$:

$\displaystyle{{C}_{{4}}^{{9}}}$ $\displaystyle={\frac{{{9}!}}{{{4}!{\left({9}-{4}\right)}!}}}$ $\displaystyle={\frac{{{9}!}}{{{4}!\times{5}!}}}$ $\displaystyle={126}$

(c) The number of all possible groups is

$\displaystyle{{C}_{{4}}^{{10}}}={\frac{{{10}!}}{{{4}!\times{6}!}}}={210}$

So the proportion of all possible groups containing the eldest boy is:

$\displaystyle{\frac{{{84}}}{{{210}}}}=\frac{2}{{5}}={40}\%$

Example 4

A class consists of $\displaystyle{15}$ boys of whom $\displaystyle{5}$ are prefects.

How many committees of $\displaystyle{8}$ can be formed if each consists of

(a) exactly $\displaystyle{2}$ prefects? (b) at least $\displaystyle{2}$ prefects?

ANSWER

The number of ways of choosing $\displaystyle{2}$ prefects from $\displaystyle{5}$ is $\displaystyle{{C}_{{2}}^{{5}}}={\frac{{{5}!}}{{{2}!\times{3}!}}}={10}$

The number of ways of choosing $\displaystyle{6}$ non-prefects from $\displaystyle{10}$ is

$\displaystyle{{C}_{{6}}^{{10}}}={\frac{{{10}!}}{{{6}!\times{4}!}}}={210}$

(a) Number of possible committees with exactly $\displaystyle{2}$ prefects:

$\displaystyle{{C}_{{2}}^{{5}}}\times{{C}_{{6}}^{{10}}}={10}\times{210}={2100}$

(b) Number of committees with $\displaystyle{3}$ prefects:

$\displaystyle{{C}_{{3}}^{{5}}}\times{{C}_{{5}}^{{10}}}$ $\displaystyle={\frac{{{5}!}}{{{3}!\times{2}!}}}\times{\frac{{{10}!}}{{{5}!\times{5}!}}}$ $\displaystyle={2520}$

Number of committees with $\displaystyle{4}$ prefects:

$\displaystyle{{C}_{{4}}^{{5}}}\times{{C}_{{4}}^{{10}}}$ $\displaystyle={\frac{{{5}!}}{{{4}!\times{1}!}}}\times{\frac{{{10}!}}{{{4}!\times{6}!}}}$ $\displaystyle={1050}$

Number of committees with $\displaystyle{5}$ prefects:

$\displaystyle{{C}_{{5}}^{{5}}}\times{{C}_{{3}}^{{10}}}$ $\displaystyle={\frac{{{5}!}}{{{5}!\times{0}!}}}\times{\frac{{{10}!}}{{{3}!\times{7}!}}}$ $\displaystyle={120}$

So the number of committees with at least $\displaystyle{2}$ prefects is:

$\displaystyle{2100}+{2520}+{1050}+{120}={5790}$

Alternative Solution:

The problem with the method used above is that if we have many (say $\displaystyle{20}$) to count, it would become very tedious. So we look at another way of doing it.

If we find the number of committees with $\displaystyle{0}$ prefects and $\displaystyle{1}$ prefect, and subtract this from the total number of committees, we will have the number with at least $\displaystyle{2}$:

Number of committees with $\displaystyle{0}$ prefects:

$\displaystyle{{C}_{{8}}^{{10}}}={\frac{{{10}!}}{{{8}!\times{2}!}}}={45}$

Number of committees with $\displaystyle{1}$ prefect:

$\displaystyle{{C}_{{1}}^{{5}}}\times{{C}_{{7}}^{{10}}}={\frac{{{5}!}}{{{1}!\times{4}!}}}\times{\frac{{{10}!}}{{{7}!\times{3}!}}}={600}$

The total number of committees is:

$\displaystyle{{C}_{{8}}^{{15}}}={\frac{{{15}!}}{{{8}!{\left({15}-{8}\right)}!}}}={\frac{{{15}!}}{{{8}!\times{7}!}}}={6435}$

So the number with at least $\displaystyle{2}$ prefects is given by:

$\displaystyle{6435}-{45}-{600}={5790}$

 Example 5

Out of $\displaystyle{5}$ mathematicians and $\displaystyle{7}$ engineers, a committee consisting of $\displaystyle{2}$ mathematicians and $\displaystyle{3}$ engineers is to be formed. In how many ways can this be done if

(a) any mathematician and any engineer can be included?

(b) one particular engineer must be in the committee?

(c) two particular mathematicians cannot be in the committee?

ANSWER

(a) $\displaystyle{{C}_{{2}}^{{5}}}\times{{C}_{{3}}^{{7}}}={\frac{{{5}!}}{{{2}!\times{3}!}}}\times{\frac{{{7}!}}{{{3}!\times{4}!}}}={350}$

(b) $\displaystyle{{C}_{{2}}^{{5}}}\times{{C}_{{2}}^{{6}}}={\frac{{{5}!}}{{{2}!\times{3}!}}}\times{\frac{{{6}!}}{{{2}!\times{4}!}}}={150}$

(c) $\displaystyle{{C}_{{2}}^{{3}}}\times{{C}_{{3}}^{{7}}}={\frac{{{3}!}}{{{2}!\times{1}!}}}\times{\frac{{{7}!}}{{{3}!\times{4}!}}}={105}$