Permutations and Combinations

We have four possible scenarios to consider:

  • Permutations with replacement

  • Permutations without replacement

  • Combinations with replacement

  • Combinations without replacement


Permutations vs Combinations


For permutations order matters, with combinations the order does not matter.


Combination:

The order does not matter if you choose 5 employees to form a committee from a group of 20. It doesn’t matter if Bob is chosen before Linda or vice versa because it’s the same committee either way.

Permutation:

However if those committee members had specific job titles like treasurer, note taker, lackey, donut wrangler, and pencil sorter then the order does matter, assuming all 20 people could fill any of the positions.


Permutation With Replacement Example


Let’s say you are thinking of entering a lottery that selects five numbers from 0 to 100 and the numbers can be repeated, so for example a lottery ticket could be 0,0,5,2,1 or even 1,1,1,1,1. How many possible lottery tickets are there?

\[P_{(n,k)}=101\cdot101\cdot101\cdot101\cdot101 = 10510100501\]

\[P_{(n,k)}=n^k\]
OR

\[P_{(101,5)}=101^5 = 10510100501\]

Another Permutation With Replacement Example


Let’s say we’re creating a lottery with 5 possible colors and each ticket has two colors, each color can be repeated. The number of possible tickets are \(5^2 = 25\).


This shows the different possible tickets that would be created in this lottery: 

library(gtools)
colors <- c("red", "blue", "green", "yellow", "black")
expand.grid(rep(list(colors),2)) #permutations with replacement
##      Var1   Var2
## 1     red    red
## 2    blue    red
## 3   green    red
## 4  yellow    red
## 5   black    red
## 6     red   blue
## 7    blue   blue
## 8   green   blue
## 9  yellow   blue
## 10  black   blue
## 11    red  green
## 12   blue  green
## 13  green  green
## 14 yellow  green
## 15  black  green
## 16    red yellow
## 17   blue yellow
## 18  green yellow
## 19 yellow yellow
## 20  black yellow
## 21    red  black
## 22   blue  black
## 23  green  black
## 24 yellow  black
## 25  black  black

Permutation Without Replacement Example


Now let’s say you are thinking of entering a lottery that selects five numbers from 0 to 100. Each number can be used only once (without replacement) and the order of the numbers matters (5,13 is different from 13,5). That’s a permutation.

Since each number can only be used once then the first pick can be one of 101 possible numbers, the second can be one of 100 possible numbers, the third can be one of 99 numbers, and on down to 97. The math looks like this:


\[P_{n,k}= 101\cdot100\cdot99\cdot98\cdot97 = 9505049400\]
It can also be written like this:
\[P_{n,k}= \frac{101\cdot100\cdot99\cdot98\cdot97\cdot96\cdot (...) \cdot2\cdot1}{96\cdot95\cdot94\cdot93\cdot92\cdot91\cdot (....) \cdot2\cdot1} = 9505049400\]

All of the numbers in the denominator cancel out all the numbers in the numerator that are less than 97 leaving just: \(101\cdot100\cdot99\cdot98\cdot97\)



Permutation Without Replacement Formula


The correct formula for a permutation without replacement is:
\[P_{n,k}= \frac{n!}{(n-k)!}\]


\[P_{101,5}= \frac {101!}{(101-5)!} = 9505049400\]


Another Permutation Example

We can create a hypothetical lottery where there are 5 colors to choose from and for each entry selects two colors without replacement.

\[P_{5,2}= \frac {5!}{(5-2)!} = 20\]

The possible entries look like this:

permutations(5,2,colors)
##       [,1]     [,2]    
##  [1,] "black"  "blue"  
##  [2,] "black"  "green" 
##  [3,] "black"  "red"   
##  [4,] "black"  "yellow"
##  [5,] "blue"   "black" 
##  [6,] "blue"   "green" 
##  [7,] "blue"   "red"   
##  [8,] "blue"   "yellow"
##  [9,] "green"  "black" 
## [10,] "green"  "blue"  
## [11,] "green"  "red"   
## [12,] "green"  "yellow"
## [13,] "red"    "black" 
## [14,] "red"    "blue"  
## [15,] "red"    "green" 
## [16,] "red"    "yellow"
## [17,] "yellow" "black" 
## [18,] "yellow" "blue"  
## [19,] "yellow" "green" 
## [20,] "yellow" "red"

You’ll notice that the color combinations repeat but in a different order, for example blue-yellow is followed by yellow-blue.


Combination Without Replacement Example


Now let’s take our lottery example where 5 numbers are selected from numbers 0 to 100 but the order doesn’t matter, so the combination 50,100 is the same as 100,50. What would that look like?

\[C_{n,k}= \frac{n!}{k!(n-k)!}\]

\[C_{101,5}= \frac {101!}{5!(101-5)!} = 79208745\]


The math for this problem is almost identical to the earlier lottery problem, the difference is that we are dividing the earlier solution by 5! to eliminate duplicate combinations where, for example, one ticket would have 50,100,25,20,7 and another ticket has 100,50,25,20,7. With combinations both tickets are the same so they’re treated as one possible ticket.


Another Combination Without Replacement Example

Using our second combination example with the lottery that uses colors, these are the possible combinations

t(combn(colors,2))
##       [,1]     [,2]    
##  [1,] "red"    "blue"  
##  [2,] "red"    "green" 
##  [3,] "red"    "yellow"
##  [4,] "red"    "black" 
##  [5,] "blue"   "green" 
##  [6,] "blue"   "yellow"
##  [7,] "blue"   "black" 
##  [8,] "green"  "yellow"
##  [9,] "green"  "black" 
## [10,] "yellow" "black"


