Prof. P. R.

Navghare
M. Tech in Information Technology from National Institute of Technology, Raipur
B. E. in Computer Engineering from RTMNU, Nagpur

Core Competencies Research Domains

✓ Theory of Computation
✓ Data Structure & Algorithm ✓ Wireless Sensor Network
✓ Computer Networking ✓ Machine Learning
✓ Machine Learning
✓ Data Science
Department of Computer Engineering

Discrete Mathematics
Course Code: 1303103

Thermal Engineering [22337]

Prof. P. R. Navghare
 Module-I Discrete Mathematics

Module -I

Module I : Set Theory and Counting (8 Hrs)

❑ Set Theory: Introduction to Sets– Set Operations

❑ Cardinality of set,
❑ Principle of inclusion and exclusion,
❑ Types of Sets, Power set,
❑ Methods of Proof-Proof by Contradiction,
❑ Proof by Mathematical Induction.
❑ Propositional Logic- logic,
❑ Propositional Equivalences,
❑ Application of Propositional Logic- Translating English Sentences.
❑ Counting: The Basics of Counting,
❑ rule of Sum and Product,
❑ Permutations and Combinations.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 3

 Discrete Mathematics

Introduction and significance of discrete mathematics

Mathematics can be broadly classified into two categories −

➢Continuous Mathematics
➢ It is based upon continuous number line or the real numbers.
➢Real numbers include irrational as well as rational numbers which are not
discrete.

➢CM Examples:
➢Real numbers
➢Calculus
➢Euclidean geometry

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 4

 Module-I Discrete Mathematics

Discrete mathematics
➢It deals with discrete objects.
➢Discrete objects are those which are separated from (not connected
to/distinct from) each other.
➢Integers, natural numbers, automobiles, houses, people etc. are all discrete
objects.
DM Examples:
▪ Integers
▪ Graphs
▪ Trees
▪ Sets
▪ Statements in logic

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 5

 Module-I Discrete Mathematics

Why study Discrete mathematics?

❑Discrete mathematics is a vital prerequisite to learning algorithms, as it covers
probabilities, trees, graphs, logic, mathematical thinking, and much more.
❑It simply explains them, so once you get those basic topics, it is easier to dig into
algorithms.
❑It also covers topics like:
❑The graph theory (used in networks, operating systems, and compilers)
❑The set theory (used in software engineering and databases)
❑The probability theory (used in artificial intelligence, machine learning, and networking)
AND MUCH MORE……

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 6

 Discrete Mathematics

Set Theory

❑A set is a collection of unordered, distinct and well-defined objects.

❑A set acts as container which holds its members or elements of similar properties.
❑Eg: S={a,b,c}
Y={Smith,Jones,Wong,Joseph}
❑A set may contain finite or infinite number of elements.
❑If set contains no element then it is null or empty set denoted by Ø or {}.
❑Set is denoted by capital letters that is A, B, C.
❑The elements of set are denoted by lower case letters like x, y, a, b, c etc.
❑If an element 'x' is member of set A, then it is represented as x∈A. If an element 'x' is not
member of set A, then it is represented as x ∉ A.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 7

 Module-I Discrete Mathematics

A set is a collection of objects.

(The objects are also called elements or members of the set.)

Examples:
1) A={car, book, 4, 10.523,black, water}
2) The set V of vowels in the English alphabet:
V = {a, e, i, o, u}.
3) Let P be the set of positive integers less than 100:
P = {1, 2, 3,…, 99}.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 8

 Module-I Discrete Mathematics

Examples :

❑ Set of letters forming the words "computer" denoted as

A = {c, o, m, p, u, t, e, r}
Here, "A' is name of set and all the elements of set A are included in a pair
of curly brackets.
❑ The set of subjects of second year Computer Engineering.
S = {DM, FDS, OOP, CG, DELD}
❑ The set of students of second year.
❑ The set of positive integers less than 10.
z= {1,2,3,... 9}
❑ The set of natural numbers greater than 5. This will be an infinite set but
the elements in the set can be listed as A={6,7,8,9,….}

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 9

 Module-I Discrete Mathematics

Set Representation
1. Roster method 2. Set Builder Method
▪ In this method, all the elements of set are ▪ When the elements of set are huge it
described between pair of braces. is not possible to write all the
▪ It is generally used when elements or members or object using roster
members of set are limited. method
▪ The order of elements in a set is not ▪ So the set builder method is used.
important. ▪ Elements of set can be grouped
▪ Example : together by stating their common
▪ A = {6,8, 3, 4, 5} properties.
▪ Write the set of all vowels in the English ▪ Example:
alphabet. ▪ A= {x lx is natural number and x < 10}
▪ O = {x | x is an odd positive integer
less than 10} OR
▪ O = {x ∈ Z+ | x is odd and x < 10}.
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 10
 Module-I Discrete Mathematics

Some Special sets:

Z— the integers (positive, negative, and zero)

N — the natural numbers (positive integers and zero)
Q— the rational numbers (all numbers that can be expressed as an
integer divided by another integer)
R— the real numbers (all numbers that aren’t imaginary, even
decimal numbers that aren’t rational)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 11

 Module-I Discrete Mathematics

Categories of Real Numbers:

All numbers except complex numbers are real numbers. These are divided into several key categories
as shown in the table below.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 12

 Module-I Discrete Mathematics

Cardinality of Sets

❑Let, A be a finite set, then number of elements in the set A, is called the
cardinality of A.
❑It is denoted as | A | or n(A).

Example:
A = { 3, 4, 8, 6 }, then cardinality of A is n(A) or |Al = 4

Properties of Cardinality of Sets

➢ (a) If A = Ø then n(A) = 0
➢ (b) If A⊂ B then n(A) < n(B)
➢ (c) Suppose A and B are finite disjoint sets. Then A U B is finite
and|AUB|=|A|+|B|

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 13

 Module-I Discrete Mathematics

Cartesian Product

❑Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all ordered
pairs (a, b), where a ∈ A and b ∈ B.
Example:
1)What is the Cartesian product of A = {1, 2} and B = {a, b, c}?
Solution: The Cartesian product A × B is
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
2)AxB≠ BxA (why?)
❑The Cartesian product of the sets A1,A2, . . . , An, denoted by
A1 × A2 ×· · ·×An = {(a1, a2, . . . , an) | ai ∈ Ai for i = 1, 2, . . . , n}.
3)Find A× B × C, where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2} ?
❑Solution: A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2),
(1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}.
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 14
 Module-I Discrete Mathematics

