Skip to content

combinatorics-introduction.md

Latest commit

 

History

History
341 lines (269 loc) · 16.2 KB

combinatorics-introduction.md

File metadata and controls

341 lines (269 loc) · 16.2 KB

Introduction to combinatorial analysis

Erika Duan 3/10/23

Summary

This tutorial explains how to use factorials, permutations and combinations to count object combination possibilities. It also covers more advanced combinatorial analysis methods involving distinct object partitions, non-distinct object combinations and the Pascal and Vandermonde identities. Combinatorial analysis is a prerequisite for calculating event probabilities and the total possible sample space using the sample-point method.

The mn rule

The m\times n rule is a simple rule for finding the total number of all possible ordered pairs (a_i, b_j) from two different sets A and B.

When you have one scenario containing m possible elements i.e. A = \{a_1, a_2, \cdots, a_m\} and one scenario containing with n possible elements i.e. B = {b_1, b_2, \cdots, b_n}, the total number of possible joint scenarios is the total number of ordered pairs (a_i, b_j) where 1 \leq i \leq m and 1 \leq j \leq n.

This is equal to m\times n = mn.

This rule is best illustrated by the scenario of rolling two dice. The total number of possible ordered pairs of two dice rolls is 6 \times 6 = 36, as each dice roll generates 6 possible simple events i.e. A = \{1, 2, 3, 4, 5, 6\} and B = \{1, 2, 3, 4, 5, 6\}.

This can also be denoted by S = \{(a, b) : a \in \{1, \cdots, 6\}, b \in \{1, \cdots, 6\}\} where n_S = 6\times6 = 36.

Factorials

The definition of an n-factorial is n! = n! \times (n-1)! \times (n-2)! \times \cdots \times 1. The total number of all possible arrangements of n distinct objects in a row is equal to n!.

For example, take a scenario where we have four different cats. The total number of possible ways that these 4 cats can sit in a row is equal to 4 \times 3\times 2\times 1 = 4!. This is intuitively explained by the fact that once a cat has occupied the first position, there are only 3 remaining cats who can occupy the second position, and only 2 remaining cats who occupy the third position.

R

In R, the function factorial() accepts a numerical vector as its argument.

# Calculate factorials in R ----------------------------------------------------
factorial(4)
#> [1] 24

factorial(4) == 4 * 3 * 2 * 1
#> [1] TRUE

Python

In Python, the function factional() exists in the math module and has a fast C type internal implementation.

# Calculate factorials in Python -----------------------------------------------
import math 
math.factorial(4)
#> 24

# Factorials can also be calculated using a for loop ---------------------------
# Method is slower than math.factorial()  

n = 4 # State n-th factorial
fact = 1
 
for i in range(1, n + 1): # To output n, Python slices to n + 1
    fact = fact * i
 
f"The factorial of {n} is {fact}"  

# The code above is equivalent to the following operations  
# fact = 1 * 1
# fact = 1 * 2
# fact = 2 * 3
# fact = 6 * 4

Julia

In Julia, the function factorial() is in-built and accepts an integer as its argument.

# Calculate factorials in Julia ------------------------------------------------
factorial(4)  
#> 24

factorial(4) == 4 * 3 * 2 * 1
#> true

Permutations

A permutation of objects occurs when you have n distinct objects and must find the total number of ordered object arrangements occupying r positions, where r < n.

P^n_r = \frac{n!}{n-r!} = n \times (n-1) \times \cdots \times (n - r + 1)

Intuitively, this makes sense as you only have r positions available for n distinct objects to occupy, so there are n objects occupying the first position, n - 1 objects occupying the second position and n - r + 1 objects occupying the r^{th} position.

For example, when n = 4 and r = 2, we have 4 distinct objects occupying the first position and 3 distinct objects occupying the second (and final) position. Therefore P^4_2 = 4 \times 3 = 12.

