Selections (VCE SSCE Mathematical Methods): Revision Notes

Selections

Understanding selections

When counting objects, sometimes we only care about which items are chosen, not the order they're in. This is different from arrangements, where order matters.

Consider the letters $A$, $B$, $C$ taken in groups of two. There are six possible arrangements: $AB$, $BA$, $AC$, $CA$, $BC$, $CB$. However, there are only three distinct selections: $\{A, B\}$, $\{A, C\}$, $\{B, C\}$.

When order doesn't matter, we call these selections or combinations.

The combination notation

We use the notation $^nC_r$ to represent the number of different ways to choose groups of size r from a total of n objects when order is unimportant.

An alternative notation you might see is $\binom{n}{r}$.

Deriving the combination formula

When the number of objects is small, we can list all combinations. For larger groups, we need a formula.

Consider choosing five colours from eight available colours (like on the Olympic flag). We can think of this as a two-step process: first choose the colours, then arrange them.

This gives us:

Choose the colours, then arrange them to get possible arrangements

$$^8C_5 \times 5! = \frac{8!}{3!}$$

Since $^8C_5 \times 5! = \frac{8!}{3!}$, we can find $^8C_5$ by dividing both sides by $5!$:

$$^8C_5 = \frac{8!}{3! \times 5!}$$

Notice that the two numbers on the bottom line (3 and 5) add to 8.

The combination formula

In general, the number of combinations of n objects in groups of size r is:

$$^nC_r = \frac{^nP_r}{r!} = \frac{n \times (n-1) \times (n-2) \times \cdots \times (n-r+1)}{r!} = \frac{n!}{r!(n-r)!}$$

Selecting from separate groups

When selecting from distinct groups, calculate the selections for each group separately, then use the multiplication rule to combine them.

Selections of any size

When counting all possible selections from a group of $n$ objects (including selecting none), we have a useful formula:

$$^nC_0 + ^nC_1 + ^nC_2 + \cdots + ^nC_{n-1} + ^nC_n = 2^n$$

Understanding the $2^n$ formula

Let's see why this works using three books: $A$, $B$, and $C$. David can choose whichever books he likes, including none.

The set $S = \{A, B, C\}$ has these subsets:

$\emptyset$, $\{A\}$, $\{B\}$, $\{C\}$, $\{A,B\}$, $\{A,C\}$, $\{B,C\}$, $\{A,B,C\}$

This gives eight choices.

Method 1: Focus on how many books David chooses

He can choose:

• 0 books in $^3C_0 = 1$ way (corresponds to $\emptyset$)
• 1 book in $^3C_1 = 3$ ways (corresponds to $\{A\}$, $\{B\}$, $\{C\}$)
• 2 books in $^3C_2 = 3$ ways (corresponds to $\{A,B\}$, $\{A,C\}$, $\{B,C\}$)
• 3 books in $^3C_3 = 1$ way (corresponds to $\{A,B,C\}$)

By the addition rule, total choices = $^3C_0 + ^3C_1 + ^3C_2 + ^3C_3$

Method 2: Focus on each book individually

For each book, David has 2 choices: choose it or don't choose it.

• Book $A$: chosen or not (2 ways)
• Book $B$: chosen or not (2 ways)
• Book $C$: chosen or not (2 ways)

By the multiplication rule, total choices = $2 \times 2 \times 2 = 2^3$

Therefore: $^3C_0 + ^3C_1 + ^3C_2 + ^3C_3 = 2^3$

This argument extends to any number of objects.

Pascal's triangle

Pascal's triangle is a pattern showing combination values. Each row corresponds to selections from $n$ objects.

This triangle is named after French mathematician Blaise Pascal, who used it extensively in probability studies.

Pattern in Pascal's triangle

The triangle continues indefinitely following these rules:

Pascal's identity

The pattern in Pascal's triangle is explained by this identity:

Proof of Pascal's identity

Using the combination formula:

$$^{n-1}C_{r-1} + ^{n-1}C_r = \frac{(n-1)!}{(n-r)!(r-1)!} + \frac{(n-1)!}{(n-1-r)!r!}$$ $$$$ $$$$ $$$$ $$$$

This proves that each number in Pascal's triangle equals the sum of the two numbers above it.