Types of sets

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 15

 Module-I Discrete Mathematics

Singleton Set
❑ Singleton Sets are those sets that have only 1 element present in them.
Example:
❑ Set A= {1} is a singleton set as it has only one element, that is, 1.
❑ Set P = {a : a is an even prime number} is a singleton set as it has only one element 2.
Properties of Singleton Set:
❑ A singleton set has exactly one element, for example: {7}
❑ Its cardinality (size) is 1.
❑ A singleton set is always a finite set.
❑ It is a subset of any set that contains its element, for example: {7} ⊆ {5, 6, 7}
❑ The power set of a singleton set has 2 elements:
Example:
❑ Power set of {a} = {∅, {a}}
❑ Every element of a singleton set is also a singleton set in the power set.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 16

 Module-I Discrete Mathematics

Empty Set
❑Empty sets are also known as Null sets or Void sets. They are the sets with no
element/elements in them. They are denoted as ϕ also known as phi.
Example:
❑Set A= {a: a is a number greater than 5 and less than 3}
❑Set B= {p: p are the students studying in class 7 and class 8}
Properties of Empty Set (∅):
❑∅ has no elements (0 elements).
❑∅ is a subset of every set.
❑There is only one empty set.
❑∅ is not a singleton set.
❑The intersection of disjoint sets is ∅.
❑The power set of ∅ is {∅} (has 1 element).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 17

 Module-I Discrete Mathematics

Finite Set

❑A finite set is a set that has a countable number of elements.

❑In other words, you can count how many elements it has, and the counting ends.
They will be called a Finite set.
Example:
❑A = {1, 2, 3, 4} → Finite (4 elements)
❑B = {"apple", "banana"} → Finite (2 elements)
❑C = ∅ (Empty set) → Also a finite set (0 elements)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 18

 Module-I Discrete Mathematics

Finite Set

Properties of Finite Set:

❑Has a fixed number of elements.
❑The number of elements is a whole number (0 or more).
❑You can count the elements and finish counting.
❑The empty set is also finite (with 0 elements).
❑All singleton sets are finite.
❑The union, intersection, or difference of two finite sets is also a finite set.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 19

 Module-I Discrete Mathematics

Infinite Set

Infinite Set
Infinite Sets are those that have an infinite number of elements present, cases in
which the number of elements is hard to determine are known as infinite sets.
Example:
A = {1, 2, 3, 4, 5, 6, ...} → Infinite
B = Set of all stars in the sky → Infinite
C = Set of all natural numbers → Infinite

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 20

 Module-I Discrete Mathematics

Infinite Set

Properties of Infinite Set:

❑Has unlimited or endless elements.
❑You cannot count all the elements — counting never ends.
❑Removing or adding a finite number of elements doesn’t make it finite.
❑Infinite sets can be countable (like natural numbers) or uncountable (like real
numbers).
❑The power set of an infinite set is also infinite.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 21

 Module-I Discrete Mathematics

Equal Set

❑Two sets having the same elements and an equal number of elements are called
equal sets. The elements in the set may be rearranged, or they may be repeated,
but they will still be equal sets.
Example:
❑Set A = {1, 2, 6, 5}
❑Set B = {2, 1, 5, 6}
❑In the above example, the elements are 1, 2, 5, 6. Therefore, A= B.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 22

 Module-I Discrete Mathematics

Equal Set

Properties of Equal Sets :

❑Two sets are equal if every element of one set is also in the other set.
❑The order of the elements doesn't matter.
❑The repetition of elements doesn’t matter (sets don’t allow duplicates).
❑If A = B, then A ⊆ B and B ⊆ A.
❑Equal sets have the same number of elements (same cardinality).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 23

 Module-I Discrete Mathematics

Equivalent Set

❑Equivalent Sets are those which have the same number of elements present in
them. It is important to note that the elements may be different in both sets but
the number of elements present is equal. For Instance, if a set has 6 elements in
it, and the other set also has 6 elements present, they are equivalent sets.
Example:
❑Set A= {2, 3, 5, 7, 11}
❑Set B = {p, q, r, s, t}
❑Set A and Set B both have 5 elements hence, both are equivalent sets.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 24

 Module-I Discrete Mathematics

Equivalent Set

Properties of Equivalent Sets :

❑Equivalent sets have the same number of elements.
❑The elements can be different; it only the count matters.
❑If two sets A and B are equivalent, we write: A ≈ B
❑All equal sets are equivalent, but not all equivalent sets are equal.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 25

 Module-I Discrete Mathematics

Subset
❑Set A will be called the Subset of Set B if all the elements present in Set A already belong to Set B.
The symbol used for the subset is ⊆.
❑If A is a Subset of B, it will be written as A ⊆ B
Example:
❑Set A= {33, 66, 99}
❑Set B = {22, 11, 33, 99, 66}
❑Then, Set A ⊆ Set B
Properties of Subsets :
❑A ⊆ A (Every set is a subset of itself)
❑∅ ⊆ A (Empty set is a subset of every set)
❑If A ⊆ B and B ⊆ C, then A ⊆ C (transitive property)
❑If A ⊆ B and A ≠ B, then A is a proper subset of B (written A ⊂ B)
❑A set with n elements has 2ⁿ subsets (including ∅ the set itself)
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 26
 Module-I Discrete Mathematics

Proper Subset
❑A proper subset is a subset that contains some but not all elements of the original set. It is not
equal to the original set. If A and B are sets, and A is a proper subset of B, we write: A ⊂ B
Example:
❑Let B = {1, 2, 3}
❑Proper subsets of B are:
❑∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}
❑{1, 2, 3} is a subset of B, but not a proper subset, because it is equal to B.
Properties of Proper Subset:
❑A proper subset has fewer elements than the original set.
❑Every proper subset is a subset, but not every subset is proper.
❑The empty set (∅) is a proper subset of any non-empty set.
❑The original set is not a proper subset of itself.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 27

 Module-I Discrete Mathematics

Power Set
❑The set of any set A is defined as the set containing all the subsets of set A. It is denoted by the
symbol P(A) and read as the Power set of A.
❑For any set A containing n elements, the total number of subsets formed is 2n. Thus, the power
set of A, P(A) has 2n elements.
It includes:
❑The empty set (∅)
❑All individual elements as sets
❑All combinations of elements
❑The set itself
Example: For any set A = {a,b,c}, the power set of A is?
Solution:
❑Power Set P(A) is,
❑P(A) = {ϕ, {a}, {b}, {c}, {a, b}, {b, c}, {c, a}, {a, b, c}}
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 28
 Module-I Discrete Mathematics