\[C_{n,k}= \frac{n!}{k!(n-k)!}\]
\[C_{5,2}= \frac{5!}{2!(5-2)!}=10\]


Combinations With Replacement


For this case let’s consider a hypothetical lottery, like above, that contains the colors red, blue, green, yellow and black, but instead of picking just two colors you can pick 15 and repeat the five colors. How many combinations could you find in that scenario?

\[C_{n,k}=\frac{(n+k-1)!}{k!(n-1)!}\]

\[C_{5,15}=\frac{(5+15-1)!}{15!(5-1)!} = 3876\]

factorial(5+15-1)/(factorial(15)*factorial(5-1)) #5 colors in 15 slots
## [1] 3876


Another Lottery Example

This will give us fewer combinations that are short enough to print out. So again we have a lottery, this time there are three colors and there are 5 slots with the colors repeating until all five slots are filled. How many possible lottery cards are there?

\[C_{n,k}=\frac{(n+k-1)!}{n!(k-1)!}\]

\[C_{3,5}=\frac{(3+5-1)!}{5!(3-1)!} = 21\]


And we can demonstrate this with R. 

colors <- c("red", "blue", "orange")
colorsPermutation<- expand.grid(rep(list(colors),5))
unique(t(apply(colorsPermutation, 1, sort)))
##       [,1]     [,2]     [,3]     [,4]     [,5]    
##  [1,] "red"    "red"    "red"    "red"    "red"   
##  [2,] "blue"   "red"    "red"    "red"    "red"   
##  [3,] "orange" "red"    "red"    "red"    "red"   
##  [4,] "blue"   "blue"   "red"    "red"    "red"   
##  [5,] "blue"   "orange" "red"    "red"    "red"   
##  [6,] "orange" "orange" "red"    "red"    "red"   
##  [7,] "blue"   "blue"   "blue"   "red"    "red"   
##  [8,] "blue"   "blue"   "orange" "red"    "red"   
##  [9,] "blue"   "orange" "orange" "red"    "red"   
## [10,] "orange" "orange" "orange" "red"    "red"   
## [11,] "blue"   "blue"   "blue"   "blue"   "red"   
## [12,] "blue"   "blue"   "blue"   "orange" "red"   
## [13,] "blue"   "blue"   "orange" "orange" "red"   
## [14,] "blue"   "orange" "orange" "orange" "red"   
## [15,] "orange" "orange" "orange" "orange" "red"   
## [16,] "blue"   "blue"   "blue"   "blue"   "blue"  
## [17,] "blue"   "blue"   "blue"   "blue"   "orange"
## [18,] "blue"   "blue"   "blue"   "orange" "orange"
## [19,] "blue"   "blue"   "orange" "orange" "orange"
## [20,] "blue"   "orange" "orange" "orange" "orange"
## [21,] "orange" "orange" "orange" "orange" "orange"

Notice that this expand.grid series of functions is identical to the commands used to create permutations with replacement at the top of the page.


Combinations With Replacement Function


And we can write a little function.

combnWReplace <- function(n,k){ #n is a vector
    nPermutation<- expand.grid(rep(list(n),k))
    results<- unique(t(apply(nPermutation, 1, sort)))
    return(results)
}

colors<- c("red", "green", "black")
combnWReplace(colors,6)
##       [,1]    [,2]    [,3]    [,4]    [,5]    [,6]   
##  [1,] "red"   "red"   "red"   "red"   "red"   "red"  
##  [2,] "green" "red"   "red"   "red"   "red"   "red"  
##  [3,] "black" "red"   "red"   "red"   "red"   "red"  
##  [4,] "green" "green" "red"   "red"   "red"   "red"  
##  [5,] "black" "green" "red"   "red"   "red"   "red"  
##  [6,] "black" "black" "red"   "red"   "red"   "red"  
##  [7,] "green" "green" "green" "red"   "red"   "red"  
##  [8,] "black" "green" "green" "red"   "red"   "red"  
##  [9,] "black" "black" "green" "red"   "red"   "red"  
## [10,] "black" "black" "black" "red"   "red"   "red"  
## [11,] "green" "green" "green" "green" "red"   "red"  
## [12,] "black" "green" "green" "green" "red"   "red"  
## [13,] "black" "black" "green" "green" "red"   "red"  
## [14,] "black" "black" "black" "green" "red"   "red"  
## [15,] "black" "black" "black" "black" "red"   "red"  
## [16,] "green" "green" "green" "green" "green" "red"  
## [17,] "black" "green" "green" "green" "green" "red"  
## [18,] "black" "black" "green" "green" "green" "red"  
## [19,] "black" "black" "black" "green" "green" "red"  
## [20,] "black" "black" "black" "black" "green" "red"  
## [21,] "black" "black" "black" "black" "black" "red"  
## [22,] "green" "green" "green" "green" "green" "green"
## [23,] "black" "green" "green" "green" "green" "green"
## [24,] "black" "black" "green" "green" "green" "green"
## [25,] "black" "black" "black" "green" "green" "green"
## [26,] "black" "black" "black" "black" "green" "green"
## [27,] "black" "black" "black" "black" "black" "green"
## [28,] "black" "black" "black" "black" "black" "black"