Combinations

Have you ever seen a lotto draw? Let's explore what happens with a simplified version of the game.

In our lotto game, three balls are chosen at random out of a barrel of 20 balls. Let's suppose the balls are numbered \(1, 23\) and \(36\). It doesn't matter what order they come out of the barrel in. They could arrive in any of the following orders:

• 1, 23, 36
• 1, 36, 23
• 23, 1 ,36
• 23, 36, 1
• 36, 1, 23
• 36, 23, 1

All six orders give us the same set of \(3\) numbers. We can't repeat any of the three numbers, but we don't care what order they arrive in.

Our list of 6 possible orders is a list of permutations of these numbers. If you don't remember much about permutations, it might be a good idea to read the article on arrangements of objects in lines.

Our single set of \(3\) numbers is an example of what we call a combination. Repetition is not allowed, and order does not matter. By forgetting about the order, we have reduced the number of possible sets of numbers by a factor of \(3!\), which is the number of arrangements of the three numbers in a straight line.

This idea gives us a way to calculate the number of combinations of \(r\) objects out of a set of \(n\) objects. That is, the number of ways of selecting \(r\) objects out of a set of \(n\) objects, where order does not matter and repetition is not allowed. To calculate how many combinations there are we

1. Work out how many ways there are of arranging \(r\) of the \(n\) objects in a line without repetition (\({}^nP_r\))
2. Divide by the number of ways of arranging the \(r\) objects in a line without repetition (\(r!\))

So, our total number of combinations is given by the formula

Different mathematicians use different notation for this formula, but they all mean the same thing:

Each one of them refers to the number of ways of choosing \(r\) objects out of a set of \(n\) objects, where order does not matter and repetition is not allowed.

Example

Fun Facts about the Combinations Formula

The combinations formula is symmetric:

so,

We can read the value of \(\begin{pmatrix}n\\r\end{pmatrix}\) from Pascal's triangle: if we number the rows, starting with 0, then \(\begin{pmatrix}n\\r\end{pmatrix}\) is the rth entry of row number n.

\(\begin{pmatrix}n\\r\end{pmatrix}\) is the number of subsets with \(r\) elements of a set of \(n\) elements.

Multi-sets: "Combinations" with Repetition

This is pretty tricky stuff, but it's included here for completeness. Let's suppose you want to allow repetition in your set, but the order of selection still doesn't matter.

For example, you might be making a selection of 20 gummi-bears from a collection of gummi-bears with 6 different colours. If you allow yourself to choose two or more of the same colour, you end up with a multi-set, which is mathematician talk for a set with repeated elements.

How do we go about counting the number of selections of gummi bears now?

Well, we have to think about the problem slightly differently. We have 20 different slots to fill with 6 different colours of lollies. As well as counting the number of copies of each colour, we also need to count the transitions between each colour. If there are 6 colours, there are \(6 - 1 = 5\) of these. So, we actually need to select \(20\) out of \(20 + 6 - 1\) objects. This can be done in

ways. In general, the number of ways to select \(r\) objects from a set of \(n\) objects, where repetition is allowed and order does not matter is given by the formula

Conclusion

Many people find counting very challenging. Don't be discouraged. The best thing you can do is to get lots of practice. Keep trying, but remember:

• Use combinations when order does not matter and repetition is not allowed.
• Use permutations when order matters and repetition is not allowed.