HANOI NATIONAL UNIVERSITY OF EDUCATION

FACULTY OF MATHEMATICS AND INFORMATICS

———————o0o——————–

PROJECT - GROUP 2
TOPIC 2: BASIC COUNTING PRINCIPLES

Subject: Elementary Algebra

Instructor: Dr. Nguyen Quang Loc

List of Students: 06. Nguyen Thanh Binh – 725121006

07. Trinh Ngoc Chau – 745121011
08. Doan Mai Chi – 725121008
09. Le Quynh Chi – 725121009
10. Nguyen Thi Ha Giang – 725121011

Class: MATH413E K72MathE

HANOI - 2025
Contents
PREFACE 2

1 THE ADDITION AND MULTIPLICATION PRINCIPLES 3

1.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Addition Principle . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Multiplication Principle . . . . . . . . . . . . . . . . . . . . . 4
1.2 Prove some formulas: Permutation and Combination . . . . . . . . . 5
1.2.1 Permutation Formula . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Combination Formula . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 THE INCLUSION-EXCLUSION PRINCIPLE 11

2.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 The Principle of Subtraction . . . . . . . . . . . . . . . . . . . 11
2.1.2 The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . 12
2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1
PREFACE
The basic counting principles play an important role in elementary combina-
torics and are widely applied in many problems in mathematics and real life. These
principles include the addition principle and the multiplication principle, which are
simple yet powerful tools to count the number of possible outcomes in a variety of
situations.
Although these principles are elementary, they form the foundation for more ad-
vanced methods in combinatorics and discrete mathematics. Through the use of
basic counting principles, one can solve problems involving arrangements, selec-
tions, and distributions efficiently and logically.
In mathematics education, especially for students with a strong interest in problem
solving and competitions, these principles are essential tools. They frequently appear
in school exams, contests, and also in real-world contexts such as scheduling, coding,
and data organization.
This report presents a clear explanation of the fundamental counting principles along
with several practical applications and examples. We hope that this document will
be useful for teachers, students, and anyone interested in learning or teaching basic
combinatorics.
We welcome any comments and suggestions to help improve the quality of this
material.

Hanoi, June 2025

Group 2

2
1 THE ADDITION AND MULTIPLICATION PRIN-
CIPLES
1.1 Theory
1.1.1 Addition Principle

Let A1 , A2 , . . . , Am be finite sets that are pairwise disjoint. Then:

m
X
N (A1 ∪ A2 ∪ · · · ∪ Am ) = N (Ai ).
i=1

Remark 1.1. We always have

m
X
N (A1 ∪ A2 ∪ · · · ∪ Am ) ≤ N (Ai ),
i=1

and equality holds if and only if A1 , A2 , . . . , Am are pairwise disjoint.

Proof. To prove this remark, we consider the following lemma:

N (A ∪ B) ≤ N (A) + N (B).

Equality holds if and only if A ∩ B = ∅.

ˆ If A ∩ B = ∅, then N (A ∪ B) = N (A) + N (B).

ˆ If A ∩ B ̸= ∅, assume N (A ∩ B) = k ≥ 1. In this case, the elements in A ∩ B

are counted twice in N (A) + N (B), so we must subtract the intersection:

N (A ∪ B) = N (A) + N (B) − N (A ∩ B) < N (A) + N (B).

Hence, we have proved the lemma. Now apply it to two sets A1 and A2 :

N (A1 ∪ A2 ) ≤ N (A1 ) + N (A2 ),

with equality if and only if A1 ∩ A2 = ∅.

Now apply the lemma again to (A1 ∪ A2 ) and A3 :

N (A1 ∪ A2 ∪ A3 ) = N ((A1 ∪ A2 ) ∪ A3 ) ≤ N (A1 ∪ A2 ) + N (A3 )

≤ N (A1 ) + N (A2 ) + N (A3 ).

Equality occurs if and only if