Power Set

Properties of Power Set :

❑If a set has n elements, its power set has 2ⁿ subsets.
Example: A = {a, b, c} → 3 elements → power set has 2³ = 8 subsets
❑The power set always includes:
❑The empty set (∅)
❑The original set
❑Power set of ∅ is: P(∅) = {∅}
❑The power set is always larger than the original set (except when the set is empty).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 29

 Module-I Discrete Mathematics

Universal Set
❑ A universal set is a set that contains all the elements of the rest of the sets. It can be said that all the sets are the subsets
of Universal sets. The universal set is denoted as U.
Example: For Set A = {a, b, c, d} and Set B = {1,2}, find the universal set containing both sets.
Solution:
❑ Universal Set U is,
❑ U = {a, b, c, d, e, 1, 2}
Properties of Universal Set:
❑ Contains all the elements being discussed.
❑ Every set is a subset of the universal set.
❑ The complement of a set is taken disjointed from the universal set.
❑ It is usually finite or defined by context (can be infinite in some cases).
❑ The intersection of U with any set A is A:
❑U ∩ A = A
❑ The union of U with any set A is U:
❑U ∪ A = U
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 30
 Module-I Discrete Mathematics

Disjoint Sets
❑That have two sets A and B that do have no common elements are called Disjoint Sets. The
intersection of the Disjoint set is ϕ, now for set A and set B A∩B = ϕ.
❑Example: Check whether Set A ={a, b, c, d} and Set B = {1, 2} are disjoint or not.
❑Solution:
❑Set A ={a, b, c, d}
❑Set B= {1,2}
❑Here, A∩B = ϕ
❑Thus, Set A and Set B are disjoint sets.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 31

 Module-I Discrete Mathematics

Types of Sets

Set Name Description Example

Empty Set A set containing no elements {}
whatsoever
Singleton Set A set containing exactly one {1}
element.
Finite Set A set with a limited, countable {apple, banana, orange}
number of elements.

Infinite Set A set with an uncountable number {natural numbers (1, 2, 3, ...)}
of elements.
Equivalent Sets Sets that have the same number of Set A = {1, 2, 3} and Set B = {a, b, c}
elements and their elements can (assuming a corresponds to 1, b to
be paired one-to-one 2, and c to 3)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 32

 Module-I Discrete Mathematics

Types of Sets
Set Name Description Example
Equal Sets Sets that have the same elements. Set A = {1, 2} and Set B = {1, 2}

Universal Set A set containing all elements The set of all students in a school
relevant to a specific discussion. (when discussing student grades)

Unequal Sets Sets that do not have all the same Set A = {1, 2, 3} and Set B = {a, b}
elements.
Power Set The set contains all possible subsets Power Set of {a, b} = { {}, {a}, {b}, {a,
of a given set. b} }
Overlapping Sets Sets, share a least one common Set A = {1, 2, 3} and Set B = {2, 4, 5}
element.
Disjoint Sets Sets that have no elements in Set A = {1, 2, 3} and Set B = {a, b, c}
common.
Subset A set where all elements are also {1, 2} is a subset of {1, 2, 3}
members
Pune Institute of Computer Technology, Pune of another set. Prof. P. R. Navghare 33
 Module-I Discrete Mathematics

Operation on Sets

Union
The union of A and B, written A  B, is the set whose elements are the elements of A
or B or both.
A  B = {x | x  A or x  B}.
Examples: Let K = {a, b}, L = {c, d} and M = {b, d}, then
K  L = {a, b, c, d}
A B
K  M = {a, b, d} U

L  M = {b, c, d}

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 34

 Module-I Discrete Mathematics

Intersection

❑ The intersection of A and B, written A ∩ B, is the set whose elements

are just the elements of both A and B. In the predicate notation the
definition is
❑ A ∩ B ={x | x  A and x  B}.
❑ Examples: Let K = {a, b}, L = {c, d} and M = {b, d}, then
K∩L=
K ∩ M = {b} U A B
L ∩ M = {d}.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 35

 Module-I Discrete Mathematics

Difference

❑ The difference of A and B, written A – B, is the set whose elements are

the elements of A which are not in B.
❑ A – B ={x | x  A and x  B}.
❑ Examples: Let K = {a, b}, L = {c, d} and M = {b, d}, then
K – L = {a, b}
K – M = {a}
L – M = {c} U A B

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 36

 Module-I Discrete Mathematics

Symmetric difference

The symmetric difference of sets A and B, denoted by AB, consists of those

elements which belong to ‘A or B’ but not ‘A and B’.
(A  B)=(A  B)-(A ∩ B). We can also write
(A  B)=(A - B)  (B - A).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 37

 Module-I Discrete Mathematics

Disjoint Sets

❑Two sets are said to be disjoint if their intersection is the empty set:
AB=

U
A
B

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 38

 Module-I Discrete Mathematics

Complement

❑The complement of a set A, written Ac, which is the set consisting of everything not in A. Ac
= {x | x  A}.
❑The same can also be written as Ac = U – A, where U is the universal set.

U A A

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 39

 Module-I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 40

 Module-I Discrete Mathematics

Venn Diagram
❑ A Venn diagram is a diagram constructed with a collection of circles drawn on a plane.
❑ Each Venn diagram begins with a rectangle representing the universal set.
❑ Then circles represent the sets.
❑ Any values that belong to more than one set will be placed in the sections where the
circles overlap.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 41

 Module-I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 42

 Module-I Discrete Mathematics

Laws of Sets

1. Commutative Laws: 3. Idempotent Laws: 5. De Morgan’s Laws:

For any two finite sets A and B; For any finite set A; For any two finite sets A and B;

(i) A U B = B U A (i) A U A = A (i) A – (B U C) = (A – B) ∩ (A – C)

(ii) A ∩ B = B ∩ A (ii) A ∩ A = A (ii) A - (B ∩ C) = (A – B) U (A – C)

2. Associative Laws: 4. Distributive Laws: De Morgan’s Laws can also we written

as:
For any three finite sets A, B and For any three finite sets A, B and
C; C; (i) (A U B)’ = A' ∩ B'

(i) (A U B) U C = A U (B U C) (i) A U (B ∩ C) = (A U B) ∩ (A U C) (ii) (A ∩ B)’ = A' U B'

(ii) (A ∩ B) ∩ C = A ∩ (B ∩ C) (ii) A ∩ (B U C) = (A ∩ B) U (A ∩ C)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 43

 Module-I Discrete Mathematics

