Interview
Class notes Mathematics Discrete Mathematics, ISBN: 9781792901690
- Course
- Institution
- Book
Best Notes from Discrete Math Class, covered all important aspects in detail.
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
COS1501 Assignment 3 2023
-
lagrange's theorem
-
MATH1302 Discussion Assignmment Unit 2 (Combinatronics)
Seller
Follow
amarpalsingh
Content preview
Lecture Notes on Discrete MathematicsJuly 30, 2019
T
AF
DR
, 2
DR
AF
T
,Contents
1 Basic Set Theory 7
1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Composition of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 The Natural Number System 25
2.1 Peano Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Other forms of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 28
2.3 Applications of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 31
2.4 Well Ordering Property of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . 33
T
AF
2.5 Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Construction of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
DR
2.7 Construction of Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Countable and Uncountable Sets 43
3.1 Finite and infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Families of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Constructing bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Cantor-Schröder-Bernstein Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5 Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 Elementary Number Theory 61
4.1 Division algorithm and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5 Combinatorics - I 71
5.1 Addition and multiplication rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.1 Counting words made with elements of a set S . . . . . . . . . . . . . . . . . . 73
5.2.2 Counting words with distinct letters made with elements of a set S . . . . . . . 74
5.2.3 Counting words where letters may repeat . . . . . . . . . . . . . . . . . . . . . 75
5.2.4 Counting subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.5 Pascal’s identity and its combinatorial proof . . . . . . . . . . . . . . . . . . . . 77
3
, 4 CONTENTS
5.2.6 Counting in two ways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3 Solutions in non-negative integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4 Binomial and multinomial theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.5 Circular arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.6 Set partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.7 Number partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.8 Lattice paths and Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6 Combinatorics - II 103
6.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Generating Functions and Partitions of n . . . . . . . . . . . . . . . . . . . . . 116
6.4 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.5 Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . 124
7 Introduction to Logic 133
7.1 Logic of Statements (SL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.2 Formulas and truth values in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.3 Equivalence and Normal forms in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.4 Inferences in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.5 Predicate logic (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
T
7.6 Equivalences and Validity in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
AF
7.7 Inferences in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
DR
8 Partially Ordered Sets, Lattices and Boolean Algebra 161
8.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.3 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4 Axiom of choice and its equivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9 Graphs - I 191
9.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.2 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
9.3 Isomorphism in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
9.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.5 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.6 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9.7 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9.8 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.9 Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
10 Graphs - II 221
10.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.2 Matching in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.3 Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
10.4 Degree sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller amarpalsingh. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67866 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now