Gathering of some of the main methods of Combinatorial Analysis.
Combinatorics is basically the study of counting the number of possibilities in finite collections of elements, based on specific criteria. This field is closely related to many other areas of mathematics and has many applications in statistics, physics, computer science and so on.
Before talking about some combinatorial counting methods, let's introduce some basic concepts that support all these subjects.
The fundamental counting principle is a rule that give us the idea that the number of possibilities to execute n actions is the multiplication of the quantity of distinct modes.
For example, if we have two sets: $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2\}$.
How many ways we can conjugate both sets?
$$ \large C=(A, B)=\{(a_1, b_1),(a_1, b_2),(a_2, b_1),(a_2, b_2),(a_3, b_1),(a_3, b_2)\} $$The answer is 6 because the set A has 3 elements and B has 2 elements so $3 \cdot 2 = 6$.
A = ["a1", "a2", "a3"]
B = ["b1", "b2"]
C = [(a, b) for a in A for b in B]
print(f'A = {A}')
print(f'The set A has {len(A)} elements')
print(f'B = {B}')
print(f'The set B has {len(B)} elements')
print(f'C = {C}')
print(f'The conjugation C has {len(C)} elements')
A = ['a1', 'a2', 'a3']
The set A has 3 elements
B = ['b1', 'b2']
The set B has 2 elements
C = [('a1', 'b1'), ('a1', 'b2'), ('a2', 'b1'), ('a2', 'b2'), ('a3', 'b1'), ('a3', 'b2')]
The conjugation C has 6 elements
Combinatorial analysis appears in many areas of pure mathematics, but there are two mathematical entities that deserve comment before we proceed.
Factorial of a natural number $n$ is the product of all positive integers less than or equal to $n$.
$$ \large n! = \prod_{k=1}^{n} = n \cdot (n-1) \cdot (n-2) \ \cdot \ ... \ \cdot \ 2 \cdot 1 $$In addition, follows some rules that supports our understanding of actorials and how to implement practical applications:
def factorial(n):
if n <= 1:
return 1
return n*factorial(n - 1)
print(f' 5! = {factorial(5)}')
print(f' 4! = {factorial(4)}')
print(f'5*4! = {5*factorial(4)}')
print(f' 0! = {factorial(0)}')
5! = 120 4! = 24 5*4! = 120 0! = 1
Binomial coefficient (or binomial number) of a natural number $n$ and class $k$ (where $n \ge k$) is an algebraic way to represent the combination of these two values. The binomial coefficient can be expressed as:
$$ \large {n \choose k} = \frac{n!}{k! \cdot (n - k)!} = \frac{n \cdot (n-1) \cdot (n-2) \ \cdot \ ... \ \cdot \ (n-k+1)}{k!} $$For example, the binomial coefficient of the number 5 with class 3 is:
$$ \large {5 \choose 3} = \frac{5!}{3! \cdot (5 - 3)!} = \frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = \frac{120}{12} = 10 $$def binomial(n, k):
n_ = factorial(n)
k_ = factorial(k)
nk_ = factorial(n - k)
return n_//(k_*nk_)
print(f'(5, 3) = {binomial(5, 3)}')
(5, 3) = 10
Binomial coefficient has a complementarity rule described by:
$$ \large {n \choose k} = {n \choose n-k} $$In this case $k$ and $n-k$ are called as complementary terms. For example:
$$ \large {8 \choose 5} = {8 \choose 3} $$print(f'(8, 5) = {binomial(8, 5)}')
print(f'(8, 3) = {binomial(8, 3)}')
(8, 5) = 56 (8, 3) = 56
Permutation of a set is the number of ways to arrange n distinct elements in n sequenced positions. This means that each way differs from the other in the way the elements are ordered. The permutation count is calculated as:
$$ \large P_n = n \cdot (n-1) \cdot (n-2) \ \cdot \ ... \ \cdot \ 2 \cdot 1 = n! $$Notice the equation is equivalent to factorial of n.
For example, given 3 colors {🟧, 🟩, 🟨}, in how many ways we can permute them?
$$ \large P(3) = 3! = 3 \cdot 2 \cdot 1 = 6 $$| Permunation | Possibilities |
|---|---|
| 1 | 🟧🟩🟨 |
| 2 | 🟧🟨🟩 |
| 3 | 🟩🟧🟨 |
| 4 | 🟩🟨🟧 |
| 5 | 🟨🟧🟩 |
| 6 | 🟨🟩🟧 |
n = 3
print(f'✨ A set of {n} distinct elements has {factorial(n)} permutations.')
✨ A set of 3 distinct elements has 6 permutations.
Similarly to permutation, in arrangement the order matters, but in relation to the number of possibilities it has some considerations.
The arrangement with repetition is used when the order of the elements matters and each element can be repeated. Considering we have a set of n elements and organize them in k positions, with the possibility of repetition, the number of arrangement is expressed as:
$$ \large A_n^k = n^k $$For example, given 2 colors {🟩, 🟨}, in how many ways we can arrange them in 3 positions?
$$ \large A(2, 3) = 2^3 = 2 \cdot 2 \cdot 2 = 8 $$| Arrangement | Possibilities |
|---|---|
| 1 | 🟩🟩🟩 |
| 2 | 🟩🟩🟨 |
| 3 | 🟩🟨🟩 |
| 4 | 🟩🟨🟨 |
| 5 | 🟨🟩🟩 |
| 6 | 🟨🟩🟨 |
| 7 | 🟨🟨🟩 |
| 8 | 🟨🟨🟨 |
n = 2
k = 3
print(f'✨ A set of {n} elements and {k} positions has {n**k} arrangements.')
✨ A set of 2 elements and 3 positions has 8 arrangements.
The arrangement without repetition is used when the order of the elements matters and each element cannot be repeated. Considering we have a set of n elements and organize them in k positions, without the possibility of repetition, the number of arrangement is expressed as:
$$ \large A_n^k = \frac{n!}{(n - k)!} $$Notice that n must be grather than k. ($n > k$)
For example, given 4 colors {🟧, 🟪, 🟩, 🟨}, in how many ways we can arrange them in pairs?
$$ \large A(4, 2) = \frac{4!}{(4 - 2)!} = \frac{4!}{2!} = \frac{4 \cdot 3 \cdot 2!}{2!} = 4 \cdot 3 = 12 $$| Arrangement | Possibilities |
|---|---|
| 1 | 🟧🟪 |
| 2 | 🟧🟩 |
| 3 | 🟧🟨 |
| 4 | 🟪🟧 |
| 5 | 🟪🟩 |
| 6 | 🟪🟨 |
| 7 | 🟩🟧 |
| 8 | 🟩🟪 |
| 9 | 🟩🟨 |
| 10 | 🟨🟧 |
| 11 | 🟨🟪 |
| 12 | 🟨🟩 |
n = 4
k = 2
print(f'✨ A set of {n} colors can be arranged in {factorial(n)//factorial(n - k)} pairs.')
✨ A set of 4 colors can be arranged in 12 pairs.
Different from permutation and arrangement, in combination the order does not matter. But in relation to the number of possibilities, there are still has some considerations.
The combination without repetition (or simple combination) is used when the order of the elements does not matter and each element cannot be repeated. Considering we have a set of n elements and organize them in k positions, with the possibility of repetition, the number of combinations is expressed as:
$$ \large C_n^k = {n \choose k} = \frac{n!}{k! \cdot (n - k)!} $$Notice the equation is equivalent to binomial of n and k.
For example, given 4 colors {🟧, 🟪, 🟩, 🟨}, in how many ways we can combine them in 2 positions?
$$ \large C(4, 2) = {4 \choose 2} = \frac{4!}{2! \cdot (4 - 2)!} = \frac{4!}{2! \cdot 2!} = \frac{4 \cdot 3 \cdot 2!}{2! \cdot 2!} = \frac{4 \cdot 3}{2} = 6 $$| Combination | Possibilities |
|---|---|
| 1 | 🟧🟪 or 🟪🟧 |
| 2 | 🟧🟩 or 🟩🟧 |
| 3 | 🟧🟨 or 🟨🟧 |
| 4 | 🟪🟩 or 🟩🟪 |
| 5 | 🟪🟨 or 🟨🟪 |
| 6 | 🟩🟨 or 🟨🟩 |
n = 4
k = 2
print(f'✨ A set of {n} colors can be combined in {binomial(n, k)} pairs.')
✨ A set of 4 colors can be combined in 6 pairs.
The combination with repetition is used when the order of the elements does not matter and each element can be repeated. Considering we have a set of n elements and organize them in k positions, the number of combinations is expressed as:
$$ \large C_n^k = {n + k - 1 \choose k} = \frac{(n + k - 1)!}{k! \cdot (n - 1)!} $$For example, given 2 colors {🟩, 🟨}, in how many ways we can combine them in 3 positions?
$$ \large C(2, 3) = {2 + 3 - 1 \choose 3} = \frac{(2 + 3 - 1)!}{3! \cdot (2 - 1)!} = \frac{4!}{3!} = \frac{4 \cdot 3!}{3!} = 4 $$| Combination | Possibilities |
|---|---|
| 1 | 🟨🟨🟨 |
| 2 | 🟩🟨🟨 or 🟨🟩🟨 or 🟨🟨🟩 |
| 3 | 🟨🟩🟩 or 🟩🟨🟩 or 🟩🟩🟨 |
| 4 | 🟩🟩🟩 |
n = 2
k = 3
print(f'✨ A set of {n} colors and {k} positions has {binomial(n + k - 1, k)} combinations.')
✨ A set of 2 colors and 3 positions has 4 combinations.