A Walk Through Combinatorics - An Introduction to Enumeration and Graph Theory

Title......Page 3
Copyright......Page 4
Dedication......Page 5
Foreword......Page 6
Preface......Page 8
Acknowledgments......Page 10
Contents......Page 12
1.1 The Basic Pigeon-Hole Principle......Page 18
1.2 The Generalized Pigeon-Hole Principle......Page 20
Exercises......Page 26
Supplementary Exercises......Page 28
Solutions to Exercises......Page 29
2.1 Weak Induction......Page 36
2.2 Strong Induction......Page 41
Exercises......Page 43
Supplementary Exercises......Page 45
Solutions to Exercises......Page 46
3.1 Permutations......Page 54
3.2 Strings over a Finite Alphabet......Page 57
3.3 Choice Problems......Page 60
Exercises......Page 64
Supplementary Exercises......Page 68
Solutions to Exercises......Page 70
4.1 The Binomial Theorem......Page 82
4.2 The Multinomial Theorem......Page 87
4.3 When the Exponent Is Not a Positive Integer......Page 89
Exercises......Page 91
Supplementary Exercises......Page 94
Solutions to Exercises......Page 97
5.1 Compositions......Page 106
5.2 Set Partitions......Page 108
5.3 Integer Partitions......Page 111
Exercises......Page 118
Supplementary Exercises......Page 119
Solutions to Exercises......Page 120
6. Not So Vicious Cycles. Cycles in Permutations......Page 126
6.1 Cycles in Permutations......Page 127
6.2 Permutations with Restricted Cycle Structure......Page 132
Exercises......Page 137
Supplementary Exercises......Page 139
Solutions to Exercises......Page 141
7.1 Enumerating The Elements of Intersecting Sets......Page 148
7.2 Applications of the Sieve Formula......Page 151
Exercises......Page 155
Solutions to Exercises......Page 156
8.1 Ordinary Generating Functions......Page 162
8.2 Exponential Generating Functions......Page 177
Exercises......Page 184
Supplementary Exercises......Page 186
Solutions to Exercises......Page 189
9.1 The Notion of Graphs. Eulerian Walks......Page 200
9.2 Hamiltonian Cycles......Page 205
9.3 Directed Graphs......Page 207
9.4 The Notion of Isomorphisms......Page 210
Exercises......Page 213
Supplementary Exercises......Page 216
Solutions to Exercises......Page 218
10.1 Minimally Connected Graphs......Page 226
10.2 Minimum-weight Spanning Trees. Kruskal\'s Greedy Algorithm......Page 233
10.3 Graphs and Matrices......Page 237
10.4 The Number of Spanning Trees of a Graph......Page 240
Exercises......Page 245
Supplementary Exercises......Page 247
Solutions to Exercises......Page 249
11.1 Introduction......Page 258
11.2 Bipartite Graphs......Page 260
11.3 Matchings in Bipartite Graphs......Page 265
11.4 More Than Two Colors......Page 271
11.5 Matchings in Graphs That Are Not Bipartite......Page 273
Exercises......Page 276
Supplementary Exercises......Page 278
Solutions to Exercises......Page 279
12.1 Euler\'s Theorem for Planar Graphs......Page 286
12.2 Polyhedra......Page 289
12.3 Coloring Maps......Page 296
Exercises......Page 298
Supplementary Exercises......Page 299
Solutions to Exercises......Page 300
13.1 Ramsey Theory for Finite Graphs......Page 304
13.2 Generalizations of the Ramsey Theorem......Page 309
13.3 Ramsey Theory in Geometry......Page 312
Exercises......Page 315
Supplementary Exercises......Page 316
Solutions to Exercises......Page 318
14.1 Pattern Avoidance......Page 324
14.2 Stack Sortable Permutations......Page 336
Exercises......Page 347
Supplementary Exercises......Page 348
Solutions to Exercises......Page 350
15.1 The Notion of Probability......Page 362
15.2 Non-constructive Proofs......Page 365
15.3 Independent Events......Page 368
15.4 Expected Values......Page 373
Exercises......Page 380
Supplementary Exercises......Page 382
Solutions to Exercises......Page 385
16.1 The Notion of Partially Ordered Sets......Page 392
16.2 The Möbius Function of a Poset......Page 397
16.3 Lattices......Page 405
Exercises......Page 412
Supplementary Exercises......Page 414
Solutions to Exercises......Page 416
17.1 In Lieu of Definitions......Page 424
17.2 Sorting Algorithms......Page 426
17.3 Algorithms on Graphs......Page 434
Exercises......Page 443
Solutions to Exercises......Page 445
18.1 Turing Machines......Page 450
18.2 Complexity Classes......Page 453
Exercises......Page 470
Supplementary Exercises......Page 471
Solutions to Exercises......Page 472
Bibliography......Page 478
Index......Page 482