( (
(A1 ∪ A2 ) ∩ A3 = ∅ (A1 ∩ A3 ) ∪ (A2 ∩ A3 ) = ∅
⇔
A1 ∩ A2 = ∅ A1 ∩ A2 = ∅

3
 
A1 ∩ A3 = ∅

Thus we get A2 ∩ A3 = ∅

A1 ∩ A2 = ∅

Repeating the same argument, we obtain the desired result.
Example 1.2. There are two restaurants in our neighborhood, Pizza Shop and Soup
Kitchen. Pizza Shop has 10 different pizzas on its menu, and Soup Kitchen has 15
soups on its menu. The number of different options for lunch if we buy our lunch
from either of these restaurants is...

Solution

There are 10 + 15 = 25 options.

Example 1.3. A bakery has a selection of 20 different cupcakes, 10 different donuts,
and 15 different muffins. If you are to select a tasty treat, how many different choices
of sweets can you choose from?

Solution

Because we have to choose from either a cupcake or donut or muffin (notice the
“OR”), we have 20 + 10 + 15 = 45 (treats) to choose from.

1.1.2 Multiplication Principle

If A1 , A2 , . . . , Am are finite sets, then

N (A1 × A2 × · · · × Am ) = N (A1 )N (A2 ) . . . N (Am ).

General principles.
ˆ If a task can be broken down into m consecutive steps.

ˆ Suppose step 1 can be performed in n1 ways.

ˆ For each of these, step 2 can be performed in n2 ways, and for each of these
step 3 can be performed in n3 ways,. . . And so on up to m.

ˆ Then the task can be completed in n1 · n2 · · · · · nm ways.

Example 1.4. Let A and B be sets with m and n elements, respectively. Find the
number of functions from A to B.

Solution

Assume A = {a1 , a2 , . . . , am } and B = {b1 , b2 , . . . , bn }.

Since each element of A must map to an element in B, we choose:
ˆ f (a1 ): n choices,

4
 ˆ f (a2 ): n choices,
..
ˆ .
ˆ f (am ): n choices.
Hence, by the multiplication principle, the number of functions from A to B is nm .
Example 1.5. A lottery ticket number is formed by two parts: the first part has 3
letters chosen from the 26-letter alphabet, and the second part has 4 digits chosen
from the decimal system. How many different tickets can be issued?
Solution
By the multiplication principle, the letter part has 263 possibilities.
Similarly, the number part has 104 possibilities.
Therefore, the total number of tickets is 263 · 104 .

1.2 Prove some formulas: Permutation and Combination

1.2.1 Permutation Formula
Definition 1.6. A permutation is the arrangements of r things from a set of n
things without replacement. Order matters in the permutation.
n!
Arn =
(n − r)!
Proof. Let us assume that there are r boxes and each of them can hold one thing.
Find the number of ways of filling in r vacant boxes by n different objects.
Number of ways the first box can be filled: n
Number of ways the second box can be filled: (n − 1)
Number of ways the third box can be filled: (n − 2)
Therefore, number of ways of filling in r boxes in succession can be given by:
n(n − 1)(n − 2)(n − 3) . . . (n − (r − 1))
This can be written as:
n(n − 1)(n − 2) . . . (n − r + 1)
The number of permutations of n different objects taken r at a time, where 0 < r ≤ n
and the objects do not repeat is:
n(n − 1)(n − 2)(n − 3) . . . (n − r + 1)

⇒ Arn = n(n − 1)(n − 2)(n − 3) . . . (n − r + 1)

[n(n − 1)(n − 2) . . . (n − r + 1)(n − r)(n − r − 1) . . . 3 × 2 × 1] n!

⇒ Arn = =
(n − r)(n − r − 1) . . . 3 × 2 × 1 (n − r)!
where 0 < r ≤ n
Remark 1.7. The number of permutations of n distinct objects is n factorial.
P = n(n − 1)(n − 2)...2.1 = n!

5
1.2.2 Combination Formula
Definition 1.8. A combination is the choice of r things from a set of n things
without replacement. The order does not matter in combination. It may also be
the number of subsets with r elements from a set of n elements.
 
r n n!
Cn = = .
r (n − r)!.r!
Proof. We prove this formula based on Permutation Formula.
We adjust our permutation formula to reduce it by how many ways the objects
could be in order (because we aren’t interested in their order any more). There are
r objects, so the number of ways the objects could be in order equals the number of
permutations of r distinct objects.
Hence,  
n n! 1 n!
= × = .
r (n − r)! r! r!(n − r)!

1.3 Exercises
Exercise 1: A class has 15 boys and 5 girls. All students are arranged in a straight
line for a group photo.

a) How many different ways can the students be arranged?

b) What is the probability that all boys stand together and all girls also stand
together?

