USTHB : 1st ING ,1)2 2023/2024 Probability and statistics

Chapter  :
Combinatorial Analysis

The aim of combinatorial analysis is to count the diffrent arrangements that can
be formed from a set of elements. It is a branch of Mathematics that studies how
to count objects. It consists of a set of formulas which are used in several
elementary problems in probability theory.
Example 1 : License plates of certain country contain three letters followed by
three numbers. How many different plates can we have ?
3. 1. Basics
Definition 3. 1. 1 (Factorial)
The factorial of positive integer number n is the product of all positive integers
less than or equal to n
𝑛! = 1 × 2 × … × (𝑛 − 1) × 𝑛
By convention, the factorial of 0 is equal to 1, i.e. 0 !=1
Definition 3. 1. 2 (Set)
A set is a collection of objects called elements
Definition 3. 1. 3 (Subset)
F is a subset of (or included in) the set E, if all the elements of F are also the
elements of E and we note : 𝐹 ⊂ 𝐸
Definition 3. 1. 4 (Cardinal)
The number of elements of a set E is called cardinal of E, denoted Card(E) or |𝐸|
Note 1 :
We denoted by 𝜙 the empty set (or null set). It is the set that does not contain any
element.
Example 2. 𝐴 = {1, 2, 3, 𝑎, 𝑏, 𝑐} 𝐵 = {1, 2, 3}.
We have : 𝐵 ⊂ 𝐴, |𝐴| = 6, and |𝐵| = 3

Chapter  Page 1
USTHB : 1st ING ,1)2 2023/2024 Probability and statistics

3. 1. 1 Fundamental counting principle

The fundamental principle of counting make it possible to count the number of
experimental results which can be decomposed into a succession of sub-
experiments.
Property 1 (The case of two experiments). Suppose that two experiments need to
be carriend out. If experiment 1 can produce any one of m results and if, for each
of them, there are n possible results for experiment 2, then there are 𝑚 × 𝑛 results
for the two experiments taken together.
When ther are more than two experiments to be performed, the fundamental
counting principle can be generalized as follows :
Property 2 (The case of m experiments). Suppose that an experiment is the
succession of m sub-experiments. If the ith experiment has 𝑛𝑖 possible outcomes,
then the total number n of possible outcomes of the overall experiment is :
𝑚

𝑛 = ∏ 𝑛𝑖 = 𝑛1 × 𝑛2 × … × 𝑛𝑚
𝑖=1

Example 3. A padlock has 3 numbers from 0 to 9. We therefore fave three choices

to make successively :
 First digit of the code (the first sub-experiment) : we have 𝑛1 = 10
possibilities.
 Second digit of the code (the second sub-experiment) : we have 𝑛2 = 10
possibilities.
 Third digit of the code (the third sub-experiment) : we have 𝑛2 = 10
possibilities.
The total number of possibilities n of different codes that can be constructed is the
product of the possibilities of each sub- experiment :
3

𝑛 = ∏ 𝑛𝑖 = 𝑛1 × 𝑛2 × 𝑛3 = 1000
𝑖=1

Chapter  Page 2
USTHB : 1st ING ,1)2 2023/2024 Probability and statistics

3. 2. Counting formula
3. 2. 1 Arrangement
Definition 3. 2. 1. Let E be a finit set with n elements and p an integer satisfying
0 ≤ 𝑝 ≤ 𝑛. We call arrangements of p elements, all ordred sequences of p
elements taken from the n elements.
We distinguish two cases :
1) Arrangement with repetition : When an element can be observed several
times in an arrangement, the number of arrangement with repetition of p
elements among n, is given by :
𝑝
𝐴̃𝑛 = 𝑛𝑝

2) Arrangement without repetition : When each element can only be observed

once in an arrangement, the number of arrangements without repetition of p
elements among n is :

𝑝 𝑛!
𝐴𝑛 =
(𝑛 − 𝑝)!
Example 4. We want to create a password composed of 3 digits. Here, the order
of elements is important (for example, password 112 is different from password
211). In addition, we can have a digit that repeats. Therefor, the number of
possible cases corresponds to the number of arrangements with repetition, with
p = 3 and n = 10 :
𝐴̃10
3
= 103
On the other hand, if we requiere that the password must contain 3 different digits,
the number of passwords possible corresponds to the the number of arrangements
without repetition, with p = 3 and n = 10 :

3
10!
𝐴10 = = 8 × 9 × 10 = 720
(10 − 3)!
3. 2. 2 Permutation
Definition 3. 2. 2. Given a set E of n elements. We call permutation of n elements
any ordered sequence of n elements. We distinguish two cases :
1) Permutation without repetition : When all elements are distinct, the number
of parmutations without repetition of n elements is given by :
𝑃𝑛 = 𝑛!

Chapter  Page 3
USTHB : 1st ING ,1)2 2023/2024 Probability and statistics

2) Permutation with repetition : In the case where there exist several repetitions
𝑛𝑖 (with ∑𝑘𝑖=1 𝑛𝑖 = 𝑛) of k elements among the n elements, the number of
permutation with repetitions is given by :
𝑛!
𝑃̃𝑛 =
𝑛1 ! × 𝑛2 ! × … × 𝑛𝑘 !

Example 5. How many ways can you arrange 5 distinct books on a shelf ?
This is the case of prmutation without repetition, therefore :
𝑃5 = 5! = 120
Now, if ampng the 5 books we have 3 identical mathematics books, and 2 identical
computer science books. The number of ways to organize these books is :
5!
𝑃̃5 = = 30
3! × 2!

3. 2. 3 Combination
Definition 3. 2. 3. Given a set E of n elements, we call combination of p elements
any subset of p elements taken from the n elements, without any determined order
and without replacement.
The number of combinations of p elements taken from n, is given by :
𝑝 𝑛!
𝐶𝑛 =
𝑝! (𝑛 − 𝑝)!

Example 6. If a student must respond to 3 questions from 4 on an exam. How

many ways can be respond ?
The exam’s questions are distincts, and the order in wich the student answers the
questions is not important. The number of possible ways is a combination with
p = 3 and n = 4
4!
𝐶43 = =4
3! (4 − 3)!

Chapter  Page 4
USTHB : 1st ING ,1)2 2023/2024 Probability and statistics

Properties 1
𝑝 𝑛−𝑝
 𝐶𝑛 = 𝐶𝑛 (symmetry)
𝑝−1 𝑝 𝑝
 𝐶𝑛−1 + 𝐶𝑛−1 = 𝐶𝑛 (Pascal’s formula)
 𝐶𝑛𝑛 = 𝐶𝑛0 = 1
 𝐶𝑛1 = 𝐶𝑛𝑛−1 = 𝑛

Arrangement Permutation Combination

Without 𝑝 𝑛! 𝑃𝑛 = 𝑛! 𝑝 𝑛!
𝐴𝑛 = 𝐶𝑛 =
repetition (𝑛 − 𝑝)! 𝑝! (𝑛 − 𝑝)!
𝑝 𝑛!
With 𝐴̃𝑛 = 𝑛𝑝
𝑃̃𝑛 =
repetition 𝑛1 ! × 𝑛2 ! × … × 𝑛𝑘 !

Table 3.1 : Counting formulas

Chapter  Page 5