Combinatorics

Combinatorics is the study of how to count things i.e. the various combinations, pemutations, subgroups that can be formed from a given set of objects/people etc.

• How many different ways we can sort three objects $[\square, \enspace \triangle, \enspace \star]$?

• How many times we can pick pair of balls from an urn that contains three different coloured balls; red, green, blue? etc.

• How many different outcomes are possible if you flip a coin four times?

• How many different full-house hands are there in poker? (Full house = three of one rank + two of another rank. For instance, e.g. AAA KK or 222 55 etc.)

• How many different committees of three people can be chosen from five people?

  • What if we additonally designate one person as the committee’s president?

$\rhd$ Knowing how to count these type of things is critical for an understanding of probability, because when calculating the probability of a given event, we often need ti count the number of ways that event can happen. Note that throughout this book we will use that we are using the frequentist approach.

Frequentist vs Bayesian approaches: Note that we assuming frequentist approach throughout this book meaning that after the experiments/trials based on our initial assumption (i.e. probability of heads occuring is 0.5) is not going to be updated by using the data, which is the Bayesian approach. Here, in order to understand basics of the probability we are assuming we are using frequentist approach.

Factorials

Before getting into the discussion of actual combinatorics and related concepts we first need to look at a certain quantity that comes up very frequently. This quantity is called the factorial.

Throughout this book when dealing with a situation that involves an intger value $N$, we often need to consider the product of the first $N$ integers:

For the few integers we have:

From above expression we can see some pattern, however, there are also some elements doesn’t make as much sense. For instance,

why both $0!$ and $1!$ are equal to 1?

Let’s take an alternative approach. From [2], we can see the following pattern,

$\rhd$ For $5!$, we need to multiply 5 integers,

$\rhd$ For $4!$, we need to multiply 4 integers,

$\rhd$ For $3!$, we need to multiply 3 integers,

$\rhd$ For $2!$, we need to multiply 2 integers,

$\rhd$ For $1!$, we need to multiply 1 integer,

$\rhd$ For $0!$, we need to multiply 0 integer,

How are we meant to multiple 0 integer?

Let’s look at other operations such as exponentiation

How about if we look at the multiplication operation?

It is also important to note that as $N$ increases $N!$ gets large very fast

N = 0:20;
factorialVec = zeros(size(N));
dFactorialVec = NaN(size(N));

% Factorial values
for i = 1:length(N)
    n = N(i);
    factorialVec(i) = factorial(n);
end

% Finite difference values
for j = 2:length(N)-1
    % Forward difference: (f[x+1] - f[x]) / ((x+1) - x) =  f[x+1] - f[x]
    dFactorialVec(j) = factorialVec(j+1) - factorialVec(j);
end

figure;
semilogy(N,factorialVec,'o','MarkerSize',6)
hold on
semilogy(N,dFactorialVec,'*','MarkerSize',7)
hold off
grid on
xlabel('$N$',"Interpreter","latex")
legend({'$N!$','$\Delta(N!)$'},"Interpreter","latex","Location","northwest")

As we can see from the above figure that the $N!$ increases almost exponentially with $N$, where $5!=120$, $10!=3,628,800$, and $20!=2.4329e+18$, if we superimpose $10^N$ and $e^N$ exponential functions on the current figure we will have:

N = 0:20;
factorialVec = zeros(size(N));
dFactorialVec = NaN(size(N));

% Factorial values
for i = 1:length(N)
    n = N(i);
    factorialVec(i) = factorial(n);
end

% Finite difference values
for j = 2:length(N)-1
    % Forward difference: (f[x+1] - f[x]) / ((x+1) - x) =  f[x+1] - f[x]
    dFactorialVec(j) = factorialVec(j+1) - factorialVec(j);
end

% Various functions for comparison
expFunction = @(x,k) x.^k;

figure;
semilogy(N,factorialVec,'o','MarkerSize',6)
hold on
semilogy(N,dFactorialVec,'*','MarkerSize',7)
semilogy(N,expFunction(exp(1),N),'-')
semilogy(N,expFunction(10,N),'-')
hold off
grid on
xlabel('$N$',"Interpreter","latex")
legend({'$N!$','$\Delta(N!)$','$e^N$','$10^N$'},"Interpreter","latex","Location","northwest")

As we can see from the above figure that the permutation is increasing very rapidly, in fact $N!$ grows faster than much faster than $e^N$ also even faster than $10^N$.

Permutations

Now we have a very basic understanding of how counting and numbers are working, we can focus on calculating number of ways things are happenning. More specifically, a permutation of a set of objects is a way of ordering them.

For example, if we have three people; Alice (A), Bob (B), and Carol (C), then some permutations are $(\mathrm{A}-\mathrm{B}-\mathrm{C})$, $(\mathrm{A}-\mathrm{C}-\mathrm{B})$, $(\mathrm{C}-\mathrm{A}-\mathrm{B})$ etc.

It turns out that there are six permutations in total:

Let’s now investigate how can we order different number of objects to get some insights about how many total possibilities appear, and how to generalize the calculation to count them.

One Object

For a single object, there is only one way to arrange it, $P_1=1$.

Two Objects

When we have two object $A$ and $B$ we can order them in 2 different ways,$P_2=2$:

Three Objects

Four Objects

Combinations

References

[1] Morin, David J. Probability: For the Enthusiastic Beginner. CreateSpace Independent Publishing Platform, 2016.

[2] Ali Nesin, 0! (Sıfır Faktöriyel) Neden 1’e Eşittir? (Why zero factorial 0! equals to zero?) URL: https://youtu.be/i5gxEhNDYls?si=DQIWMxDdY2-MzJK8 (Accessed: 08-07-2026)

[3] Ali Nesin, 0!=1’in Önerilen Kanıtları Neden Yanlış (Why is the proposed solutions for 0!=1 are wrong?)[https://youtu.be/T97dGFB7dww?si=u9IYBCfF-vtZEz-v] (Accessed: 15-07-2026)