Solution

a) There are 15 + 5 = 20 students.

The first position can be chosen in 20 different ways.
The second position can be chosen in 19 different ways.
............
The last position can be chosen in only 1 way.
Using Multiplication Principle, the number of ways to arrange 20 students is

20.19.18...2.1 = 20!

b) We have:
The number of ways to arrange 15 boys is 15!
The number of ways to arrange 5 girls is 5!
Case 1: The boys stands to the right of the girls.
Using Multiplication Principle, the number of ways to arrange 20 students is
15!.5!

6
 Similarly with Case 2: The boys stands to the left of the girls.
Through both cases, using Addition Principle, the number of ways to arrange
20 students is 2.15!.5!
The probability that all boys stand together and all girls also stand together
2 · 15! · 5!
is:
20!

Exercise 2.1: Five men and nine women stand equally spaced around a circle in
random order. Find the number of arrangements of the above people.

Solution

There are total 9 + 5 = 14 people.

First pin one man on one seat (to ensure no rotate situations). Then we arrange
the remaining 13 people.
Hence the number of arrangements of the above people is 13!
Remark 1.9. The above case is called a Circular Permutation. The number of
circular permutations of n elements is: (n − 1)!
Exercise 2.2: (Problem 1: 2023 AIME I)
Five men and nine women stand equally spaced around a circle in random order.
m
The probability that every man stands diametrically opposite a woman is , where
n
m and n are relatively prime positive integers. Find m + n.

Solution

7
First pin one man on one seat (to ensure no rotate situations). Then there are 13!
arrangements. (Exercise 2.1)
Therefore,

N (Ω) = 13!

Let A be the event: ”All people are arranged in a circle such that every man stands
diametrically opposite a woman.”
Remember that it has 5 men and 9 women. Therefore, there are 4 men left.
The first man has 12 ways to choose his position. (Because there are total 14
positions, we subtract the 2 positions of the man pinned and his partner.)
Similarly, the second man has 10 ways to choose his position. The third man has 8
ways to choose his position. And the last man has 6 ways to choose his position.
Hence the number of ways to arrange 5 men is 12.10.8.6.

There are a total of 9 women. Therefore, the number of ways to choose 5 women to
stand opposite the 5 men above is: A59

There are 4 women left. The number of ways to arrange them into the remaining 4
positions is: 4!
Hence

N (A) = 12.10.8.6.A59 .4!

N (A) 12.10.8.6.A59 .4! 48

P = = = .
N (ω) 13! 143

The answer is

48 + 143 = 191 .

Exercise 3.1: Determine the number of positive integer solutions of the equation

x1 + x2 + · · · + xm = n, n ∈ N

Euler’s candy division problem: Distributing n candies to k children.

First, we count the number of ways to distribute the candies so that each child
receives at least one candy.
We arrange the n candies in a straight line.

There are exactly n − 1 gaps between the candies. We place dividers in these gaps
to divide the candies into k parts.

8
We give the first part to the first child, the second part to the second child, and so
on, with the last part going to the kth child.
Clearly, the number of ways to distribute the candies is exactly the number of ways
to place the dividers as described above.

Choose k − 1 gaps among the n − 1 available gaps to place the dividers. There are
k−1
Cn−1 ways to do this. This is also the answer to the problem.
From this result, we can derive other equivalent formulations of the problem such
as Exercise 3.1.

Return to Exercise 3.1: Determine the number of positive integer solutions of

