Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathematics (PCC-CSM405/ PCC-CSD405/ PCC-CSG405)
Academic Session: 2024-25
Study Material
(Discrete Mathematics (PCC-CSM405)
_____________________________________________________________________________________________
Table of Contents
Module II:
Counting techniques
Sl no. Topic Page no.
1. Introduction 2
2. Basic Counting Principles: 2
3. The Inclusion-Exclusion Principle. 3
4. Permutations and Combinations 4
5. Recurrence relation 11
6. Practice Questions 18
7. References 21
Department of Mathematics
Brainware University, Kolkata 1
, Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathematics (PCC-CSM405/ PCC-CSD405/ PCC-CSG405)
Academic Session: 2024-25
Module 2 Counting techniques
C ounting techniques, also known as combinatorics, is a branch of mathematics concerned with counting and
organizing the number of possibilities or arrangements of objects. Combinatorics is fundamental to various
areas of mathematics, computer science, and other disciplines.
Combinatorics can be traced back more than 3000 years to India and China. For many centuries, it primarily
comprised the solving of problems relating to the permutations and combinations of objects. The use of the word
“combinatorial” can be traced back to Leibniz in his dissertation on the art of combinatorial in 1666. Over the
centuries, combinatorics evolved in recreational pastimes. In the modern era, the subject has developed both in
depth and variety and has cemented its position as an integral part of modern mathematics. Undoubtedly part of
the reason for this importance has arisen from the growth of computer science and the increasing use of
algorithmic methods for solving real-world practical problems. These have led to combinatorial applications in a
wide range of subject areas, both within and outside mathematics, including network analysis, coding theory,
and probability.
Suppose that a password on a computer system consists of six, seven, or eight characters. Each of these
characters must be a digit or a letter of the alphabet. Each password must contain at least one digit. How many
such passwords are there? The techniques needed to answer this question and a wide variety of other counting
problems will be introduced in this section.
Counting problems arise throughout mathematics and computer science. For example, we must count the
successful outcomes of experiments and all the possible outcomes of these experiments to determine
probabilities of discrete events. We need to count the number of operations used by an algorithm to study its
time complexity. We will introduce the basic techniques of counting in this section. These methods serve as the
foundation for almost all counting techniques.
Basic Counting Principles:
We will present two basic counting principles, the product rule and the sum rule. Then we will show how they
can be used to solve many different counting problems. The product rule applies when a procedure is made up of
separate tasks.
The Rule of Product:
If a task can be performed in m ways and another independent task can be performed in n ways, then the
combination of both tasks can be performed in mn ways.
Set theoretical version of the rule of product:
Let A × B be the Cartesian product of sets A and B. Then:
|A × B| = |A| · |B| . More generally: |A_1 × A_2 × · · · × A_n| = |A_1 | · |A_2 | · · · |A_n | .
For instance, assume that a license plate contains two letters followed by three digits. How many different
license plates can be printed?
Answer: Each letter can be printed in 26 ways, and each digit can be printed in 10 ways, so 26 · 26 · 10 · 10 · 10
= 676000 different plates can be printed.
Exercise: Given a set A with m elements and a set B with n elements, find the number of functions from A to B.
The Rule of Sum:
If a task can be performed in 𝑚 ways, while another task can be performed in 𝑛 ways, and the two tasks cannot be
performed simultaneously, then performing either task can be accomplished in 𝑚 + 𝑛 ways.
Set theoretical version of the rule of sum: If 𝐴 and 𝐵 are disjoint sets (𝐴 ∩ 𝐵 = ∅), then
|𝑨⋃𝑩| = |𝑨| + |𝑩|.
Department of Mathematics
Brainware University, Kolkata 2
Course Name (Course Code): Discrete Mathematics (PCC-CSM405/ PCC-CSD405/ PCC-CSG405)
Academic Session: 2024-25
Study Material
(Discrete Mathematics (PCC-CSM405)
_____________________________________________________________________________________________
Table of Contents
Module II:
Counting techniques
Sl no. Topic Page no.
1. Introduction 2
2. Basic Counting Principles: 2
3. The Inclusion-Exclusion Principle. 3
4. Permutations and Combinations 4
5. Recurrence relation 11
6. Practice Questions 18
7. References 21
Department of Mathematics
Brainware University, Kolkata 1
, Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathematics (PCC-CSM405/ PCC-CSD405/ PCC-CSG405)
Academic Session: 2024-25
Module 2 Counting techniques
C ounting techniques, also known as combinatorics, is a branch of mathematics concerned with counting and
organizing the number of possibilities or arrangements of objects. Combinatorics is fundamental to various
areas of mathematics, computer science, and other disciplines.
Combinatorics can be traced back more than 3000 years to India and China. For many centuries, it primarily
comprised the solving of problems relating to the permutations and combinations of objects. The use of the word
“combinatorial” can be traced back to Leibniz in his dissertation on the art of combinatorial in 1666. Over the
centuries, combinatorics evolved in recreational pastimes. In the modern era, the subject has developed both in
depth and variety and has cemented its position as an integral part of modern mathematics. Undoubtedly part of
the reason for this importance has arisen from the growth of computer science and the increasing use of
algorithmic methods for solving real-world practical problems. These have led to combinatorial applications in a
wide range of subject areas, both within and outside mathematics, including network analysis, coding theory,
and probability.
Suppose that a password on a computer system consists of six, seven, or eight characters. Each of these
characters must be a digit or a letter of the alphabet. Each password must contain at least one digit. How many
such passwords are there? The techniques needed to answer this question and a wide variety of other counting
problems will be introduced in this section.
Counting problems arise throughout mathematics and computer science. For example, we must count the
successful outcomes of experiments and all the possible outcomes of these experiments to determine
probabilities of discrete events. We need to count the number of operations used by an algorithm to study its
time complexity. We will introduce the basic techniques of counting in this section. These methods serve as the
foundation for almost all counting techniques.
Basic Counting Principles:
We will present two basic counting principles, the product rule and the sum rule. Then we will show how they
can be used to solve many different counting problems. The product rule applies when a procedure is made up of
separate tasks.
The Rule of Product:
If a task can be performed in m ways and another independent task can be performed in n ways, then the
combination of both tasks can be performed in mn ways.
Set theoretical version of the rule of product:
Let A × B be the Cartesian product of sets A and B. Then:
|A × B| = |A| · |B| . More generally: |A_1 × A_2 × · · · × A_n| = |A_1 | · |A_2 | · · · |A_n | .
For instance, assume that a license plate contains two letters followed by three digits. How many different
license plates can be printed?
Answer: Each letter can be printed in 26 ways, and each digit can be printed in 10 ways, so 26 · 26 · 10 · 10 · 10
= 676000 different plates can be printed.
Exercise: Given a set A with m elements and a set B with n elements, find the number of functions from A to B.
The Rule of Sum:
If a task can be performed in 𝑚 ways, while another task can be performed in 𝑛 ways, and the two tasks cannot be
performed simultaneously, then performing either task can be accomplished in 𝑚 + 𝑛 ways.
Set theoretical version of the rule of sum: If 𝐴 and 𝐵 are disjoint sets (𝐴 ∩ 𝐵 = ∅), then
|𝑨⋃𝑩| = |𝑨| + |𝑩|.
Department of Mathematics
Brainware University, Kolkata 2
