Unit III - 1 Discrerte maths and its applciation

In the era of machine learning (ML) and artificial intelligence (AI), the importance of mathematical foundations cannot be overstated. Discrete mathematics forms a critical part of this foundation, providing the tools and structures that enable the development of algorithms, computational models, and problem-solving techniques. Discrete mathematics, unlike continuous mathematics, deals with distinct, separate values, making it particularly relevant to fields like computer science, where digital systems rely on discrete data and operations.

For students of computer science, mastering discrete mathematics is essential to understanding the workings of computer algorithms, data structures, and the underlying logic of computational processes. However, its significance extends beyond just computer science students. Those from other disciplines who wish to delve into the intricacies of ML and AI will also benefit immensely from a strong grasp of discrete mathematics.

The study of discrete mathematics encompasses various topics, including set theory, logic, combinatorics, graph theory, and probability—all of which are essential in the realms of ML and AI. This PDF serves as an excellent resource, offering a comprehensive and thorough explanation of these topics. It provides not only theoretical insights but also practical applications, making it an ideal study material for those eager to master the mathematical concepts that drive ML and AI.

In this document, we will explore the key topics covered in the PDF, demonstrating how they are applied in machine learning and AI. Additionally, we will discuss the importance of discrete mathematics for students who may not have a computer science background but are interested in gaining a deeper understanding of the technologies that are shaping the future.

What is Discrete Mathematics?
Discrete mathematics is a branch of mathematics that deals with discrete elements, as opposed to continuous elements. In discrete mathematics, the objects under study are countable, such as integers, graphs, and logical statements. It is a foundational area of mathematics that underpins computer science and has wide-ranging applications in various fields, including ML, AI, cryptography, network theory, and more.

Unlike calculus, which deals with smooth curves and continuous functions, discrete mathematics is concerned with structures that have distinct, separated values. This is why it is especially useful in computer science, where digital systems and algorithms work with discrete steps and finite sets of data.

The primary areas of discrete mathematics include:

Set Theory: The study of collections of objects.
Logic: The study of reasoning and truth values.
Combinatorics: The study of counting and arrangement.
Graph Theory: The study of graphs, which are mathematical representations of networks.
Probability: The study of likelihood and random events in discrete settings.
These areas, as we will see, are crucial in developing

1. CS201 –Discrete Mathematics
Dr. Sadhvi
Assistant Professor
CSE, IIIT Dharwad

2. Counting
2

3. •Counting problemsare of the following kind:
•“How manydifferent 8-letter passwords are there?”
•“How manypossible 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?”)
3

4. Combinatorics
Count the number of ways to put things together into various
combinations.
e.g.If a password is 6, 7, or 8 characters long; a character is an uppercase letters or a digit, and the
password is required to include at least one digit -how many passwords can there be?
Or, how many graphs are there on Nnodes? How many of those are 3-colorable?
Many uses in discrete math (because of all the discrete structures),
including e.g. probability theory
E.g., what is the probability that a randomly generated graph is
3-colorable?
First, two most basic rules:
•Sum rule
•Product rule
How can we figure that out?

5. Sum Rule
Let us consider two tasks:
•mis the number of ways to do task 1
•nis the number of ways to do task 2
•Tasks are independentof each other, i.e.,
•Performing task 1does not accomplish task 2and vice versa.
Sum rule:the number of ways that “eithertask 1ortask 2
can be done, but not both”, is m + n.
Generalizes to multiple tasks ...
Task 1
Task 2

6. Example
A student can choose a computer project from one of
three lists. The three lists contain 23, 15, and 19
possible projects respectively. How many possible
projects are there to choose from?
6
23+15+19

7. Sum rule example
How many strings of 4 decimal digits, have exactly three digits
that are 9s?
•The string can have:
•The non-9as the first digit
•OR the non-9 as the second digit
•OR the non-9 as the third digit
•OR the non-9 as the fourth digit
•Thus, we use the sum rule
•For each of those cases, there are 9 possibilities for the non-9
digit (any number other than 9)
•Thus, the answer is 9+9+9+9 = 36
7