Finding the product of different permutations is useful when counting the number of times that one of two top candidates appear in a selection panel of two candidates from a total of five candidates. This can be framed as finding the total different arrangements of 1) selecting 1 top candidate from 2 top candidates and 2) selecting 1 mediocre candidate from 3 mediocre candidates.

P^2_1 \times P^3_1 = \frac{2!}{(2-1)!} \times \frac{3!}{(3-1)!} = 2 \times 3 = 6

Combinations

A combination of objects occurs when you have n distinct objects and must find the total number of unordered object arrangements occupying r positions, where r < n. For example, we consider “ACT” and “CAT” to be different ordered word arrangements (two permutations). When order does not matter, “ACT” and “CAT” contain the same distinct letters and are counted as the same combination.

C^n_r = {n\choose r} = \frac{P^n_r}{r!} = \frac{n!}{(n-r)!r!}

Intuitively, this is because the total possible arrangement of r distinct objects is r!. Therefore, C^n_r = \frac{P^n_r}{r!}.

Combinations and the bijection principle

What happens when we are interested in the number of ways that identical objects can be distributed to different locations? We can adapt this question as a combination calculation even though it involves positioning identical rather than distinct objects.

Consider the different ways that 2 identical hoops can be placed on two posts:

  • We represent the scenario where both are placed on the first post as “oo+”.
  • We represent the scenario where one hoop is placed on the first hoop and one ring is placed on the second hoop as “o+o”.
  • We represent the scenario where two hoops are placed on the second hoop as “+oo”.
  • The boundary between the two posts is therefore represented as the third distinct object “+”.

Because the hoops are identical, the order of individual hoop placements on the same post does not matter (as they correspond to the same combination). Therefore, the total possible ways that two identical hoops can be placed through two posts is equal to C^3_2 = \frac{3!}{(3-2)!\times2!} = \frac{3\times2\times1}{1\times2\times1} = 3.

Combinations and lattice paths

The bijection principle can also be applied to the identification of lattice pathway solutions.

The properties of combination addition can also be derived from the study of lattice paths. Consider the lattice graph above, which has end coordinates of (4, 3) along the Cartesian plane. The sum of all solutions leading to coordinates (3, 3) and (4, 2) is equal to all the solutions leading to coordinates (4, 3).

Therefore, C^7_3 = C^6_3 + C^6_2 where C^7_3 = 35, C^6_3 = 20 and C^6_2 = 15.

Distinct object partions

The conditions for calculating the total number of ways of partitioning n distinct objects into k distinct groups are:

  • A total of n distinct objects are partitioned into k distinct groups.
  • Each object only appears in exactly one group.
  • This implies that the sum of objects in all groups is equal to n.
  • The groups are denoted by r_1, r_2, \cdots, r_k where \displaystyle\sum_{i=1}^{k} r_i = n.

Pascal’s identity

Pascal’s identity can be derived from an extension of the lattice path analogy, where the sum of all solutions leading to coordinates (a+b-1, b) and (a+b-1, b-1) is equal to all the solutions leading to coordinates (a+b, b).

If we substitute a + b - 1 = m and b = k, we obtain the formula for Pascal’s identity.

{m+1\choose k} = {m\choose k} + {m\choose k-1} where m \in \{0, 1, 2, \cdots\} and k \in \{1, 2, 3, \cdots\}

Pascal’s identity can also be derived by considering the following scenario. Suppose we need to count the total possible unordered arrangements of a committee, when selecting k persons from m men and 1 woman.

Vandermonde’s identity

The formula for Vandermonde’s identity can be derived by considering an extension of the previous scenario. Suppose we need to count the total possible unordered arrangements of a committee, when selecting k persons from m men and w woman.

{m+w\choose k} = {m\choose 0}{w\choose k} + {m\choose 1}{w\choose k-1} + \cdots + {m\choose k-1}{w\choose 1} + {m\choose k}{w\choose 0}

Resources