Foundations of Discrete Mathematics with Algorithms and Programming

Cover
......Page 1
Half Title
......Page 2
Title
......Page 4
Copyrights
......Page 5
Translation......Page 6
Dedication
......Page 7
Contents......Page 8
Preface......Page 12
1 Sets, Relations and Functions......Page 18
1.1 Introduction......Page 19
1.2 Functions......Page 22
1.3 Equivalence Relations......Page 26
1.4 Finite and Innite Sets......Page 28
1.5 Cardinal Numbers of Sets......Page 31
1.6 Power Set of a Set......Page 34
1.7 Exercises......Page 36
1.8 Partially Ordered Sets......Page 37
1.9 Lattices......Page 42
1.10.2 Examples of Boolean Algebras......Page 51
1.11 Atoms in a Lattice......Page 55
1.12 Exercises......Page 59
2 Combinatorics......Page 64
2.1 What Is Combinatorics?......Page 65
2.2 Elementary Counting Principles......Page 68
2.3 Permutations and Combinations......Page 81
2.3.1 Sums and Products......Page 96
2.4 Binomial Theorem......Page 100
2.5 Multinomial Coefficients......Page 108
2.6 Stirling Numbers......Page 120
2.7 Stirling Number of the Second Kind n k......Page 130
2.8 Bell Numbers......Page 142
2.9 The Principle of Inclusion......Page 144
2.9.1 Applications of Inclusion and Exclusion Principle......Page 149
2.9.2 Application of Inclusion and Exclusion Principle to Elementary Number Theory . .......Page 154
2.9.3 Applications to Permanents......Page 160
2.10 Generating Functions......Page 169
2.10.1 Solving Recurrence Relations Using Generating Function Techniques......Page 174
2.10.2 Catalan Numbers......Page 177
2.11 Generating Subsets......Page 183
2.12 Exercises......Page 192
3 Basics of Number Theory......Page 200
3.2 Divisibility......Page 201
3.3 gcd and lcm of Two Integers......Page 203
3.4 Primes......Page 206
3.5 Exercises......Page 210
3.6 Congruences......Page 211
3.7 Complete System of Residues......Page 214
3.8 Linear Congruences......Page 219
3.9 Lattice Points Visible from the Origin......Page 223
3.10 Exercises......Page 226
3.11 Some Arithmetical Functions......Page 227
3.13 The Big O Notation......Page 235
4.1 The Idea of a Graph......Page 242
4.2 An Informal and Intuitive......Page 251
4.3 Multigraph or Undirected Graph......Page 256
4.4 Some Special Graphs......Page 261
4.5 Graphs and Subgraphs......Page 281
4.6 Walks, Paths, Cycles......Page 288
4.7 Connectedness......Page 292
4.8 Graphs and Puzzles......Page 300
4.8.1 An Application......Page 305
4.8.2 Two Friendship Theorems......Page 306
4.8.3 Pandava Princes Problem and 3 Houses,3 Utilities Problem......Page 309
4.9 Ramsey Numbers......Page 310
4.10 Graph Algebra......Page 325
4.11 Exercises......Page 331
5 Introduction to Algorithms......Page 342
5.1 Algorithms......Page 343
5.2 Complexity of Algorithms......Page 347
5.3 An Overview of a Classical Computer......Page 370
5.4 Introduction to Programming......Page 377
5.4.1 Parameter Passing......Page 390
5.4.2 Recursion......Page 398
5.5 Introduction to Data Structures......Page 404
5.5.1 Access Restricted Lists......Page 423
5.6 Examples of Algorithms......Page 433
5.7 Exercises......Page 456
6.1 Introduction......Page 464
6.2 Algebra of Propositions......Page 465
6.3 Proofs in Mathematics......Page 471
6.3.1 Universal and Existential Quantiers......Page 474
6.4 Probability......Page 475
Appendices Answers to Even-Numbered Exercises......Page 494
A Answers to Chapter 1......Page 496
B Answers to Chapter 2......Page 500
C Answers to Chapter 3......Page 504
D Answers to Chapter 4......Page 508
E Answers to Chapter 5......Page 514
F Answers to Chapter 6......Page 520
Index......Page 524