8. Set Theoretic Version
If Ais the set of ways to do task 1, and Bthe set of ways to
do task 2, and if Aand Bare disjoint,then:
“the ways to do either task 1 or 2 are
AB, and|AB| = |A| + |B|”
8

9. Product Rule
Let us consider two tasks:
•mis the number of ways to do task 1
•nis the number of ways to do task 2
•Tasks are independentof each other, i.e.,
•Performing task 1does not accomplish task 2 and vice versa.
Product rule: the number of ways that “bothtasks 1 and 2 can be
done” in mn.
Generalizes to multiple tasks ...
task 1 task 2

10. Product rule example
•There are 18 math majors and 325 CS majors
•How many ways are there to pick one math major and
one CS major?
Total is 18 * 325 = 5850
10

11. Product Rule
How many functions are there from set A to set B?
A B
To define each function we have to make 3 choices, one for each
element of A. Each has 4 options (to select an element from B).
How many ways can each choice
be made?
4 44
4
3
= 64 = |B|
|A|
So, how many Boolean
functions on n vars?
2
2
n

12. How many one-to-one functions are there from set A to set B?
A B
To define each function we have to make 3 choices, one for each
element of A.
How many ways can each choice
be made?
4 32
24
# is called P(n,r) for r-permutations
(here P(4,3) ---“3 unique choices out of 4
objects”, order matters)
Ex: S={1,2,3}. Ordered arrangement
3,1,2 is called a permutation.
There are n!of those (product rule).
3,2 is a r-permutation(r=2).
There are n!/(n-r!) of those.
Hmm. What if |A| = 4?
= 4! / (4-3)!

13. Product rule example
How many strings of 4 decimal digits, do not contain the same digit
twice?
We want to chose a digit, then another that is not the same, then
another…
•First digit: 10 possibilities
•Second digit: 9 possibilities (all but first digit)
•Third digit: 8 possibilities
•Fourth digit: 7 possibilities
Total = 10*9*8*7 = 5040
How many strings of 4 decimal digits, end with an even digit?
First three digits have 10 possibilities
Last digit has 5 possibilities
Total = 10*10*10*5 = 5000
13

14. Set Theoretic Version
If Ais the set of ways to do task 1, and Bthe set of ways to do
task 2, and if Aand Bare disjoint, then
The ways to do both task 1 and 2 can be represented as AB,
and |AB|=|A|·|B|
14

15. Count the number of ways to put things together into
various combinations.
E.g.If a password is 6, 7, or 8 characters long; a character is an uppercase
letters or a digit, and the password is required to include at least one digit.
How many passwords can there be?
Let P –total number of possible passwords
P
i –total number of passwords of length i, i = 6,7,8
P = P
6+ P
7+ P
8 (sum rule)
P
i–computing it directly is tricky
“popular” counting trick:let’s calculate all of them, including those with no
digits and then subtract the ones with no digits.
P
i= 36
i
–26
i
P= 36
6
–26
6
+36
7
–26
7
+ 36
8
–26
8
= 2,684,483,063,360
More complex counting problems

16. IP Address Example (Internet Protocol v. 4)
An address is a string of 32 bits –it begins with a
network id (netid), followed by a host number (hostid),
which identifies a computer as a member of a particular
network.
Main computer addresses are in one of 3 types:
•Class A (largest networks):address contains a 0 followed by 7-bit “netid”≠ 17, and a 24-
bit “hostid”
•Class B (medium networks):address contains a 10 followed by a 14-bit netid and a 16-bit
hostid.
•Class C (smallest networks):address contains a 110 has 21-bit netid and an 8-bit hostid.
Netids all 1s are not allowed. Hostids that are all 0s or all 1s are not allowed.
How many valid IP addresses are there?

