This is a textbook for an introductory combinatorics course that can take up one or two semesters. An extensive list of problems, ranging from routine exercises to research questions, is included. In each section, there are also exercises that contain material not explicitly discussed in the preceding text, so as to provide instructors with extra choices if they want to shift the emphasis of their course. Just as with the first edition, the new edition walks the reader through the classic parts of combinatorial enumeration and graph theory, while also discussing some recent progress in the area: on the one hand, providing material that will help students learn the basic techniques, and on the other hand, showing that some questions at the forefront of research are comprehensible and accessible for the talented and hard-working undergraduate. The basic topics discussed are: the twelvefold way, cycles in permutations, the formula of inclusion and exclusion, the notion of graphs and trees, matchings and Eulerian and Hamiltonian cycles. The selected advanced topics are: Ramsey theory, pattern avoidance, the probabilistic method, partially ordered sets, and algorithms and complexity.As the goal of the book is to encourage students to learn more combinatorics, every effort has been made to provide them with a not only useful, but also enjoyable and engaging reading.
Author(s): Miklos Bona
Edition: 2
Publisher: World Scientific Publishing Company
Year: 2006
Language: English
Pages: 490
Cover......Page 1
Title Page......Page 5
Foreword......Page 9
Preface......Page 11
Acknowledgments......Page 13
Contents......Page 15
1.1 The Basic Pigeon-Hole Principle......Page 21
1.2 The Generalized Pigeon-Hole Principle......Page 23
Exercises......Page 29
Supplementary Exercises......Page 31
Solutions to Exercises......Page 32
2.1 Weak Induction......Page 39
2.2 Strong Induction......Page 44
Exercises......Page 46
Supplementary Exercises......Page 48
Solutions to Exercises......Page 49
3.1 Permutations......Page 57
3.2 Strings over a Finite Alphabet......Page 60
3.3 Choice Problems......Page 63
Exercises......Page 67
Supplementary Exercises......Page 71
Solutions to Exercises......Page 73
4.1 The Binomial Theorem......Page 85
4.2 The Multinomial Theorem......Page 90
4.3 When the Exponent Is Not a Positive Integer......Page 92
Exercises......Page 94
Supplementary Exercises......Page 97
Solutions to Exercises......Page 100
5.1 Compositions......Page 109
5.2 Set Partitions......Page 111
5.3 Integer Partitions......Page 114
Exercises......Page 121
Supplementary Exercises......Page 122
Solutions to Exercises......Page 123
6. Not So Vicious Cycles. Cycles in Permutations......Page 129
6.1 Cycles in Permutations......Page 130
6.2 Permutations with Restricted Cycle Structure......Page 135
Exercises......Page 140
Supplementary Exercises......Page 142
Solutions to Exercises......Page 144
7.1 Enumerating The Elements of Intersecting Sets......Page 151
7.2 Applications of the Sieve Formula......Page 154
Exercises......Page 158
Solutions to Exercises......Page 159
8.1.1 Recurrence Relations and Generating Functions......Page 165
8.1.2 Products of Generating Functions......Page 172
8.1.3 Compositions of Generating Functions......Page 177
8.2.1 Recurrence Relations and Exponential Generating Functions......Page 180
8.2.2 Products of Exponential Generating Functions......Page 182
8.2.3 Compositions of Exponential Generating Functions......Page 184
Exercises......Page 187
Supplementary Exercises......Page 189
Solutions to Exercises......Page 192
9.1 The Notion of Graphs. Eulerian Walks......Page 203
9.2 Hamiltonian Cycles......Page 208
9.3 Directed Graphs......Page 210
9.4 The Notion of Isomorphisms......Page 213
Exercises......Page 216
Supplementary Exercises......Page 219
Solutions to Exercises......Page 221
10.1 Minimally Connected Graphs......Page 229
10.2 Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm......Page 236
10.3.1 Adjacency Matrices of Graphs......Page 240
10.4 The Number of Spanning Trees of a Graph......Page 243
Exercises......Page 248
Supplementary Exercises......Page 250
Solutions to Exercises......Page 252
11.1 Introduction......Page 261
11.2 Bipartite Graphs......Page 263
11.3 Matchings in Bipartite Graphs......Page 268
11.4 More Than Two Colors......Page 274
11.5 Matchings in Graphs That Are Not Bipartite......Page 276
Exercises......Page 279
Supplementary Exercises......Page 281
Solutions to Exercises......Page 282
12.1 Euler's Theorem for Planar Graphs......Page 289
12.2 Polyhedra......Page 292
12.3 Coloring Maps......Page 299
Exercises......Page 301
Supplementary Exercises......Page 302
Solutions to Exercises......Page 303
13.1 Ramsey Theory for Finite Graphs......Page 307
13.2 Generalizations of the Ramsey Theorem......Page 312
13.3 Ramsey Theory in Geometry......Page 315
Exercises......Page 318
Supplementary Exercises......Page 319
Solutions to Exercises......Page 321
14.1 Pattern Avoidance......Page 327
14.2 Stack Sortable Permutations......Page 339
Exercises......Page 350
Supplementary Exercises......Page 351
Solutions to Exercises......Page 353
15.1 The Notion of Probability......Page 365
15.2 Non-constructive Proofs......Page 368
15.3.1 The Notion of Independence and Bayes' Theorem......Page 371
15.3.2 More Than Two Events......Page 375
15.4 Expected Values......Page 376
15.4.1 Linearity of Expectation......Page 377
15.4.2 Existence Proofs Using Expectation......Page 380
15.4.3 Conditional Expectation......Page 381
Exercises......Page 383
Supplementary Exercises......Page 385
Solutions to Exercises......Page 388
16.1 The Notion of Partially Ordered Sets......Page 395
16.2 The Möbius Function of a Poset......Page 400
16.3 Lattices......Page 408
Exercises......Page 415
Supplementary Exercises......Page 417
Solutions to Exercises......Page 419
17.1 In Lieu of Definitions......Page 427
17.1.1 The Halting Problem......Page 428
17.2.1 BubbleSort......Page 429
17.2.2 MergeSort......Page 432
17.2.3 Comparing the Growth of Functions......Page 436
17.3.1 Minimum-cost Spanning Trees, Revisited......Page 437
17.3.2 Finding the Shortest Path......Page 441
Exercises......Page 446
Solutions to Exercises......Page 448
18.1 Turing Machines......Page 453
18.2.1 The Class