6. For any two finite sets A and B

7. For any three finite sets A, B and C
(i) A – B = A ∩ B'
(i) A – (B ∩ C) = (A – B) U (A – C)
(ii) B – A = B ∩ A'
(ii) A – (B U C) = (A – B) ∩ (A – C)
(iii) A – B = A ⇔ A ∩ B = ∅
(iii) A ∩ (B - C) = (A ∩ B) - (A ∩ C)
(iv) (A – B) U B = A U B
(iv) A ∩ (B △ C) = (A ∩ B) △ (A ∩ C)
(v) (A – B) ∩ B = ∅

(vi) A ⊆ B ⇔ B' ⊆ A'

(vii) (A – B) U (B – A) = (A U B) – (A ∩ B)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 44

 Module-I Discrete Mathematics

Mutually Exclusive and Exhaustive Sets

❑We say that a group of sets is exhaustive of another set if their union is equal
to that set. For example, if A  B = C we say that A and B are exhaustive with
respect to C.
❑We say that two sets A and B are mutually exclusive if, A∩B =  that is,
the sets have no elements in common.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 45

 Module-I Discrete Mathematics

The Principle of Inclusion and Exclusion

❑The Principle of Inclusion and Exclusion allows us to find the cardinality of a union of sets
by knowing the cardinalities of the individual sets and all possible intersections of them.
❑The basic version of the Principle of Inclusion and Exclusion is that for two finite sets A and
B, it holds that |A  B|=|A|+|B|–|A ∩ B|.

If there are three finite sets:

|ABC|=|A|+|B|+|C|–|A∩B|–|A∩C|–|B∩C|+|A∩B∩C|.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 46

 Module-I Discrete Mathematics

Multiset

Multiset(orbag)is a generalization of the notion of a set in which members are

allowed to appear more than once.
Example:
S={1,2,2,3,4,1,2,3}
It can also be represented as S={1.2, 2.3, 3.2,4}.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 47

 Module-I Discrete Mathematics

Problems on Set

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 48

 Module-I Discrete Mathematics

Problems on Set

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 49

 Module-I Discrete Mathematics

Problems on Set

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 50

 Module-I Discrete Mathematics

Problems on Set

15. Show that AU (B’ ∩ C)= (AUB’) ∩ (AU C) Using vien diagram

16. Show that (A-B)-C=A-(BUC) Using vien diagram

17. In a survey 2000 people read india today or buiseness times, It was found that 1200 read India today,
900 read buiseness times and 400 read both, find how many read atleast one magazine and how many
read none.

18. In a Computer lab out of 6 computers 2 have floating point arithmetic unit 5 have magnetic disc
memory 3 have graphics display 2 have both floating point and magnetic 3 have both magnetic and
geaphics 1 has both floating point and graphics 1 has floating , magnetic and graphics How many have
atleast one specification.

[Link] the integers 1 to 1000 how many of them are not divisible by 3, nor by 5 nor by 7.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 51

 Module-I Discrete Mathematics

Problems on Set

20. An investigator interviewed 100 students to determine their preferences for 3 drinks milk
,coffee and Tea He reported the following 10 students had all the 3 drinks 20 had milk & C 30
C & T, 25 had M & T , 12 M Only , 5 C only & 8 had T only. How many did not take any of three
drinks.

[Link] 100, 32 maths 20 Physics , 45 Biology 15 M & B, 7 M & P, 10 P &B, 30 do not study
any 3 subjects. Find number of students exactly one of 3 subject.

22. Among 1000 people , 595 are democrate , 595 were glasses and 550 like icecream 395 D &
G , 350 D & I, 400 G & I , 250 D & G & I How many them are not D , NOT U NOT I How many
are D but not G & I.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 52

 Module-I Discrete Mathematics

Problems on Set

1. Explain following terms with example.

i)Symmetric difference between set [4]
ii)Union of set
iii)Intersection of Set
iv) Subset of a Set

2. A college Records gives following information : 119 students enrolled in Introductory computer science, 96
of them took data structures, 53 took foundations, 39 took assembly language, 31 took both foundation and [5]
Assembly language, 32 took both data structures and Assembly language, 38 took data structures and
foundations and 22 took all of three courses is this information correct? Why?

3. Let U = {1, 2, 3,…., 10}, A = {2, 4, 6, 8, 10}, B = {1, 3, 5, 7, 9, 10} [6]

Find:
i)(A ∪ B)'
ii)(A ∩ B)'
iii)(B)'
iv)(B–A)'

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 53

 Module-I Discrete Mathematics

Problems on Set

4) Let A ={1, 2, 3} and B = {1, 2, 3, 4, 5}. Find [5]

i) P(A U B)
ii) P(A ∩ B)
iii) A–B

5) Suppose 100 Computer Engineering students studies at least one of the following language C, C++ and
Python. It is given that 65 students studies C language, 45 studies C++ language and 42 studies Python [5]
language. 20 students studies C and C++ language, 25 student studies C and Python language, 15 students
studies C++ and Python language. Find students studying : [5]
i) Only C and C++ language, not Python language
ii) Only C and Python language, not C++ language

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 54

 Module-I Discrete Mathematics

Problems on Set
6) In the survey of 60 people, it was found that 25 read Newsweek magazine, 26 read time, 26 read
Fortune. Also 9 read both Newsweek and Fortune, 11 read both Newsweek and Time, 8 read both Time
and Fortune and 8 read no magazine at all. [5]
a)Find out the total number of people who read all the three magazines
b)Fill in the correct number in all the regions of the Venn diagram
c)Determine the number of people who read exactly one magazine

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 55

 Module-I Discrete Mathematics

Propositions

❑A proposition is a declarative sentence that is either true or false.

Examples of propositions:
1. The Moon is made of green cheese.
2. New Delhi is the capital of India.
3. Toronto is the capital of Canada.
4. 1+0=1
5. 0+0=2
Examples that are not propositions.
1. Sit down!
2. What time is it?
3. x+1=2
4. x + y = z
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 56
 Module-I Discrete Mathematics

Propositional Logic

Constructing Propositions
❑Propositional Variables: p, q, r, s, . . .
❑The proposition that is true is denoted by T
❑Proposition that is false is denoted by F
❑Compound Propositions; constructed from logical connectives and
other propositions
❑Negation ¬
❑Conjunction ∧
❑Disjunction ∨
❑Implication →
❑Biconditional

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 57

 Module-I Discrete Mathematics

Conjunction