the equation
x1 + x2 + · · · + xm = n, n ∈ N

Solution

Let xi represent the number of candies received by the ith child in the candy distri-
bution problem.
Then, the number of solutions to the equation is exactly the number of ways to
distribute n candies to m children.
m−1
Therefore, the number of positive integer solutions is Cn−1

Note: To find the number of non-negative integer solutions to the above equation,
we just need to add 1 to each term. Then, the problem will become Exercise 3.1.

x1 + x2 + · · · + xm = n
⇒ (x1 + 1) + (x2 + 1) + · · · + (xm + 1) = n + m

Put yi = xi + 1. We have the number of non-negative integer solutions to the above

equation equals the number of positive integer solutions to the equation y1 + y2 +
· · · + ym = n + m, n, m ∈ N
m−1
Hence, the number of non-negative integer solutions is Cn+m−1

Exercise 3.2 (Hanoi Contest for Selecting the Team of Excellent Students,
2020–2021): Find the number of positive integer tuples (a1 , a2 , · · · , a15 ) that satisfy
the following conditions:

1. 1 ≤ a1 < a2 < · · · < a15 ≤ 2020;

2. ai ≡ i2 (mod 5), ∀i = 1, 2, . . . , 15.

Solution

First, we consider the remainder of ai when divided by 5.

i 1 2 3 4 5 6 ... 14 15
ai ≡ i2 mod 5 1 4 4 1 0 1 ... 1 0

9
We put

a1 = 5k1 − 4
a2 − a1 = 5k2 − 2
a3 − a2 = 5k3
a4 − a3 = 5k4 − 3
a5 − a4 = 5k5 − 1
a6 − a5 = 5k6 − 4
..
.
a15 − a14 = 5k15 − 1
2020 − a15 = 5k16 − 5,

with ki is positive integer.

Summing both sides, we get

2020 = 5(k1 + k2 + · · · + k16 ) − 35 ⇒ k1 + k2 + · · · + k16 = 411.

Remember that ki is positive integer. According to the result of Exercise 3.1, the
above equation has
m−1 15
Cn−1 = C410
sets of positive integer solutions.

10
2 THE INCLUSION-EXCLUSION PRINCIPLE
2.1 Theory
2.1.1 The Principle of Subtraction

Let X be a subset of A, then:

N (A \ X) = N (A) − N (X).

This principle is often used with the philosophy: ”Count the easy part to deduce
the difficult part”. The following example illustrates this principle.

Example 2.1. Five people stand in a line. Calculate the probability that person A
does not stand next to person B.

Solution

There are 5! = 120 total arrangements. To count the number of arrangements where
A does not stand next to B, we first count the opposite case: A stands next to B.
Treat A and B as a single block. There are 4! ways to arrange this block with the
others. Since A and B can switch positions within the block, we have:

2 · 4! = 48.

So the number of arrangements where A does not stand next to B is:

5! − 2 · 4! = 72.

Therefore, the probability is:

72
= 0.6.
120
Example 2.2. On each side of a square, select n distinct points. How many triangles
can be formed from these points?

Solution

Any 3 non-collinear points form
a triangle. There are 4n

3
ways to choose 3 points
n
from the total. There are 4 · 3 ways to choose 3 points on the same side. So the
number of valid triangles is:    
4n n
−4 .
3 3

11
2.1.2 The Principle of Inclusion-Exclusion
Let A = A1 ∪ A2 ∪ . . . ∪ An , where A1 , A2 , . . . , An are finite sets. To find the number
of elements in set A, we proceed as follows.
First, for each fixed k such that 1 ≤ k ≤ n, consider the intersection of any k sets
among the initial n sets. Let Nk denote the total number of elements in all such
intersections.
Then we have:
n
X X
N1 = N (Ai ); N2 = N (Ai ∩ Aj );
i=1 1≤i<j≤n

X
Nk = N (Ai1 ∩ Ai2 ∩ . . . ∩ Aik );
1≤i1 <i2 <...<ik ≤n

