Combinations and Permutations

Combinations and Permutations describe sets of objects that can be drawn from a population.  In a combination, sequence is not important, thus AB and BA are the same combination of A and B whilst AB and BA are different permutations.

Formula

The formula for the number of combinations and permutations of x objects from a population of size n is shown below:

For a given value of set size and population, there are always more permutations than combinations

Example

A population consists of five items A, B, C, D and E. Two items are drawn drawn from this population, the number of combinations and permutations is:

The combinations are:

AB, AC, AD, AE

BC, BD, BE

CD, CE

DE

The permutations are:

AB, AC, AD, AE, BA, CA, DA, EA

BC, BD, BE, CB, DB, EB

CD, CE, DC, EC

DE, ED

Spreadsheets

The combin and permut functions in MS Excel and Google Docs perform the combinations and permutation calculations respectively.

combin(5,2) returns 10

permut(5,2) returns 20

Application

Soccer leagues provides an intuitive example of combinations and permutations.

In a soccer league each team plays every other team under the same conditions the same number of times.  If all the matches are played on a single ground, there is no distinction between home and away games.  Thus the number of  games played is the number of combinations of two teams from the total number of teams in the league.  Thus if there are 10 teams in the league, the number of matches will be:

C(10,2) = 45

However, in many leagues, clubs have their own grounds and play half their games at home and half away.  Looking at results tables, it is clear that the home team has an advantage (Very roughly, the results from the major UK leagues are 50% home win, 25% draw and 25% away win).  Thus to be fair, each team must play every other team at home and away, thus the number of matches will be the number of permutations:

P(10,2) = 90

In the case of a small league of say 10 teams, in order to provide enough games to occupy a nine month season of 5 games/week, the permutations can be repeated twice making a total of 180 games.