17. Example Using Both Rules: IP address solution
(# addrs) = (# class A) + (# class B) + (# class C)
(by sum rule)
# class A = (# valid netids)·(# valid hostids)
(by product rule)
(# valid class A netids) = 2
7
− 1 = 127.
(# valid class A hostids) = 2
24
− 2 = 16,777,214.
Continuing in this fashion we find the answer is:
3,737,091,842 (3.7 billion IP addresses)

18. Wedding picture example
Consider a wedding picture of 6 people
• There are 10 people, including the bride and groom
How many possibilities are there if the bride must be in the
picture?
Product rule: place the bride AND then place the rest of the party
First place the bride
•She can be in one of 6 positions
Next, place the other five people via the product rule
•There are 9 people to choose for the second person, 8 for the third, etc.
•Total = 9*8*7*6*5 = 15120
Product rule yields 6 * 15120 = 90,720 possibilities
18
Q.: Are we counting same subsets of folks in different positions?
Yes! (note bride is treated “differently”; has to be in the picture)

19. Wedding pictures example
Consider a wedding picture of 6 people
• There are 10 people, including the bride and groom
How many possibilities are there if the bride and groom must both be
in the picture
Product rule: place the bride/groom AND then place the rest of the
party
First place the bride and groom
•She can be in one of 6 positions
•He can be in one 5 remaining positions
•Total of 30 possibilities
Next, place the other four people via the product rule
•There are 8 people to choose for the third person, 7 for the fourth, etc.
•Total = 8*7*6*5 = 1680
Product rule yields 30 * 1680 = 50,400 possibilities
19

20. Wedding pictures example
Consider a wedding picture of 6 people
• There are 10 people, including the bride and groom
How many possibilities are there if only one of the bride or the groom are in the
picture?
Sum rule: place only the bride
• Product rule: place the bride AND then place the rest of the party
• First place the bride
She can be in one of 6 positions
• Next, place the other five people via the product rule
There are 8 people to choose for the second person, 7 for the third, etc.
• We can’t choose the groom!
Total = 8*7*6*5*4 = 6720
• Product rule yields 6 * 6720 = 40,320 possibilities
 OR place only the groom
• Same possibilities as for bride: 40,320
Sum rule yields 40,320 + 40,320 = 80,640 possibilities
20

21. Wedding pictures example
Consider a wedding picture of 6 people
• There are 10 people, including the bride and groom
Alternative means to get the answer
How many possibilities are there if only one of the bride or the groom are in the
picture?
Total ways to place the bride (with or without groom): 90,720
• See before.
Total ways for both the bride and groom: 50,400
• See before.
Total ways to place ONLY the bride: 90,720 –50,400 = 40,320
Same number for the groom
Total = 40,320 + 40,320 = 80,640
21

22. The inclusion-exclusion principle
When counting the possibilities, we can’t include a given
outcome more than once.
|A
1U A
2| = |A
1| + |A
2| -|A
1∩ A
2|
•E.g. Let A
1have 5 elements, A
2have 3 elements, and 1 element be both
in A
1and A
2
•Total in the union is 5+3-1 = 7, not 8
22

23. Inclusion-exclusion example
How may bit strings of length eight start with 1 or end with 00?
Count bit strings that start with 1
•Rest of bits can be anything: 2
7
= 128
•This is |A
1|
Count bit strings that end with 00
•Rest of bits can be anything: 2
6
= 64
•This is |A
2|
Count bit strings that both start with 1 and end with 00
•Rest of the bits can be anything: 2
5
= 32
•This is |A
1∩ A
2|
Use formula |A
1U A
2| = |A
1| + |A
2| -|A
1∩ A
2|
Total is 128 + 64 –32 = 160

24. How many bit strings of length 10 contain either 5 consecutive 0s or 5
consecutive 1s?
Consider 5 consecutive 0s first
Sum rule: the 5 consecutive 0’s can start at position 1, 2, 3, 4, 5, or 6
•Starting at position 1
•Remaining 5 bits can be anything: 2
5
= 32
•Starting at position 2
•First bit must be a 1
•Otherwise, we are including possibilities from the previous case!
•Remaining bits can be anything: 2
4
= 16
•Starting at position 3
•Second bit must be a 1 (same reason as above)
•First bit and last 3 bits can be anything: 2
4
= 16
•Starting at positions 4 and 5 and 6
•Same as starting at positions 2 or 3: 16 each
•Total = 32 + 16 + 16 + 16 + 16 + 16 = 112
The 5 consecutive 1’s follow the same pattern, and have 112
possibilities
There are two cases counted twice (that we thus need to exclude):
0000011111 and 1111100000
Total = 112 + 112 –2 = 222

25. Tree diagrams
We can use tree diagrams to enumerate the possible
choices.
Once the tree is laid out, the result is the number of
(valid) leaves.
25

26. Tree diagrams example
Use a tree diagram to find the number of bit strings of
length four with no three consecutive 0s

27. Pigeonhole Principle
If k+1 objects are assigned to kplaces, then at least1 place
must be assigned ≥2 objects.
Proof: (by contradiction)
Suppose none of the k places contains more than one object. Then the total
number of objects would be at most k. This is a contradiction, since there
are k + 1 objects.
In terms of the assignment function:
If f: A→Band |A|≥|B|+1, then some element of B
has ≥2 pre-images under f. I.e., fis notone-to-one.

28. More pigeons than pigeonholes

29. Example
How many students must be in class to guarantee that at
least two students receive the same score on the final exam,
if the exam is graded on a scale from 0 to 100 points?
102

30. Simple Example
It’s dark; you know that in your drawer there are:
12
10
But you can’t see a thing. How many socks should you get to guarantee a correct pair?
What does it have to do with the pigeon hole principle?
10+12
1 hole per color
A.: 3

31. Generalized Pigeonhole Principle
If N≥k+1objects are assigned to kplaces, then at
leastone place must be assigned at leastN/k
objects.
E.g., there are N = 280 people in a party. There are k = 52
weeks in the year.
•Therefore, there must be atleast1 week during which
at least280/52= 5.38= 6 students in the party have
a birthday.
31

32. Proof of G.P.P.N
k
N
k
k
N
k
k
N
k 




































111
By contradiction. Suppose everyplace has < N/k
objects, thus ≤ N/k−1.
Then the total number of objects is at most
So, there are less than Nobjects, which contradicts
our assumption of Nobjects!

33. G.P.P. Example
Given: There are 280 people in the party. Without knowing
anybody’s birthday, what is the largest value of nfor which we
can prove that at leastnpeople must have been born in the
same month?
Answer:
33
280/12= 23.3= 24

34. A bowl contains 10 red and 10 yellow balls. How many
balls must be selected to ensure3 balls of the same
color?
•One solution:
•Consider 2 balls of each color
•You can’t take another ball without hitting 3
•Thus, the answer is 5
•Via generalized pigeonhole principle
•How many balls are required if there are 2 colors, and one color
must have 3 balls?
•How many pigeons are required if there are 2 pigeon holes, and one
must have 3 pigeons?
•number of boxes: k= 2
•We want N/k= 3
•What is the minimum N?
•N= 5

35. A bowl contains 10 red and 10 yellow balls
How many balls must be selected to ensure3 yellow balls?
•In the “worst” case
•Consider 10 red balls and 2 yellow balls
•You can’t take another ball without hitting 3 yellow balls
•Thus, the answer is 13

36. Permutations
A permutationof a set Sof objects is an ordered
arrangement of the elements of S where each element
appears only once:
e.g., 1 2 3, 2 1 3, 3 1 2
There are n! permutations of n objects. (by product rule)
An ordered arrangement of rdistinctelements of Sis
called an r-permutation.
The number of r-permutations of a set Swith n=|S|
elements is
P(n,r) = n(n−1)…(n−r+1) = n! / (n−r)!
36

37. Permutations
37
In a running race of 12 sprinters, each of the top 5
finishers receives a different medal. How many ways
are there to award the 5 medals?
a)60
b)12
5
c)12!/7!
d)5
12
e)No clue
12 1110 9 8
A.: 12!/7!