Nn = N (A1 ∩ A2 ∩ . . . ∩ An ).

Remark 2.3. The quantity Nk has nk terms. The principle of inclusion-exclusion

is then proved using the following lemma:

Lemma 2.4. n
X
N (A1 ∪ A2 ∪ . . . ∪ An ) = (−1)k−1 Nk . (1)
k=1

Proof. Let x ∈ A1 ∪ A2 ∪ · · · ∪ An . Clearly, in the left-hand side of the identity (1),

x is counted exactly once.
To prove identity (1), we must show that in the right-hand side, x is also counted
exactly once.
Suppose that x belongs to exactly k of the
sets among A1 , A2 , . . . , An . Then, for
k
each t ≤ k, the element x will appear in t of the intersections contributing to the
term Nt . For t > k, x will not be included at all.
Therefore, in the right-hand side of (1), the total number of times x is counted is:
k   k  !
X k X k
(−1)t−1 =1− 1− (−1)t−1 = 1 − (1 − 1)k = 1.
t=1
t t=1
t

Thus, identity (1) holds.

Statement of the Inclusion-Exclusion Principle:
Suppose A1 , A2 , . . . , An are subsets of a finite set X with |X| = N . We want to
count the number of elements in X that are not in the union A1 ∪ A2 ∪ · · · ∪ An ,
that is:

|X \ (A1 ∪ A2 ∪ · · · ∪ An )| = N − |A1 ∪ A2 ∪ · · · ∪ An |.
Using the inclusion-exclusion principle, we have:

|X \ (A1 ∪ A2 ∪ · · · ∪ An )| = N − N1 + N2 − N3 + · · · + (−1)n Nn

12
where Nk denotes the sum of the cardinalities of all k-fold intersections of the sets
Ai .
This formula is known as the Inclusion-Exclusion Principle, a powerful tool in
combinatorics.
Example 2.5. There are n letters and n envelopes, each labeled with an address.
The letters are randomly placed into the envelopes.
(a) What is the probability that no letter ends up in the correct envelope?

(b) What is the probability that exactly k letters (with 0 ≤ k ≤ n) end up in the
correct envelopes?

Solution

(a) The total number of ways to assign the letters into envelopes is n!.
Let X be the set of all such permutations.
Let Ak be the set of permutations where the k-th letter is placed in the correct
envelope.
Then we have n subsets: A1 , A2 , . . . , An . To count the number of derangements
(i.e., permutations with no fixed points), we apply the inclusion-exclusion prin-
ciple.
Note that:
|Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = (n − k)!
because we fix k positions and permute the remaining n − k letters.
There are nk such intersections, so:

 
n n!
Nk = (n − k)! =
k k!

Therefore, the number of derangements is:

n
X (−1)k
Dn = n!
k=0
k!

Thus, the desired probability in part (a) is:

n
Dn X (−1)k
=
n! k=0
k!

(b) We want the probability that exactly k letters are in the correct envelopes.
The number of derangements of n − k elements is:
n−k
X (−1)j
Dn−k = (n − k)!
j=0
j!

13
 Thus, the number of favorable permutations is:
n−k
(−1)j
   
n n X
· Dn−k = (n − k)!
k k j=0
j!

Finally, the desired probability is:

n−k
(−1)j
 
1 n X
P (k, n) = (n − k)!
n! k j=0
j!

2.2 Exercises
Exercise 1: Determine the number of surjections (onto functions) from a set A
with m elements to a set B with n elements.

Solution

If m < n, the answer is zero, so assume m ≥ n.

Let X be the set of all functions from A to B. ⇒ N (X) = nm .
Assume that B = {1; 2; ...; n}.
Let Ai be the set of functions of X such that its images do not contain i.
Then, the number of surjections is
n
X
N = N [X \ (A1 ∪ A2 ∪ ... ∪ An )] = N (X) − (−1)k−1 Nk
k=1

and X
Nk = N (Ai1 ∩ Ai2 ∩ ... ∩ Aik )
1≤i1 <i2 <...<ik ≤n

