Permutations

A permutation is a re-ordering of a set of items. If we had a set of three items such as tea, coffee and sugar, for example, we could order these three items in six ways, i.e. {tea, coffee, sugar}, {tea, sugar, coffee}, {coffee, tea, sugar}, {coffee, sugar, tea}, {sugar, tea, coffee} and {sugar, coffee, tea}. More generally, if we had \(N\) items we could order them in \(N!\) ways or \(N \times (N-1) \times (N-2) \times \ldots 2 \times 1\). This is because if you had \(N\) items, there are \(N\) possibilities for the first item in the ordering, there are \(N-1\) possibilities for the second, and so on.

We can also talk about the permutations of \(N\) items taken \(n\) at a time. For example, let’s say we have a class with 28 students. One desk in the classroom has six seats. How many ways are there for how we could seat different groups of students at this desk? Any one of the 28 students could sit on the first chair. Then any one of 27 students could sit on the second chair, and so on until we have 23 possible students left who could sit on the sixth and final chair. In general, the number of permutations of \(N\) items taken \(n\) at a time is \[\begin{aligned} \mathrm{Perm}(N,n) &= N \times (N-1) \times \ldots \times (N-n+1),\\ &= \frac{N \times (N-1) \times (N-2) \times \ldots 2 \times 1}{ (N-n) \times (N-n-1) \times (N-n-2) \times \ldots 2 \times 1},\\ &= \frac{N!}{(N-n)!}.\end{aligned}\]

Combinations

In contrast to a permutation, a combination is a way of selecting a subset of items from a larger set, but where the ordering of the subset is irrelevant. For example, if we have a set of \(N\) items, how many ways could we choose \(n\) items from this set (assuming \(n<N\)). This number is related to \(\mathrm{Perm}(N,n)\). In the example above, we have seen that there are \(28 \times 27 \times \ldots \times 23\) ways that we could seat 28 students at a desk with 6 seats. This takes into account the order in which each possible group of six students are seated. If do not care who sits where, but just whether a given student is seated at the desk or not, then we can divide the number of permutations by the number of ways of ordering each group of 6 students. This is \(6 \times 5 \times 4 \times 3 \times 2 \times 1\) or \(6!\). In other words, the number of ways we could select a subset of 6 students from a group of 28 is \[\mathrm{Comb}(28,6) = \frac{28 \times 27 \times \ldots \times 23}{6 \times 5 \times 4 \times 3 \times 2 \times 1},\] and in general, \[\begin{aligned} \mathrm{Comb}(N,n) &= \frac{\mathrm{Perm}(N,n)}{n!},\\ &= \frac{N!}{n!(N-n)!}.\end{aligned}\] The term \(\mathrm{Comb}(N,n)\) is very commonly written as \(\tbinom{N}{n}\), and read as “N choose n”.

Permutations and combinations using R

Permutations and combinations ultimately just involve products and ratios of factorials. In R, we can calculate the factorial of any number using factorial. For example,

x <- c(5, 3, 11) # just arbitrarily chosen numbers
factorial(x)     # their factorials
## [1]      120        6 39916800

The problem is that factorials can get large very quickly, and this can lead to overflow. We can try to avoid this by using logarithms of the factorials. For example,

lfactorial(x)     # the logarithms of the factorials of x
## [1]  4.787492  1.791759 17.502308

In fact, R provides logarithms of the \(\mathrm{Comb}(N,n)\) function above as follows:

lchoose(12, 3)    # the logarithm of 12 choose 3
## [1] 5.393628

We can then define our own permutations and combination functions:

permutation = function(N, m, as_log=F) {
  log_perm <- lfactorial(N) - lfactorial(N-m)
  ifelse(as_log, log_perm, exp(log_perm))
}

combination = function(N, m, as_log=F) {
  log_comb <- lchoose(N, m)
  ifelse(as_log, log_comb, exp(log_comb))
}

We’ll test this out with some of the calculations above:

permutation(59, 6)
## [1] 32441381280

and

combination(59, 6)
## [1] 45057474

If you like commas to help read any numbers with around 6 or more numbers you can do the following:

permutation(59, 6) %>% format(big.mark=',')
## [1] "32,441,381,280"

and

combination(59, 6) %>% format(big.mark=',')
## [1] "45,057,474"