Some Formulas
IC252
Dr. Sarita Azad
21st Jan 2026
The Principle of Inclusion-Exclusion
The Principle of Inclusion-Exclusion (PIE) is a counting method to find the size of the union of sets by
adding individual set sizes, then subtracting pairwise overlaps, adding triple overlaps, and so on
|AB|=|A|+|B|-|AB|
| A B C | =?
2
The Principle of Inclusion-Exclusion
|AB|=|A|+|B|-|AB|
| A B C | = | A | + | B | + | C |
- | A B | - | B C| - | A C |
+|ABC|
3
The Principle of Inclusion-Exclusion
| A1 A 2 . . . An | = Σ | Ai |
- Σ | Ai Aj |
+ Σ | Ai Aj Ak |
- ...
+ (-1)n-1 Σ | A1 A2 ... An |
4
Question
How many permutations of the 26 letters of the English alphabet do not contain
any of the strings fish, rat, or bird?
5
Let
•𝐴: permutations containing fish as a string
Solution •𝐵: permutations containing rat
•𝐶: permutations containing bird
1. Start with the universe: 26!
2. Subtract the permutations that contain:
– fish.
To count the number of permutations with a fixed substring:
Treat the fixed substring as 1 letter.
There are (26 – 4 + 1)! such permutations.
– rat: (26 – 3 + 1)!
– bird: : (26 – 4 + 1)!
3. Add the permutations that contain:
– fish & rat: (26 – 4 – 3 + 2)!
– fish & bird: 0
– rat & bird: 0
4. Subtract the permutations that contain all 3 strings
There are 0 such permutations.
Answer: 26! – 23! – 24! – 23! + 21!
6
Techniques for counting
Rule 1
Suppose we carry out have a sets A1, A2, A3, … and that
any pair are mutually exclusive
(i.e. A1 A2 = ) Let
ni = n (Ai) = the number of elements in Ai.
Let A = A1 A2 A3 ….
Then N = n( A ) = the number of elements in A
= n1 + n2 + n3 + …
A1
A2
n1
n2
A3
n3 A4
n4
Rule 2
Suppose we carry out two operations in sequence
Let
n1 = the number of ways the first
operation can be performed
n2 = the number of ways the second
operation can be performed once the
first operation has been completed.
Then N = n1 n2 = the number of ways the two
operations can be performed in sequence.
Examples
We have a committee of 10 people. We choose from
this committee, a chairman and a vice chairman. How
may ways can this be done?
Solution:
Let n1 = the number of ways the chairman can be
chosen = 10.
Let n2 = the number of ways the vice-chairman
can be chosen once the chair has been
chosen = 9.
Then N = n1n2 = (10)(9) = 90
The Multiplicative Rule of Counting
Suppose we carry out k operations in sequence
Let
n1 = the number of ways the first operation
can be performed
ni = the number of ways the ith operation can be
performed once the first (i - 1) operations
have been completed. i = 2, 3, … , k
Then N = n1n2 … nk = the number of ways the
k operations can be performed in sequence.
Examples
1. Permutations: How many ways can you order n
objects
Solution:
Ordering n objects is equivalent to performing n operations in
sequence.
1. Choosing the first object in the sequence (n1 = n)
2. Choosing the 2nd object in the sequence (n2 = n -1).
…
k. Choosing the kth object in the sequence (nk = n – k + 1)
…
n. Choosing the nth object in the sequence (nn = 1)
The total number of ways this can be done is:
N = n(n – 1)…(n – k + 1)…(3)(2)(1) = n!
Example How many ways can you order the 4 objects
{A, B, C, D}
Solution:
N = 4! = 4(3)(2)(1) = 24
Here are the orderings.
ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA
Examples - continued
2. Permutations of size k (< n): How many ways can you
choose k objects from n objects in a specific order
Solution:This operation is equivalent to performing k operations
in sequence.
1. Choosing the first object in the sequence (n1 = n)
2. Choosing the 2nd object in the sequence (n2 = n -1).
…
k. Choosing the kth object in the sequence (nk = n – k + 1)
The total number of ways this can be done is:
N = n(n – 1)…(n – k + 1) = n!/ (n – k)!
This number is denoted by the symbol
n!
Pk =n ( n − 1) ( n − k + 1) =
n
( n − k )!
Definition: 0! = 1
This definition is consistent with
n!
Pk =n ( n − 1) ( n − k + 1) =
n
( n − k )!
for k = n
n! n!
n Pn = = = n!
0! 1
Example How many permutations of size 3 can be found in
the group of 5 objects {A, B, C, D, E}
5!
Solution: 5 P3 = = 5 ( 4 )( 3) = 60
( 5 − 3) !
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ACB ADB AEB ADC AEC AED BDC BEC BED CED
BAC BAD BAE CAD CAE DAE CBD CBE DBE DCE
BCA BDA BEA CDA CEA DEA CDB CEB DEB DEC
CAB DAB EAB DAC EAC EAD DBC EBC EBD ECD
CAB DBA EBA DCA ECA EDA DCB ECB EDB EDC
Example We have a committee of n = 10 people and we want to
choose a chairperson, a vice-chairperson and a treasurer
Example We have a committee of n = 10 people and we want to
choose a chairperson, a vice-chairperson and a treasurer
Solution: Essentually we want to select 3 persons from the
committee of 10 in a specific order. (Permutations of size 3
from a group of 10).
10! 10!
10 P3 = = = 10 ( 9 )(8) = 720
(10 − 3)! 7!
Example We have a committee of n = 10 people and we want to choose a chairperson, a vice-
chairperson and a treasurer. Suppose that 6 of the members of the committee are male and 4
of the members are female. What is the probability that the three executives selected are all
male?
Example We have a committee of n = 10 people and we want to choose a
chairperson, a vice-chairperson and a treasurer. Suppose that 6 of the members of
the committee are male and 4 of the members are female. What is the probability that
the three executives selected are all male?
Solution: Again we want to select 3 persons from the
committee of 10 in a specific order. (Permutations of size 3
from a group of 10).The total number of ways that this can be
done is:
10! 10!
10 P3 = = = 10 ( 9 )(8) = 720
(10 − 3)! 7!
This is the size, N = n(S), of the sample space S. Assume all
outcomes in the sample space are equally likely.
Let E be the event that all three executives are male
6! 6!
n ( E ) = 6 P3 = = = 6 ( 5)( 4 ) = 120
( 6 − 3)! 3!
Hence
n(E) 120 1
PE = = =
n ( S ) 720 6
Thus if all candidates are equally likely to be selected to any
position on the executive then the probability of selecting an all
male executive is:
1
6
Examples - continued
3. Combinations of size k ( ≤ n): A combination of size k chosen
from n objects is a subset of size k where the order of
selection is irrelevant. How many ways can you choose a
combination of size k objects from n objects (order of
selection is irrelevant)
Here are the combinations of size 3 selected from the 5 objects
{A, B, C, D, E}
{A,B,C} {A,B,D} { A,B,E} {A,C,D} {A,C,E}
{A,D,E} {B,C,D} {B,C,E} {B,D,E} {C,D,E}
Important Notes
1. In combinations ordering is irrelevant. Different
orderings result in the same combination.
2. In permutations order is relevant. Different
orderings result in the different permutations.
How many ways can you choose a combination of size k
objects from n objects (order of selection is irrelevant)
is denoted by the symbol
n
n Ck or read “n choose k”
k
It is the number of ways of choosing k objects from n
objects (order of selection irrelevant).
nCk is also called a binomial coefficient.
It arises when we expand (x + y)n (the binomial
theorem)
The Binomial theorem:
( x + y)
n
= n C0 x 0 y n + n C1 x1 y n −1 + n C2 x 2 y n −2 +
+ n Ck x k y n−k + + n Cn x n y 0
n 0 n n 1 n −1 n 2 n −2
= x y + x y + x y +
0 1 2
n k n−k n n 0
+ x y + + x y
k n
Pascal’s triangle – a procedure for calculating binomial coefficients
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
• The two edges of Pascal’s triangle contain 1’s
• The interior entries are the sum of the two nearest
entries in the row above
• The entries in the nth row of Pascals triangle are the
values of the binomial coefficients
n n n n n n n
1
0 3 4 k n − 1 n
Pascal’s triangle
1
k
1 2
1 1 k
3
1 2 1
k
4
1 3 3 1
k
1 4 6 4 1 5
k
1 5 10 10 5 1 6
k
1 6 15 20 15 6 1 7
k
1 7 21 35 35 21 7 1
The Binomial Theorem
( x + y) = x + y
1
( )
2
x + y = x 2
+ 2 xy + y 2
( x + y ) = x + 3x y + 3xy + y
3 3 2 2 3
( )
4
x + y = x 4
+ 4 x 3
y + 6 x 2 2
y + 4 xy 3
+ y 3
( x + y)
5
= x5 + 5 x 4 y + 10 x 3 y 2 + 10 x 2 y 3 + 5 xy 4 + y 5
( x + y)
6
= x 6 + 6 x5 y + 15 x 4 y 2 + 20 x3 y 3 + 15 x 2 y 4 + 6 xy 5 + y 6
( x + y ) = x7 + 7 x6 y + 21x5 y 2 + 35x 4 y 3 + 35x3 y 4 + 21x 2 y 5 + 7 xy 6 + y 7
7
Basic counting formulae
1. Orderings
n ! = the number of ways you can order n objects
2. Permutations
n!
n Pk = = The number of ways that you can
( n − k )! choose k objects from n in a
specific order
3. Combinations
n n!
= n Ck = = The number of ways that you
k k !( n − k )! can choose k objects from n
(order of selection irrelevant)
Applications to some counting problems
• The trick is to use the basic counting formulae
together with the Rules
• We will illustrate this with examples
• Counting problems are not easy. The more practice
better the techniques
Application to Lotto 6/49
• An application of combinations, hypergeometric distribution, and
expected value
• Used to understand rare events
• Understanding winning numbers and bonus
using set representation
Application to Lotto 6/49
Problem statement
• Six winning numbers are drawn from the numbers 1 to 49, one additional
number, called the bonus number, is drawn at random from the remaining
numbers not among the six winning numbers.
• The bonus number is not used to determine the jackpot, but it is used to define
additional prize categories such as matching 5 winning numbers plus the bonus.
Role of Bonus Number
• Bonus is drawn from remaining 43 numbers
• Does NOT affect jackpot
• Creates intermediate prize categories
Total Possible Tickets
• Order does not matter → combinations
• Total tickets = C(49,6) = 13,983,816
Jackpot Probability
• To win jackpot: match all 6 numbers Six numbers are chosen from the six
winning numbers,
6
• P(Jackpot) = 1 / C(49,6) = 1
6
• = 1 / 13,983,816
You can lose and win in several ways
1. No winning numbers – lose
2. One winning number – lose
3. Two winning numbers - lose
4. Two + bonus – win $5.00
5. Three winning numbers – win $10.00
6. Four winning numbers – win approx. $80.00
7. 5 winning numbers – win approx. $2,500.00
8. 5 winning numbers + bonus – win approx. $100,000.00
9. 6 winning numbers (jackpot) – win approx. $4,000,000.00
Jackpot Probability
• To win jackpot: match all 6 numbers
• P(Jackpot) = 1 / C(49,6)
• = 1 / 13,983,816
5 Numbers + Bonus
• Choose 5 of 6 winning numbers: C(6,5)
• Choose bonus: C(1,1)
• P = C(6,5)/C(49,6)
Counting the possibilities
1. No winning numbers – lose
All six of your numbers have to be chosen from the losing numbers
and the bonus.
43
= 6,096,454
6
2. One winning numbers – lose
One number is chosen from the six winning numbers and the
remaining five have to be chosen from the losing numbers and the
bonus.
6 43
= 6 ( 962,598 ) = 5,775,588
1 5
3. Two winning numbers – lose
Two numbers are chosen from the six winning numbers and the
remaining four have to be chosen from the losing numbers (bonus
not included)
6 42
= 15 (111,930 ) = 1,678,950
2 4
4. Two winning numbers + the bonus – win $5.00
Two numbers are chosen from the six winning numbers, the
bonus number is chose and the remaining three have to be chosen
from the losing numbers.
6 1 42
= 15 (1)(11,480 ) = 172,200
2 1 3
5. Three winning numbers – win $10.00
Three numbers are chosen from the six winning numbers and the
remaining three have to be chosen from the losing numbers + the
bonus number
6 43
= 20 ( 12,341) = 246,820
3 3
6. four winning numbers – win approx. $80.00
Four numbers are chosen from the six winning numbers and the
remaining two have to be chosen from the losing numbers + the
bonus number
6 43
= 15 ( 903) = 13,545
4 2
7. five winning numbers (no bonus) – win approx. $2,500.00
Five numbers are chosen from the six winning numbers and the
remaining number has to be chosen from the losing numbers
(excluding the bonus number)
6 42
= 6 ( 42 ) = 252
5 1
8. five winning numbers + bonus – win approx. $100,000.00
Five numbers are chosen from the six winning numbers and the
remaining number is chosen to be the bonus number
6 1
= 6 (1) = 6
5 1
9. six winning numbers (no bonus) – win approx. $4,000,000.00
Six numbers are chosen from the six winning numbers,
6
= 1
6
Summary
n Prize Prob
0 winning 6,096,454 nil 0.4359649755
1 winning 5,775,588 nil 0.4130194505
2 winning 1,678,950 nil 0.1200637937
2 + bonus 172,200 $ 5.00 0.0123142353
3 winning 246,820 $ 10.00 0.0176504039
4 winning 13,545 $ 80.00 0.0009686197
5 winning 252 $ 2,500.00 0.0000180208
5 + bonus 6 $ 100,000.00 0.0000004291
6 winning 1 $ 4,000,000.00 0.0000000715
Total 13,983,816