We see that N (Ai1 ∩ Ai2 ∩ ... ∩ Aik ) is the number of functions from A to the set of
(n − k) elements .

⇒ N (Ai1 ∩ Ai2 ∩ ... ∩ Aik ) = (n − k)m

Therefore,
Nk = Cnk .(n − k)m
n
X n
X
k
Thus, N = n + m
(−1) Cnk .(n m
− k) = (−1)k Cnk .(n − k)m .
k=1 k=0

Application of Exercise 1: Stirling Numbers of the Second Kind

Definition 2.6. A Stirling number of the second kind, denoted by S(n, k), is the
number of ways to partition a set of n labeled objects into k nonempty unlabeled
subsets.

14
By applying the result of Exercise 1, we obtain:
k
1 X
S(n, k) = (−1)i Cki (k − i)n
k! i=0

Exercise 2: Given a1 , a2 , . . . , an are integers greater than 1 and pairwise relatively

prime. How many of the first m positive integers are not divisible by any of the
given numbers?

Solution

Let X = {1, 2, . . . , m} and let Ai be the set of numbers in X that are divisible by
ai . Then we obtain A1 , A2 , . . . , An as subsets of X.
It is clear that the number of desired numbers is

N = N [X \ (A1 ∪ A2 ∪ . . . ∪ An )]

and N = N (X) = m.
We have:
X
Nk = N (Ai1 ∩ Ai2 ∩ . . . ∩ Aik )
1≤i1 <i2 <...<ik ≤n

where
N (Ai1 ∩ Ai2 ∩ . . . ∩ Aik ) = the number of elements in X hdivisiblei by ai1 , . . . , aik
= the number of elements in X divisible by ai1 . . . aik = ai m ...aik
1
Thus,
 
X m
Nk =
1≤i <i <...<i ≤n
ai1 . . . aik
1 2 k

Therefore,
n  
X
k−1
X m
N =m− (−1)
k=1 1≤i1 <i2 <...<ik ≤n
ai1 . . . aik
n  
X
k
X m
=m+ (−1)
k=1 1≤i <i <...<i ≤n
ai1 . . . aik
1 2 k

Exercise 3: (Euler’s formula) For every integer n > 1, let φ(n) denote the number
of positive integers less than n that are coprime to n. Prove that
m
Y 1
φ(n) = n (1 − )
i=1
pi

where n = pα1 1 .pα2 2 . . . pαmm is the standard prime factorization of n, in which p1 , p2 , . . . , pm

are all the distinct prime divisors of n.

Solution

15
Let S be the set of the first n positive integers and let Ai be the subset of S consisting
of numbers divisible by pi , where i = 1, 2, . . . , m.
Then, the set S \ (A1 ∪ A2 ∪ . . . ∪ Am ) consists of the positive integers less than n
that are coprime to n.
For 1 ≤ i1 < . . . < ik ≤ m, we have:
h i
n
N (Ai1 ∩ Ai2 ∩ . . . ∩ Aik ) = pi ...p i
= pi pin...pi
1 k 1 2 k

and
X
Nk = N (Ai1 ∩ Ai2 ∩ . . . ∩ Aik )
1≤i1 <i2 <...<ik ≤m

By the Inclusion-Exclusion Principle, we have:

φ(n) = N [S \ (A1 ∪ A2 ∪ . . . ∪ Am )]
= N (S) − N (A1 ∪ . . . ∪ Am )
Xm
=n− (−1)k−1 Nk
k=1
m
X n X n n
=n− + − . . . + (−1)m
i=1
pi 1≤i<j≤m pi pj p 1 . . . pm
m
!
X 1 X 1 1
=n 1− + − . . . + (−1)m
p
i=1 i
pp
1≤i<j≤m i j
p 1 . . . pm
m  
Y 1
=n 1−
i=1
pi

Exercise 4: Given a determinant of order n, where all the elements on the main
diagonal are zero and the other elements are nonzero real numbers. How many terms
in this determinant are equal to 0?
Recall
X n
Y
det(A) = sign(σ) aiσ(i)
σ∈Sn i=1