38. Permutations
Suppose you “have” time to listen to 10 songs on your
daily jog around campus. There are 6 Atunes, 8 B
tunes, and 3 Ctunes to choose from.
Finally, suppose you still want 4 A, 4 B, and 2 Ctunes,
and the order of the groups doesn’t matter, but you
get dizzy and fall down if all the songs by any one
group aren’t played together.
How many playlists are there?
P(6,4) x P(8,4) x P(3,2) x 3!

39. Permutations
In how many ways can 5 distinct Cats and 3 distinct Dogs stand in
line, if no two Dogs stand together?
C1 C2 C3 C4 C5
5! X P(6,3)
= 5! x C(6,3) x 3!

40. Combinations
The number of ways of choosing relements from S
(order does notmatter).
S={1,2,3}
e.g., 1 2 , 1 3, 2 3
The number of r-combinations C(n,r)of a set with
n=|S| elements is!
( , )
!( )!
n n
C n r
rr n r




40“n choose r”. Also called a “binomial coefficient”.
= P(n,r) / r!
Note: we have C(n,r) = C(n, n−r)

41. Combination Example
How many distinct 7-card hands can be drawn from a standard
52-card deck?
•The order of cards in a hand doesn’t matter.
Answer C(52,7) = P(52,7) / P(7,7)
= 52·51·50·49·48·47·46 / 7·6·5·4·3·2·1
= 52.17.10.7.2.47.23
= 133,784,560
41