❑The Conjunction of propositions p and q is denoted by p ∧ q and has

truth table:

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 58

 Module-I Discrete Mathematics

Disjunction

❑ The disjunction of propositions p and q is denoted by p ∨ q and

has truth table:

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 59

 Module-I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 60

 Module-I Discrete Mathematics

Converse, Contrapositive, and Inverse

❑ q → p is the converse of p → q
❑ ¬q → ¬p is the contrapositive of p → q
❑ ¬p → ¬q is the inverse of p → q

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 61

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 62

 UNIT I Discrete Mathematics

Translating logical formula to English sentence

❑Alice is either smart or honest, but Alice is not honest if she is

smart:
(p ∨ q) ∧ (p → ¬ q).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 63

 UNIT I Discrete Mathematics

❑ A proposition is satisfiable, if its truth table contains true at least

once. Example: p ∧ q.
❑ Tautology, if it is always true. Example: p ∨ ¬p.
❑ Contradiction, if it always false. Example: p ∧ ¬p.
❑ Contingency, if it is neither a tautology nor a contradiction.
Example: p.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 64

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 65

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 66

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 67

 UNIT I Discrete Mathematics

Examples
1)Let p be “Mark is Rich” and q be “Mark is happy” write each of following in symbolic form [4]
a)Mark is poor but happy
b)Mark is neither rich nor happy
c)Mark is either rich or happy
d)Mark is Rich and not happy

2) Explain terms Tautology and Contradiction in truth table with an example. [5]

3) Let P : I will study hard and Q: I will get admission in IIT. Statement: If I study
hard then I will get admission in IIT.
Write the Converse, Inverse & Contrapositive of the above statement. [5]

4)What is Logical Equivalence? Show that

[5]

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 68

 UNIT I Discrete Mathematics

Examples:

5) Express the contrapositive, converse and inverse form of conditional statement given
below:
“If x is rational, then x is real”

6)Let p be “Mark is Rich” and q be “Mark is happy” write each of following in symbolic form
[5]
i)Mark is poor but happy
ii)Mark is neither rich nor happy
iii)Mark is either rich or happy
iv)Mark is Rich and not happy

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 69

 UNIT I Discrete Mathematics

Principal Normal Forms:

1. PDNF
2. PCNF

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 70

 UNIT I Discrete Mathematics

Mathematical Reasoning

❑ The general form of a rule of inference is:

❑Where p1, p2,.., pn are known as the hypotheses and q is known

as the conclusion and ‘∴’ means ‘therefore’. The rule states that if
p1and p2 and … and pn are all true, then q is true as well.

Some valid arguments:

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 71

 UNIT I Discrete Mathematics

Proving Theorems

❑ Direct proof:
❑ An implication p q can be proved by showing that if p is true, then q is also
true.
❑ Example: Prove that “If n is odd, then n2 is odd.”

Assume that n is odd.

Then it can be written as n = 2k + 1, where k is an integer.
Consequently, n2 = (2k + 1)2.
= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1
Since n2 can be written in this form, it is odd
Q1) Prove that “If n is even, then n2 is even.”
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 72
 UNIT I Discrete Mathematics

Indirect proof:
❑ An implication p → q is equivalent to its contra-positive
 q →  p. Therefore, we can prove p → q by showing that whenever q is false,
then p is also false.
Q2) Give an indirect proof of the theorem
“If 3n + 2 is odd, then n is odd”.
❑ Assume that n is even.
❑ Then n = 2k, where k is an integer.
❑ It follows that 3n + 2 = 3(2k) + 2
= 6k + 2
= 2(3k + 1)
❑ Therefore, 3n + 2 is even.
❑ We have shown that the contrapositive of the implication is
true, so the implication itself is also true (If 3n + 2 is odd, then n
is odd).
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 73
 UNIT I Discrete Mathematics

Mathematical Induction
Principle of Mathematical Induction Statement

Any statement P(n) which is for "n" natural number can be proved using the
Principle of Mathematical Induction by following the below steps,

Step 1: Verify if the statement is true for trivial cases (n = 1) i.e. check if P(1)
is true.

Step 2: Assume that the statement is true for n = k for some k ≥ 1 i.e. P(k) is
true.

Step 3: If the truth of P(k) implies the truth of P(k + 1), then the statement
P(n) is true for all n ≥ 1.
Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 74
 UNIT I Discrete Mathematics

Mathematical Induction Steps

Base Step: Prove P(k) is true for k =1

Assumption Step: Let P(k) is true for all k in N and k > 1

Induction Step: Prove P(k+1) is true using basic

mathematical properties.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 75

 UNIT I Discrete Mathematics

Example 1): For any positive integer number n, prove that n3 + 2n is

always divisible by 3
Example 2): For all n ≥ 1, prove that, 12 + 22 + 32+....+n2 = {n(n + 1)
(2n + 1)} / 6

Example 2: For all n ≥ 1, prove that, 1.2.3 + 2.3.4 + 3.4.5+...+n(n + 1) (n +

2) = {n (n + 1) (n + 2) ( n + 3)} / 4
Example 3: For all n ≥ 1, prove that, 1 + 3 + 5 +... + 2n - 1 = n2
Example 4: For all n ≥ 1, prove that, 1.2 + 2.3 + 3.4 +...+ n(n + 1) = {n(n +
1)(n + 2)} / 3
Example 5: Prove an = a1 + (n - 1) d, is the general term of any arithmetic
sequence.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 76

 UNIT I Discrete Mathematics

Problem 1: Prove that for all natural numbers n, the following holds: 1 + 2
+ 3 + . . . + n = [n(n + 1)]/2.

Problem 2: Show that for all integers n ≥ 1 : 13 + 23 + 33 + . . . + n3 = [{n(n

+ 1)}/2]2.

Problem 3: Verify that for all natural numbers n: 2n > n2.

Problem 4: Prove that for all integers n ≥ 1: 1×2 + 2×3 + 3×4 + ⋯ +

n(n+1) = [n(n+1)(n+2)]/3.

Problem 5: Show that for all integers n ≥ 1: 7n − 4n is divisible by 3.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 77

 UNIT I Discrete Mathematics

1) Use mathematical induction to prove [5]

Sn = 2 + 4 + 6 + 8 + ... + 2n = n(n + 1) for all positive integer n.

2) By using mathematical induction prove that

S = 1 + 3 + ... + (2n–1) = n2; for all integers n > 1

3)By using mathematical induction show that 1+2+3+.....+n =

n(n+1)/2 for all natural number values of n.