Solution

This leads to an equivalent problem of counting the number of permutations σ ∈ Sn

such that there exists i ∈ {1, 2, . . . , n} with σ(i) = i.
Define Ai := {σ ∈ Sn : σ(i) = i}.
X \k
Tk
N ( j=1 Aij ) = (n − k)! ⇒ Nk = N ( Aij ) = Cnk (n − k)!
1≤i1 <i2 <...<ik ≤n j=1

16
Thus, the number of satisfied permutations is
n
X n
X
(−1)k−1 Nk = (−1)k−1 Cnk (n − k)!
k=1 k=1
n
X n!
= (−1)k−1
k=1
k!
n
X (−1)k−1
= n!
k=1
k!

Exercise 5: A box contains 5 distinct red marbles, 4 distinct yellow marbles and 9
distinct blue marbles. How many ways are there to choose 6 marbles such that all
three colors are represented?

Solution

Let X be the set of all possible ways to choose any 6 marbles.

Let A be the set of ways to choose 6 marbles such that no red marbles are included.
Let B be the set of ways to choose 6 marbles such that no yellow marbles are
included.
Let C be the set of ways to choose 6 marbles such that no blue marbles are included.
Then, the set of ways to choose 6 marbles such that all three colors are represented
is X \ (A ∪ B ∪ C).
By the Inclusion-Exclusion Principle, we have:

N [X \ (A ∪ B ∪ C)] = N (X) − N (A) − N (B) − N (C)

+ N (A ∩ B) + N (B ∩ C) + N (A ∩ C) − N (A ∩ B ∩ C)

ˆ N (X) = C18
6

ˆ N (A) = C13
6 6
, N (B) = C14 , N (C) = C96

ˆ N (A ∩ B) = C96 , N (B ∩ C) = 0, N (A ∩ C) = 0

ˆ N (A ∩ B ∩ C) = 0
6 6 6
⇒ N [X \ (A ∪ B ∪ C)] = C18 − C13 − C14 − C96 + C96 + 0 + 0 − 0 = 13845
Therefore, there are 13845 ways to choose 6 marbles such that all three colors are
represented.
Exercise 6: Find the number of non-negative integer roots of the equation:

x1 + x2 + x3 + x4 = 15

such that
x1 ≤ 3, x2 ≤ 4, x3 ≤ 5, x4 ≤ 7.

Solution

17
Let U be the set of all non-negative integer roots of the equation

x1 + x2 + x3 + x4 = 15

We recall the Euler’s candy division problem: How many ways to distribute n
identical candies to m children such that each child has at least one candy?
Equivalently, we need to find the number of positive integer roots of the equation

x1 + x2 + ... + xm = n(n ≥ m ≥ 1)

Remark 2.7. The number of positive integer roots of the equation

m−1
x1 + x2 + ... + xm = n (n ≥ m ≥ 1) is Cn−1 .

Corollary 2.8. The number of non-negative integer roots of the equation

m−1
x1 + x2 + ... + xm = n is Cn+m−1 .

Apply corollary 3.8 to the original problem, we have:

3
N (U ) = C18 = 816.

Let A1 be the set of non-negative integer roots satisfying x1 ≥ 4.

Let A2 be the set of non-negative integer roots satisfying x2 ≥ 5.
Let A3 be the set of non-negative integer roots satisfying x3 ≥ 6.
Let A4 be the set of non-negative integer roots satisfying x4 ≥ 8.
Then, according to the inclusion-exclusion principle, the number of roots to be found
is
X4
N = N (U ) − N (A1 ∪ A2 ∪ A3 ∪ A4 ) = N (U ) − (−1)k−1 Nk
k=1

and X
Nk = N (Ai1 ∩ Ai2 ∩ ... ∩ Aik )
1≤i1 <i2 <...<ik ≤4

Apply corollary 3.8, we have:

ˆ N (A1 ) = C14
3 3
= 364, N (A2 ) = C13 3
= 286, N (A3 ) = C12 3
= 220, N (A4 ) = C10 =
120 ⇒ N1 = 990.