42. 48
The binomial theoremprovides a useful method for raising any binomial to a
nonnegative integral power.
Consider the patterns formed by expanding (x+ y)
n
.
(x+ y)
0
= 1
(x+ y)
1
= x+ y
(x+ y)
2
= x
2
+ 2xy+ y
2
(x+ y)
3
= x
3
+ 3x
2
y+3xy
2
+ y
3
(x+ y)
4
= x
4
+ 4x
3
y+6x
2
y
2
+ 4xy
3
+ y
4
(x+ y)
5
= x
5
+ 5x
4
y+ 10x
3
y
2
+ 10x
2
y
3
+5xy
4
+ y
5
Notice that each expansion has n+ 1 terms.
1 term
2 terms
3 terms
4 terms
5 terms
6 terms
Example: (x+y)
10
will have 10 + 1, or 11 terms.
Binomial Coefficients

43. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
49
Consider the patterns formed by expanding (x+ y)
n
.
(x+ y)
0
= 1
(x+ y)
1
= x+ y
(x+ y)
2
= x
2
+ 2xy+ y
2
(x+ y)
3
= x
3
+ 3x
2
y+3xy
2
+ y
3
(x+ y)
4
= x
4
+ 4x
3
y+6x
2
y
2
+ 4xy
3
+ y
4
(x+ y)
5
= x
5
+ 5x
4
y+ 10x
3
y
2
+ 10x
2
y
3
+5xy
4
+ y
5
1. The exponents on xdecrease from nto 0.
The exponents on yincrease from 0 to n.
2. Each term is of degree n.
Example: The 5
th
term of (x+y)
10
is a term with x
6
y
4
.”

44. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
50
The coefficients of the binomial expansion are called binomial
coefficients.The coefficients have symmetry.
The coefficient of x
n–r
y
r
in the expansion of (x+ y)
n
is written
or
n
C
r
.n
r



(x+ y)
5
= x
5
+ 5x
4
y+ 10x
3
y
2
+ 10x
2
y
3
+5xy
4
+ y
5
The first and last coefficients are 1.
The coefficients of the second and second to last terms
are equal to n.
1 1
Example: What are the last 2 terms of (x+y)
10
? Since n= 10,
the last two terms are 10xy
9
+ 1y
10
.
So, the last two terms of (x+y)
10
can be expressed
as
10
C
9 xy
9
+
10
C
10 y
10
or as xy
9
+ y
10
.







9
10 







10
10

45. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
51
The triangular arrangement of numbers below is called Pascal’s
Triangle.
Each number in the interior of the triangle is the sum of the two
numbers immediately above it.
The numbers in the n
th
row of Pascal’s Triangle are the binomial
coefficients for (x+ y)
n
.
11 1
st
row
1 21 2
nd
row
1 331 3
rd
row
14641 4
th
row
15101051 5
th
row
0
th
row1
6 + 4 = 10
1 + 2 = 3

46. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
52
Example: Use the fifth row of Pascal’s Triangle to generate the
sixth row and find the binomial coefficients , ,
6
C
4
and
6
C
2
.6
1


 6
5



5
th
row 1 5 10 10 51
6
th
row6
0


 6
1


 6
2


 6
3


 6
4


 6
5


 6
6



6
C
0
6
C
1
6
C
2
6
C
3
6
C
4
6
C
5
6
C
6
= 6 = and
6
C
4
= 15 =
6
C
2
.6
1


 6
5



There is symmetry between binomial coefficients.
n
C
r
=
n
C
n–r
161520156 1

47. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
53
Example: Use Pascal’s Triangle to expand (2a+ b)
4
.
(2a+ b)
4
= 1(2a)
4
+ 4(2a)
3
b+ 6(2a)
2
b
2
+ 4(2a)b
3
+ 1b
4
= 1(16a
4
) + 4(8a
3
)b+ 6(4a
2
b
2
) + 4(2a)b
3
+ b
4
= 16a
4
+ 32a
3
b+ 24a
2
b
2
+ 8ab
3
+ b
4
11 1
st
row
1 21 2
nd
row
1331 3
rd
row
14641 4
th
row
0
th
row1

48. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
54
Binomial Theorem

50. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
56
Binomial Theorem
Example: Use the Binomial Theorem to expand(x
4
+ 2)
3
.0
3
C 1
3
C 2
3
C 3
3
C 
34
)2(x 
34
)(x )2()(
24
x 
24
)2)((x 3
)2( 1 
34
)(x  3 )2()(
24
x 3 
24
)2)((x 1 3
)2( 8126
4812
 xxx

51. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
57
Although the Binomial Theorem is stated for a binomial which
is a sumof terms, it can also be used to expand a differenceof
terms.
Simply rewrite
(x-y)
n
as (x+ (–y))
n
and apply the theorem to this sum.
Example: Use the Binomial Theorem to expand (3x–4)
4
.4
)43(x 4
))4(3(x 432234
)4(1)4)(3(4)4()3(6)4()3(4)3(1  xxxx 256)64)(3(4)16)(9(6)4)(27(481
234
 xxxx 25676886443281
234
 xxxx

52. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
58
Example: Use the Binomial Theorem to write the first three
terms in the expansion of (2a+b)
12
....)2(
2
12
)2(
1
12
)2(
0
12
)2(
210111212



























 babaaba ... )2(
!2 )!212(
!12
)2(
!1 )!112(
!12
)2(
!0 )!012(
!12
2101011111212
•••






 babaa ...)2)(11 12()2(12)2(
2101011111212
•  babaa ...135168 24576 4096
2101112
 babaa

53. Copyright © by Houghton Mifflin Company,
Inc. All rights reserved.
59
Example: Find the eighth term in the expansion of (x+ y)
13
.
Think of the first term of the expansion as x
13
y
0
.The power of
yis 1 less than the number of the term in the expansion.
The eighthterm is
13
C
7
x
6
y
7
.
Therefore, the eighth term of (x+ y)
13
is 1716x
6
y
7
.!7 !6
!7)89 1011 12 13(
!7 !6
!13
•
••••••
•
7
13
C 1716
12345 6
89101112 13
•••••
•••••


54. Find the 6
th
term in the expansion of (3a + 2b)
12
Using the Binomial Theorem, let x = 3a and y = 2b
and note that in the 6
th
term, the exponent of y is
m = 5 and the exponent of x is n –m = 12 –5 = 7.
Consequently, the 6
th
term of the expansion is:
57
5
13
yxC 
57
23
!5!7
!789101112
ba


= 55,427,328 a
7
b
5

55. Exercise