4)By using mathematical induction show that 1+4+7+...+(3n-

2)=n(3n-1)/2 for all natural number values of n.

5) Using mathematical induction, prove that

1 + 2 + … + n = n (n + 1)/2

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 78

 UNIT I Discrete Mathematics

Basic Counting Principles

Counting problems are of the following kind:

❑“How many different 8-letter passwords are there?”

❑“How many possible ways are there to pick 11 soccer players out
of a 20-player team?”

❑Most importantly, counting is the basis for computing

probabilities of discrete events.

❑(“What is the probability of winning the lottery?”)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 79

 UNIT I Discrete Mathematics

Rule of Sum and Product

❑ Rule of Product – For two experiments with possible outcomes

m, n. There are mxn possible outcomes when both of these
experiments take place.

❑ Rule of Sum – There are m+n possible outcomes when exactly

one of these experiments takes place.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 80

 UNIT I Discrete Mathematics

Basic Counting Principles

The sum rule:

❑ If a task can be done in n1 ways and a second task in n2 ways,
and if these two tasks cannot be done at the same time, then
there are n1 + n2 ways to do either task.
Example:
❑ The department will award a free computer to either a CS
student or a CS professor.
❑ How many different choices are there, if there are 530 students
and 15 professors?
✓ There are 530 + 15 = 545 choices.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 81

 UNIT I Discrete Mathematics

Basic Counting Principles

Generalized sum rule:

If we have tasks T1, T2, …, Tm that can be done in n1, n2, …, nm

ways, respectively, and no two of these tasks can be done at the
same time, then there are n1 + n2 + … + nm ways to do one of
these tasks.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 82

 UNIT I Discrete Mathematics

Basic Counting Principles

The product rule:

Suppose that a procedure can be broken down into two successive tasks. If there are
n1 ways to do the first task and n2 ways to do the second task after the first task has
been done, then there are n1n2 ways to do the procedure.

Example:
The department will award a free computer to a CS student and a CS professor.
How many different choices are there, if there are 530 students and 15 professors?

There are 530 *15 = 7950 choices.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 83

 UNIT I Discrete Mathematics

Basic Counting Principles

Example:
How many different license plates are there that containing exactly three English
letters ?
Solution:
There are 26 possibilities to pick the first letter, then 26 possibilities for the second
one, and 26 for the last one.

So there are 26.26.26 = 17576 different license plates

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 84

 UNIT I Discrete Mathematics

Basic Counting Principles

Generalized product rule:

If we have a procedure consisting of sequential tasks T1, T2, …, Tm that can be done in
n1, n2, …, nm ways, respectively, then there are n1 . n2 . … . nm ways to carry out the
procedure.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 85

 UNIT I Discrete Mathematics

Basic Counting Principles

The sum and product rules can also be phrased in terms of set theory.

Sum rule: Let A1, A2, …, Am be disjoint sets. Then the number of ways to choose any
element from one of these sets is |A1 UA2 U… UAm | =
|A1| + |A2| + … + |Am|.

Product rule: Let A1, A2, …, Am be finite sets. Then the number of ways to choose one
element from each set in the order A1, A2, …, Am is
|A1  A2   Am | = |A1|  |A2|  …  |Am|.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 86

 UNIT I Discrete Mathematics

More examples

Q.1 - With 31 flavors of ice cream, 4 sizes of serving, and a choice of “cone” or “dish,”
how many different orders of ice cream are there?
Q.2 - At a restaurant, there are 18 dinners with meat, 10 different dinners with fish, and
5 vegetarian dinners? How many dinners to choose from?
Q.3 - In New Delhi, license plates consisted of two letters followed by 3 digits. How
many possible license plates are?
Q.4 - A traveling salesman wants to do a tour of all 50 state capitals. How many ways
can he do this?
Q.5 – How many different salads can be made from M, A, P, O, B. Only one fruit can also
be used. (Simpler method: Use the product rule)
Q.6 – How many 4 digit even numbers have all 4 digits distinct.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 87

 UNIT I Discrete Mathematics

Answers

Q.1 - 31x4x2=248
Q.2 - 18+10+5=33 choices
Q.3 - 262 × 103
Q.4 - 50 choices for the first place to visit, 49 for the second, . . . 50! Altogether
Q.5 - 2*2*2*2*2 - 1 = 31
Q.6 – 1st case -> ends with 0 -> 9*8*7*1 = 504
(9 choices for the first digit, 8 for the second, 7
for the third and 1 choice for 0)
2nd case -> ends with 2,4,6,8 -> 8×8×7=448
(8 choices for the first digit (no 0 nor the last digit), 8 for the second digit and
7for the third digit)
Since there are 4 possible choices for the last digit (2, 4, 6, 8)
448*4 = 1792
Total = 504+1792=2296

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 88

 UNIT I Discrete Mathematics

The Pigeonhole Principle

❑The pigeonhole principle: If (k + 1) or more objects are placed into k boxes, then
there is at least one box containing two or more of the objects.

❑Example 1: If there are 11 players in a soccer team that wins 12-0, there must be at
least one player in the team who scored at least twice.

❑Example 2: If you have 6 classes from Monday to Friday, there must be at least one
day on which you have at least two classes.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 89

 UNIT I Discrete Mathematics

❑The generalized pigeonhole principle: If N objects are placed into k boxes, then
there is at least one box containing at least N/k of the objects.

❑Example 1: In our 60-student class, at least 12 students will get the same letter
grade (A, B, C, D, or F).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 90

 UNIT I Discrete Mathematics

Permutations and Combinations

❑How many ways are there to pick a set of 3 people from a group of 6?

❑There are 6 choices for the first person, 5 for the second one, and 4 for the third one,
so there are
6*5*4 = 120 ways to do this.

❑This is not the correct result!

❑For example, picking person C, then person A, and then person E leads to the same
group as first picking E, then C, and then A.

❑However, these cases are counted separately in the above equation.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 91

 UNIT I Discrete Mathematics

Permutations and Combinations

❑So how can we compute how many different subsets of people can be picked (that is,
we want to disregard the order of picking) ?

❑To find out about this, we need to look at permutations.

❑A permutation of a set of distinct objects is an ordered arrangement of these objects.

❑An ordered arrangement of r elements of a set is called an r-permutation.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 92

 UNIT I Discrete Mathematics

Permutations and Combinations

❑Example: Let S = {1, 2, 3}.
❑The arrangement 3, 1, 2 is a permutation of S.
❑The arrangement 3, 2 is a 2-permutation of S.

