Combinations and Permutations in R

Intro

Combinatorics is one of the cornerstones of mathematics. Many problems start or are solved by counting the number of possibility. Probability theory is built on these tools. R provides us with many ways to count using permutations and combinations. There are options to use with and without repetitions and much more. In this article, we will learn how to count the number of permutations and combinations in R.

Permuations with Repeition

An example of permutations with repetition is counting the number of possible lock combinations. Think about a safe lock where there are 3 possible numbers. Each number can be from 0-9 and you are allowed to reuse the numbers and order matters, thus it is a permutation. Let’s see to count these combinations in R.

To calculate the total number of permutations with repetition, we use the simple formula n^r. Thus, to solve our problem above, we can use the following.

10^3

## [1] 1000

So there are 1,000 possible combinations for our lock. Let’s say we want to generate each of these combinations to visualize them. A helpful tool for this is gtools. We can install it by uncommenting and running the following.

# install.packages('gtools')

library(gtools)

Now, we can use the permutations function to generate all possible lock combinations.

# R starts with 1, so we need to create a list of 0 to 10
choices = c(0:9)

# n is the number of options, r is the number of groups, v is the value of our choices
res = permutations(n = 10, r = 3, v = choices, repeats.allowed = TRUE)

# Only show the head as there are many options
head(res)

##      [,1] [,2] [,3]
## [1,]    0    0    0
## [2,]    0    0    1
## [3,]    0    0    2
## [4,]    0    0    3
## [5,]    0    0    4
## [6,]    0    0    5

We can confirm the count is the same by counting the rows from the matrix above.

nrow(res)

## [1] 1000

As we can see there are 1000 rows which is the same as we calculated above.

Permuations without Repetition

Now we move on to permutations without repetition. This means that the choice we have gets smaller each time. For example, let’s say for our lock combination above, we had to select 3 unique numbers each time. The calculation for this would be:

9 * 8 * 7 = 504

Without getting two in the weeds, the mathematical way to calculate this is:

Which is basically saying select all possible permutations of the 9 groups, but remove 6 groups as we only want 3 choices (our lock is a 3 slot combination). In the equation above, 6-1 cancel out. The cool mathy notation for this is.

Where n is the number of possible choices and r is the number of choices. So we can calculate this in R like so.

n = 9
r = 3

factorial(n) / factorial(n - r)

## [1] 504

If we would like to see all the possible permutations, we can use our permutations function again, but set the repeats.allowed = FALSE.

# R starts with 1, so we need to create a list of 0 to 10
choices = c(0:9)

# n is the number of options, r is the number of groups, v is the value of our choices
res = permutations(n = 10, r = 3, v = choices, repeats.allowed = FALSE)

# Only show the head as there are many options
head(res)

##      [,1] [,2] [,3]
## [1,]    0    1    2
## [2,]    0    1    3
## [3,]    0    1    4
## [4,]    0    1    5
## [5,]    0    1    6
## [6,]    0    1    7

Combinations without Repetition

Now, let’s move on to combinations. We will start without repetition as that is a bit easier. The difference between combinations and permutations is that order does not matter for combinations. For example, let’s say we want to know the combinations of of cards in a 5 card hand. In general, the order doesn’t matter. You can have a pair of 3’s (one clubs and one hearts, for example) and it doesn’t matter which 3 comes first.

The formula for combinations without repetition is:

The formula is similar to permutations but with an extra divisor, r!. So, to calculate the number of 5 card hands we can use R’s built in function, choose or calculate it manually.

n = 52
r = 5

factorial(n) / (factorial(n - r) * factorial(r))

## [1] 2598960

choose(n = n, k = r)

## [1] 2598960

We can see the combinations using the combinations function from gtools.

n = 52
r = 5

c.res = combinations(n, r, repeats.allowed=FALSE)
head(c.res)

##      [,1] [,2] [,3] [,4] [,5]
## [1,]    1    2    3    4    5
## [2,]    1    2    3    4    6
## [3,]    1    2    3    4    7
## [4,]    1    2    3    4    8
## [5,]    1    2    3    4    9
## [6,]    1    2    3    4   10

Combinations without Repetition

Our final section is about combinations with replacement. Let’s start again with the formula.

We can caluclate this in R using the following:

n = 52
r = 5

factorial(n + r - 1) / (factorial(r) * factorial(n - 1))

## [1] 3819816

And finally, we can visualize the combinations using gtool.

n = 52
r = 5

c.res = combinations(n, r, repeats.allowed=TRUE)
head(c.res)

##      [,1] [,2] [,3] [,4] [,5]
## [1,]    1    1    1    1    1
## [2,]    1    1    1    1    2
## [3,]    1    1    1    1    3
## [4,]    1    1    1    1    4
## [5,]    1    1    1    1    5
## [6,]    1    1    1    1    6 -->