ˆ N (A1 ∩A2 ) = C93 = 84, N (A1 ∩A3 ) = C83 = 56, N (A1 ∩A4 ) = C63 = 20, N (A2 ∩
A3 ) = C73 = 35, N (A2 ∩ A4 ) = C53 = 10, N (A3 ∩ A4 ) = C43 = 4 ⇒ N2 = 209.

ˆ N (A1 ∩ A2 ∩ A3 ) = 1, N (A1 ∩ A2 ∩ A4 ) = 0, N (A1 ∩ A3 ∩ A4 ) = 0, N (A2 ∩ A3 ∩

A4 ) = 0 ⇒ N3 = 1.

ˆ N4 = N (A1 ∩ A2 ∩ A3 ∩ A4 ) = 0.

⇒ N = 816 − 990 + 209 − 1 + 0 = 34 .

Exercise 7: From five digits 1, 2, 3, 4, 5, how many 10-digit numbers can be formed
that satisfy two following conditions:

18
a) In each number, each digit appears exactly two times?

b) In each number, two identical digits are not next to each other?

Solution

Let A be the set of all 10-digit numbers composed of 1, 2, 3, 4, 5, satisfying the

condition a).
For each i = 1, 5, let Ai be all numbers in A such that in each number, 2 digits i are
next to each other.
Then, according to the inclusion-exclusion principle, the number of satisfied
numbers is
5
X
N = N (A) − N (A1 ∪ A2 ∪ ... ∪ A5 ) = N (A) − (−1)k−1 Nk
k=1

and X
Nk = N (Ai1 ∩ Ai2 ∩ ... ∩ Aik )
1≤i1 <i2 <...<ik ≤5

We have:
10!
N (A) = = 113400
25
For each number in Ai , consider 2 adjacent digits i as 1 digit.
This means that N (Ai ) is the number of ways we arrange 9 digits where there are
4 digits appearing two times.
9! 9!
⇒ N (Ai ) = ⇒ N1 = 5 · = 113400
24 24
Using the above argument, we can generalize that:

(10 − k)!
Nk = C5k · , ∀k = 1, 5.
25−k
⇒ N2 = 50400, N3 = 12600, N4 = 1800, N5 = 120.
⇒ N = 113400 − 1133400 + 50400 − 12600 + 1800 − 120 = 39480 .
Exercise 8: How many ways are there to arrange 8 rooks on an international
chessboard with a main diagonal crossed out so that no rook can attack another?

Solution

Let U be all arrangements of 8 rooks so that no rook can attack another.

There are 8.8 places for the initial rook.
Since 2 rooks do not lie on the same row or column, there are 7.7 places for the
second rook.
Similarly, it implies that there are (8!)2 places for 8 rooks.
But we must consider duplicates as all rooks are considered the same.
Therefore,
(8!)2
N (U ) = = 8!
8!

19
We will count the number of arrangements so that there is at least 1 rook on the
diagonal.
Let Ai be the set of arrangements such that the rooks are placed on the square (i, i),
for i = 1, 8.
We need to determine N (A1 ∪ A2 ∪ ... ∪ A8 ).
We see that N (Ai ) is the number of arrangements for 7 rooks that are not in the
i-th row and column.
Thus, N (Ai ) = 7!, ∀i = 1, 8.
Similarly, N (Ai ∩ Aj ) = 6!, N (Ai ∩ Aj ∩ Ak ) = 5!, ..., N (A1 ∩ A2 ∩ ... ∩ A8 ) = 1!.
Then, according to the inclusion-exclusion principle, the number of satisfied
arrangements is
8
X X
N = N (U ) − N (Ai ) + N (Ai ∩ Aj ) − ... + N (A1 ∩ A2 ∩ ... ∩ A8 )
i=1 1≤i̸=j≤8

⇒ N = 8! − C81 .7! + C82 .6! − C83 .5! + C84 .4! − C85 .3! + C86 .2! − C87 .1! + C88 .0! = 14833

The End

20