❑The number of r-permutations of a set with n distinct elements is denoted by P(n, r).

❑We can calculate P(n, r) with the product rule:

❑P(n, r) = n.(n – 1).(n – 2) .…(n – r + 1).

❑(n choices for the first element, (n – 1) for the second one, (n – 2) for the third one…)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 93

 UNIT I Discrete Mathematics

Permutations and Combinations

Example:

❑P(8, 3) = 8.7.6 = 336

= ([Link].[Link])/([Link].1)

General formula:
❑P(n, r) = n!/(n – r)!

❑Knowing this, we can return to our initial question:

❑How many ways are there to pick a set of 3 people from a group of 6 (disregarding the
order of picking)?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 94

 UNIT I Discrete Mathematics

Permutations and Combinations

❑An r-combination of elements of a set is an unordered selection of r elements from

the set.
❑Thus, an r-combination is simply a subset of the set with r elements.

❑Example: Let S = {1, 2, 3, 4}.

❑Then {1, 3, 4} is a 3-combination from S.

❑The number of r-combinations of a set with n distinct elements is denoted by C(n, r).

❑Example: C(4, 2) = 6, since, for example, the 2-combinations of a set {1, 2, 3, 4} are {1,
2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 95

 UNIT I Discrete Mathematics

Permutations and Combinations

❑How can we calculate C(n, r)?

❑Consider that we can obtain the r-permutation of a set in the following way:

❑First, we form all the r-combinations of the set

(there are C(n, r) such r-combinations).

❑Then, we generate all possible orderings in each of these r-combinations (there are
P(r, r) such orderings in each case).

❑Therefore, we have:

❑P(n, r) = C(n, r).P(r, r)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 96
 UNIT I Discrete Mathematics

Permutations and Combinations

❑ C(n, r) = P( = n!/(n – r)!/(r!/(r – r)!)

= n!/(r!(n – r)!)

❑ Now we can answer our initial question:

❑ How many ways are there to pick a set of 3 people from a group of 6
(disregarding the order of picking)?

❑ C(6, 3) = 6!/(3!3!) = 720/(66) = 720/36 = 20

❑ There are 20 different ways, that is, 20 different groups to be picked.

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 97

 UNIT I Discrete Mathematics

Permutations and Combinations

Example:
A soccer club has 8 female and 7 male members. For today’s match, the coach wants to
have 6 female and 5 male players on the grass. How many possible configurations are
there?

C(8, 6)  C(7, 5) = 8!/(6!2!)  7!/(5!2!)

= 2821
= 588

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 98

 UNIT I Discrete Mathematics

Permutations and Combinations

❑ An arrangement of elements in sequence is called permutation .
❑ No. of possible arrangements of n elements are n!.
❑ In permutation order of elements matters.

❑ No. of possible arrangements of n elements taking r at a time is given by ,

P (n , r) = n ! / ( n – r )!
where , 0<=r<=n
Where n=no of distinct elements.
r= no of elements taken at a time.

❑ Types of permutation
1. Simple permutation
2. Circular Permutation
3. Permutation with repetition(r1 are of one kind,r2 are of other kind….)
4. Permutation with repetition( when each element can be repeated up to r times)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 99

 UNIT I Discrete Mathematics

Type1: Simple Permutation

Ex1. 4 persons enter bus in which there are 6 vacant seats. In how many ways they
can take places ?
Ans : P(6,4) = 6 * 5*4*3 = 360 ways
Ex2. If repetition is not allowed then.
How many 3 digits numbers can be formed from six digits 2,3,4,5,7,9 ?
How many of these no. are less than 400?
How many are even ?
How many are multiple of 5 ?
Ans : 1) 6*5*4=120 ways
2) 2*5*4=40 ways
3) 4*5*2=40 ways
4) 4*5*1=20 ways

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 100

 UNIT I Discrete Mathematics

Type1: Simple Permutation

Ex 3. Six different mathematics books ,four different electronics books and three
different computer books are to be arranged on a shelf .How many different
arrangement is possible if
1. The books in each subject must all be together ?
[Link] the electronics books must be together ?
Ans: 1) 3!(All Together) ×6!(M)×4!(E)×3!©
2) 10!(1(E Together) +6(M)+3(C))×4!(E)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 101

 UNIT I Discrete Mathematics

Type 2: Circular Permutation

❑In general n object can be arranged in (n-1)! Ways.

❑Ex1: In how many ways can 9 people be seated at a round

table if They can sit anywhere ?
❑2 particular person must not be seated next to each other.

❑Ans: 1) (n-1)! i.e. (9-1)! = 8!

❑ 2) if 2 particular person must be seated next to each
other then 2*7!
❑Therefor 2 particular person must not be seated next to each
other= 8!-(2*7!)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 102

 UNIT I Discrete Mathematics

Type3: Permutation with repetition

❑ The no. of ways in which n elements can be arranged ,where r1 elements are of
one kind,r2 are of other kind and so on…..
❑ Then the no. of arrangements = )n! / r1!r2!r3!

❑ Ex1: In how many ways can the letter MISSISSIPPI can be arranged ?
❑ 11!/1!⋅4!⋅4!⋅2!

❑ Ex2: How many no. can be formed with the digit 1,2,3,4,3,2,1 , so that the odd
digit always occupy the odd places.
❑ 4!/2!⋅2! * 3!/2!.1!

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 103

 UNIT I Discrete Mathematics

Type4: Permutation with repetition

❑ The no. of permutations of n elements ,r at a time when each element may be

repeated ,once, twice,….. Up to r times.
❑ Then the no. of possible arrangements is n^r

❑ [Link] how many ways an auto license plate can be made if each is identified by
2 letters followed by 4 digits ?
❑ 26×26×10×10×10×10

❑ Ex2: In how many ways an auto license plate can be made if each is identified by
2 letters followed by 4 digits & first digit should not be 0 ?
❑ 26×26×10×10×10

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 104

 UNIT I Discrete Mathematics

Combinations

❑ We also saw the following:

❑This symmetry is intuitively plausible.

❑For example, let us consider a set containing six elements (n = 6).
❑Picking two elements and leaving four is essentially the same as picking four
elements and leaving two.
❑In either case, our number of choices is the number of possibilities to divide
the set into one set containing two elements and another set containing four
elements

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 105

 UNIT I Discrete Mathematics

Combinations

Pascal’s Identity:
❑ Let n and k be positive integers with n k.
Then C(n + 1, k) = C(n, k – 1) + C(n, k).
❑ How can this be explained?
❑ What is it good for?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 106

 UNIT I Discrete Mathematics

