Combinatorics

Introduction

Table of contents

1. Concepts
2. Number of possible permutations
3. Number of possible combinations

🡻

1. Concepts

• Sampling with replacement: Elements are randomly selected from a population, and the population remains unchanged after each sample is drawn. Also referred to as sampling with repetitions.
• Sampling without replacement: Elements are randomly selected from a population, and elements included in a sample are removed from the population prior to subsequent sampling. Also referred to as sampling without repetitions.
• Permutation: Given a set A with n elements, consider an experiment that consists of selecting k elements from A. Let each outcome consist of the k elements in the order selected. Then each outcome is called a permutation of n elements taken k at a time.
• Combination: Consider a set A with n elements. Each subset A_i with k elements (k < n) is called a combination of n elements taken k at a time.

# Consider a sample space
S = c( "A", "B", "C", "D", "E", "F" )

set.seed( 212 ) # For reproducibility

### Sampling with replacement ###

# Each sample draws two elements 
# from S
J = 1:6
sample_1 = sample( J, size = 2 )
sample_2 = sample( J, size = 2 )
sample_3 = sample( J, size = 2 )

# For each sample, population 
# J remains unchanged, so 
# elements can appear in 
# multiple samples
S[ sample_1 ] # [1] "F", "C"
S[ sample_2 ] # [1] "A", "B"
S[ sample_3 ] # [1] "A", "E"

### Sampling without replacement ###

# Each sample draws two elements 
# from S
sample_1 = sample( J, size = 2 )
# Remove elements from population
J = J[ !J %in% sample_1 ]  
sample_2 = sample( J, size = 2 )
J = J[ !J %in% sample_2 ]  
sample_3 = sample( J, size = 2 )

# After each sample, population is 
# updated to only have unsampled 
# elements - therefore, each 
# element only appears once 
# across samples
S[ sample_1 ] # [1] "D", "A"
S[ sample_2 ] # [1] "E", "F"
S[ sample_3 ] # [1] "C", "B"

References:

• DeGroot, M. H., & Schervish, M. J. (2012). Probability and statistics (4th ed.). Boston, MA: Addison-Wesley. →
• Dodge, Y. (2008). The concise encyclopedia of statistics. New York, NY: Springer. →

🡹 🡻

2. Number of possible permutations

Content.

# Example R code

Note: Advanced content.

References:

• Reference →

🡹 🡻

3. Number of possible combinations

Assume an experiment (e.g., a dice roll, a coin flip, etc.):

• has k parts (k ≥ 2);
• the i^th part of the experiment can have n_i outcomes;
• all of the outcomes in each part can occur irrespective of what occurred in other parts (i.e., sampling with replacement).

The total number of unique combinations of outcomes over parts is then:

\(\prod_{i=1}^k n_i\).

Using R, we can easily run a Monte Carlo simulation that demonstrates this. Consider rolling a 6-sided die 3 times:

# Function to simulate rolling a 6-sided die 3 times
roll_dice_3_times <- function() {
  # Sample space
  S <- 1:6
  # Simulate 3 rolls of die
  output <- sample( S, size = 3, replace = T )
  return( output )
}

# Monte Carlo simulation of 10,000 rolls
mc_sim <- sapply(
  1:10000,
  function(i) roll_dice_3_times()
)

# Convert column vectors with separate outcomes
# for each roll into character strings in order to
# easily identify unique combinations
terms <- apply( mc_sim, 2, paste, collapse = ',')

# Extract all unique combinations of outcomes
unq <- unique( terms )

# Total number of unique outcome combinations
print( length( unq ) ) # 216

# Using multiplication rule

# 6 possible outcomes for each roll
n <- c( 6, 6, 6 )

# Product of number of outcomes for each part
print( prod( n ) ) # 216

Let n be the total number of elements in the set, and let k be the number of elements drawn from the set with replacement. Then the total number of permutations is \(n^k\). For example, considers a 3-dial combination lock with the numbers 0 to 9 on each dial. Then the set of possible elements is \(S = {0, \dots, 9}\), with n = 10 and k = 3, resulting in \(10^3 = 1000\) possible permutations.

\[P(n,k) = \frac{n!}{(n - k)!} = \frac{ \Gamma(n+1) }{ \Gamma( n - k + 1 ) }.\] \[C(n,k) = \frac{n!}{k! (n - k)! }\]

exp(lgamma(n+1)‐lgamma(n‐m+1))

\[\begin{align*} \textrm{ Permutation } & \vert & \textrm{ Replacement } & \vert & \textrm{ Expression } \\ \textrm{ Yes } & \vert & \textrm{ Yes } & \vert & n^k \\ \textrm{ Yes } & \vert & \textrm{ No } & \vert & P(n, k) \\ \textrm{ No } & \vert & \textrm{ Yes } & \vert & C(n + k - 1, k) \\ \textrm{ No } & \vert & \textrm{ No } & \vert & C(n, k) \\ \end{align*}\]

References:

• DeGroot, M. H., & Schervish, M. J. (2012). Probability and statistics (4th ed.). Boston, MA: Addison-Wesley. →

🡹

Return to: Probability; Sections; Home page