KoalaTea

05.12.2021
Intro
Combinatorics is one of the cornerstones of mathematics. Many problemsstart or are solved by counting the number of possibility. Probabilitytheory is built on these tools. R provides us with many ways to countusing permutations and combinations. There are options to use with andwithout repetitions and much more. In this article, we will learn how tocount the number of permutations and combinations in R.
Permuations with Repeition
An example of permutations with repetition is counting the number ofpossible lock combinations. Think about a safe lock where there are 3possible numbers. Each number can be from 0-9 and you are allowed toreuse the numbers and order matters, thus it is a permutation. Let’s seeto count these combinations in R.
To calculate the total number of permutations with repetition, we usethe simple formula nr. 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 wantto generate each of these combinations to visualize them. A helpful toolfor this is gtools
. We can install it by uncommenting and running thefollowing.
# install.packages('gtools')library(gtools)
Now, we can use the permutations
function to generate all possiblelock combinations.
# R starts with 1, so we need to create a list of 0 to 10choices = c(0:9)# n is the number of options, r is the number of groups, v is the value of our choicesres = permutations(n = 10, r = 3, v = choices, repeats.allowed = TRUE)# Only show the head as there are many optionshead(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 thematrix above.
nrow(res)
## [1] 1000
As we can see there are 1000 rows which is the same as we calculatedabove.
Permuations without Repetition
Now we move on to permutations without repetition. This means that thechoice we have gets smaller each time. For example, let’s say for ourlock combination above, we had to select 3 unique numbers each time. Thecalculation for this would be:
9 * 8 * 7 = 504
Without getting two in the weeds, the mathematical way to calculate thisis:
6∗5∗4∗3∗2∗19∗8∗7∗6∗5∗4∗3∗2∗1
Which is basically saying select all possible permutations of the 9groups, but remove 6 groups as we only want 3 choices (our lock is a 3slot combination). In the equation above, 6-1 cancel out. The cool mathynotation for this is.
(n−r)!n!
Where n is the number of possible choices and r is the number ofchoices. So we can calculate this in R like so.
n = 9r = 3factorial(n) / factorial(n - r)
## [1] 504
If we would like to see all the possible permutations, we can use ourpermutations function again, but set the repeats.allowed = FALSE
.
# R starts with 1, so we need to create a list of 0 to 10choices = c(0:9)# n is the number of options, r is the number of groups, v is the value of our choicesres = permutations(n = 10, r = 3, v = choices, repeats.allowed = FALSE)# Only show the head as there are many optionshead(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 asthat is a bit easier. The difference between combinations andpermutations is that order does not matter for combinations. Forexample, let’s say we want to know the combinations of of cards in a 5card hand. In general, the order doesn’t matter. You can have a pair of3’s (one clubs and one hearts, for example) and it doesn’t matter which3 comes first.
The formula for combinations without repetition is:
r!(n−r!)n!
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 infunction, choose
or calculate it manually.
n = 52r = 5factorial(n) / (factorial(n - r) * factorial(r))
## [1] 2598960
choose(n = n, k = r)
## [1] 2598960
We can see the combinations using the combinations
function fromgtools.
n = 52r = 5c.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 startagain with the formula.
r!(n−1!)(n+r−1)!
We can caluclate this in R using the following:
n = 52r = 5factorial(n + r - 1) / (factorial(r) * factorial(n - 1))
## [1] 3819816
And finally, we can visualize the combinations using gtool
.
n = 52r = 5c.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 -->
datasciencerstatistics