Combinations

Imagine a set S containing n elements and a set T containing (n + 1) elements, namely

all elements in S plus a new element a.
Calculating C(n + 1, k) is equivalent to answering the question: How many subsets of T
containing k items are there?
Case I: The subset contains (k – 1) elements of S
plus the element a: C(n, k – 1) choices.
Case II: The subset contains k elements of S and
does not contain a: C(n, k) choices.
Sum Rule: C(n + 1, k) = C(n, k – 1) + C(n, k).

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 107

 UNIT I Discrete Mathematics

Combinations

❑ In combination order does not matter.

❑ So combination of n elements taken r at a time is given by C(n,r) = n! /r!(n-r)!

❑ Ex1: A farmer buys 3 cows,2 pigs, and 4 hens from a man who has 6 cows , 5 pigs and
8 hens. How many choices the farmer have ?
❑ 6c3 * 5c2 * 8c4
❑ Ex2: From 8 men and 4 women a team of 5 is to be formed .In how many ways can
this be done so as to include at least one woman.
❑ 12c5 (Total)- 8c5(Only M)

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 108

 UNIT I Discrete Mathematics

Combinations

Ex3: There are 10 points in a 2d plane .Four of them are collinear. Find the number of
straight lines that can be joined by joining these points.
Ans: 10c2(Total) – 4c2(Collinear) - 1(unique line) = 40

Ex4: A bag contains 7 white balls and 5 black balls. Find the number of ways that 4 balls
can be drawn from the bag if
1. They can be of either color
2. Two must be white and two black.
3. They must all of the same color.
Ans: 1) 12c4 2) 7c2 * 5c2 3) 7c4+5c4

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 109

 UNIT I Discrete Mathematics

Examples of Permutations & Combinations

Arrangements or Permutations
Eg 1. A maths debating team consists of 4 speakers.
a) In how many ways can all 4 speakers be arranged in a row for
a photo?
b) How many ways can the captain and vice-captain be chosen?

Eg 2. A flutter on the horses There are 7 horses in a race.

a) In how many different orders can the horses finish?
b) b) How many trifectas (1st , 2nd and 3rd) are possible?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 110

 UNIT I Discrete Mathematics

Permutations with Restrictions

Eg. In how many ways can 5 boys and 4 girls be arranged on a bench if
a)there are no restrictions?
c)boys and girls alternate?
Eg. In how many ways can 5 boys and 4 girls be arranged on a bench if

c) boys and girls are in separate groups Anne and Jim wish to stay together?

d) Anne and Jim wish to stay together?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 111

 UNIT I Discrete Mathematics

Arrangements with Repetitions

If we have n elements of which x are alike of one

kind, y are alike of another kind, z are alike of
another kind,
………… then the number of ordered selections
or
permutations is given by:

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 112

 UNIT I Discrete Mathematics

Arrangements with Repetitions

Eg.1 How many different arrangements of the word PARRAMATTA are

possible?
Eg 2. How many arrangements of the letters of the word REMAND are
possible if:
a) there are no restrictions?
b) they begin with RE?
c) they do not begin with RE?
Eg [Link] are 6 boys who enter a boat with 8 seats, 4 on each side. In how many
ways can
a)they sit anywhere?
b)two boys A and B sit on the port side and another boy W sit on the starboard side?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 113

 UNIT I Discrete Mathematics

Arrangements with Repetitions

Eg 3. From the digits 2, 3, 4, 5, 6

a) how many numbers greater than 4000 can be formed?

b) how many 4 digit numbers would be even?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 114

 UNIT I Discrete Mathematics

Circular Arrangements

❑ Circular arrangements are permutations in which objects are arranged in a circle.

❑ Consider arranging 5 objects (a, b, c, d, e) around a circular table.

abcde bcdea
cdeab
deabc eabcd

are different in a line, but are identical around a circle

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 115

 UNIT I Discrete Mathematics

Circular Arrangements

To calculate the number of ways in which n objects can be arranged in a circle, we

arbitrarily fix the position of one object, so the remaining (n-1) objects can be arranged as
if they were on a straight line in (n-1)! ways.
i.e. the number of arrangements =(n – 1) !
in a circle

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 116

 UNIT I Discrete Mathematics

Circular Arrangements

Eg 1. At a dinner party 6 men and 6 women sit at a round table. In

how many ways can they sit if:
a) there are no restrictions
b) men and women alternate
Eg 2. At a dinner party 6 men and 6 women sit at a round table.
In how many ways can they sit if:

c) Ted and Carol must sit together

d) Bob, Ted and Carol must sit together

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 117

 UNIT I Discrete Mathematics

Circular Arrangements

Eg 3. In how many ways can 8 differently coloured beads be threaded on a string?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 118

 UNIT I Discrete Mathematics

Combinations

Eg 1. How many ways can a basketball team of 5 players be

chosen from 8 players?

Eg 2. A committee of 5 people is to be chosen from a group of 6

men and 4 women. How many committees are possible if
a) there are no restrictions?
b) one particular person must be chosen on the committee?
c) one particular woman must be excluded from the committee?
d) there are to be 3 men and 2 women?
e) there are to be men only?
f) there is to be a majority of women?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 119

 UNIT I Discrete Mathematics

Combinations

Eg 3. In a hand of poker, 5 cards are dealt from a regular pack of 52 cards.

(i) What is the total possible number of hands if there are no restrictions?
ii) In how many of these hands are there:
a) 4 Kings?
b) 2 Clubs and 3 Hearts?
c) all Hearts?
d) all the same colour?
e) four of the same kind?
f) 3 Aces and two Kings?

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 120

 UNIT I Discrete Mathematics

Further Permutations and Combinations

Eg.1 If 4 Maths books are selected from 6 different Maths books and
3 English books are chosen from 5 different English books, how
many ways can the seven books be arranged on a shelf:
a)If there are no restrictions?
b)If the 4 Maths books remain together?
c) a Maths book is at the beginning of the shelf?
d)Maths and English books alternate
e)A Maths is at the beginning and an English book is in the middle
of the shelf.
Eg 2. (i) How many different 8 letter words are possible using the letters of the word SYLLABUS ?
(ii) If a word is chosen at random, find the probability that the word:
a) contains the two S’s together
b)begins and ends with L

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 121

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 122

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 123

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 124

 UNIT I Discrete Mathematics

Pune Institute of Computer Technology, Pune Prof. P. R. Navghare 125