Combinations


Martin McBride, 2021-11-04
Tags combinations
Categories statistics probability

Combinations are similar to permutations. The difference is that, with combinations, the order of the items doesn't matter.

Example of combinations

One example of combinations is the National Lottery. The machine has 59 balls, numbered 1 to 59. In the game, 6 balls are chosen.

It doesn't matter which order the balls are drawn, if the 6 numbers match your ticket you will win. If the numbers are drawn in the order (10, 17 45, 23, 52, 36) the result is exactly the same as the numbers being drawn in the order (45, 52, 17, 36, 10, 23). The two situations are considered identical in terms of the final result.

In other words

  • (10, 17 45, 23, 52, 36) and (45, 52, 17, 36, 10, 23) are identical combinations, because each set contains the same numbers.
  • But they are different permutations, because the numbers are in a different order.

Calculating the number of combinations

In the article on permutations, we used an example of 5 different coloured counters - red, yellow, green, blue, and black.

If we pick 3 of the counters at random, how many possible combinations are there?

We know that the number of permutations of 3 elements from 5 is:

$$ \frac {n!}{(n-r)!} = \frac {5!}{2!} = 60 $$

However, some of these different permutations are the same combination. For example the permutations RGB, GRB and BGR are all the same combination of a red, a green, and a blue counter.

In fact, for every combination of 3 counters, there are 3 factorial permutations. So to obtain the current number of combinations we must divide the number of permutations by 3 factorial (in more generally r factorial):

$$ \frac {n!}{r!(n-r)!} = \frac {5!}{3!.2!} = 10 $$

Symmetry

The number of combinations of r items from n is equal to the number of combinations of (n-r) items from n.

This can be seen intuitively, as follows. Using the previous example, whenever we take a combination of 3 counters, we leave 2 counters behind. For each unique combination of 3 counters, there is a corresponding unique combination of the remaining 2 counters. So the number of combinations of 3 counters from 5 is equal to the number of combinations of 2 counters from 5.

Alternatively, we can show this from the equation:

$$ \frac {n!}{r!(n-r)!} $$

If we replace r with (n - r) we get:

$$ \frac {n!}{(n-r)!(n-(n-r))!} = \frac {n!}{(n-r)!r!} = \frac {n!}{r!(n-r)!} $$

Combinations with repeats

In the previous example, we were selecting r objects from a set of n unique objects. No object can appear more than once in the combination. The same Lottery ball can't be drawn twice.

In this section, we will consider the case where repeats are allowed. For example, throwing a dice 10 times, and writing down the result each time. Clearly, the same number can appear more than once in the result. How many combinations are possible?

In this case, n is 6 because there are 6 possible scores. r is 10 because we throw the dice 10 times.

The solution to this requires us to look at the problem in a slightly different way. We could create a table of the number of times each score appears. For example:

Score 1 2 3 4 5 6
Count 2 1 1 3 2 1

This table shows that, when we threw the dice 10 times, it came up as 1 twice, it never came up as 2, it came up as 3 twice, and so on. The total of all the counts must be 10 because we threw the dice 10 times.

Here is another way of representing the table:

Score 1 2 3 4 5 6
Count XX X X XXX XX X

The number of 'X' characters represent the number of throws with that particular score.

We can avoid the table altogether by using a different character ':' to separate the X characters.

XX:X:X:XXX:XX:X

This set of characters contains 10 'X' characters (each representing a throw of the dice). It contains 5 ':' characters to divide the 'X' characters into 6 groups. In terms of n and r:

  • The number of 'X' characters is r.
  • There number of ':' characters is n - 1.

The key thing here is that every possible combination of dice scores is represented by a unique permutation of the characters. In fact, there is a one-to-one correspondence.

The string 'XX:X:X:XXX:XX:X' represents the scores in order 1 to 6. It doesn't depend on the order of the scores, so it represents a unique combination.

This means that the number of combinations of dice throws is the same as the number of permutations of 10 'X' and 5 ':' characters. In the section on permutations we saw that the formula for the number of permutations of a binary set is:

$$ \frac {n!}{c!(n-c)!} $$

In this case, the total number of 'X' and ':' characters is n + r - 1. Substituting this for n in the formula above gives a formula for the number of combinations of r objects from a set of n unique objects, with repeats allowed as:

$$ \frac {(n-r-1)!}{r!(n-1)!} $$

If you found this article useful, you might be interested in the book Computer Graphics in Python or other books by the same author.

Prev

Popular tags

2d arrays abstract data type alignment and animation arc array arrays behavioural pattern bezier curve built-in function callable object chain circle classes clipping close closure cmyk colour combinations comparison operator comprehension context context manager conversion count creational pattern data types design pattern device space dictionary drawing duck typing efficiency ellipse else encryption enumerate fill filter font font style for loop function function composition function plot functools game development generativepy tutorial generator geometry gif gradient greyscale higher order function hsl html image image processing imagesurface immutable object index inner function input installing iter iterable iterator itertools l system lambda function len line linear gradient linspace list list comprehension logical operator lru_cache magic method mandelbrot mandelbrot set map monad mutability named parameter numeric python numpy object open operator optional parameter or partial application path pattern permutations polygon positional parameter print pure function python standard library radial gradient range recipes rectangle recursion reduce repeat rgb rotation roundrect scaling sector segment sequence setup shape singleton slice slicing sound spirograph sprite square str stream string stroke structural pattern subpath symmetric encryption template text text metrics tinkerbell fractal transform translation transparency triangle tuple turtle unpacking user space vectorisation webserver website while loop zip