Table of Contents
Foreword vii
Preface ix
Acknowledgments xi
I Basic Methods
1 Seven Is More Than Six. The Pigeon-Hole Principle 1
1.1 The Basic Pigeon-Hole Principle 1
1.2 The Generalized Pigeon-Hole Principle 3
Exercises 9
Supplementary Exercises 11
Solutions to Exercises 13
2 One Step at a Time. The Method of Mathematical Induction 21
2.1 Weak Induction 21
2.2 Strong Induction 26
Exercises 28
Supplementary Exercises 30
Solutions to Exercises 31
II Enumerative Combinatorics
3 There Are A Lot Of Them. Elementary Counting Problems 39
3.1 Permutations 39
3.2 Strings over a Finite Alphabet 42
3.3 Choice Problems 45
Exercises 49
Supplementary Exercises 53
Solutions to Exercises 55
4 No Matter How You Slice It. The Binomial Theorem and Related Identities 67
4.1 The Binomial Theorem 67
4.2 The Multinomial Theorem 72
4.3 When the Exponent Is Not a Positive Integer 74
Exercises 76
Supplementary Exercises 79
Solutions to Exercises 82
5 Divide and Conquer. Partitions 93
5.1 Compositions 93
5.2 Set Partitions 95
5.3 Integer Partitions 98
Exercises 105
Supplementary Exercises 106
Solutions to Exercises 108
6 Not So Vicious Cycles. Cycles in Permutations 113
6.1 Cycles in Permutations 114
6.2 Permutations with Restricted Cycle Structure 120
Exercises 124
Supplementary Exercises 126
Solutions to Exercises 129
7 You Shall Not Overcount. The Sieve 135
7.1 Enumerating The Elements of Intersecting Sets 135
7.2 Applications of the Sieve Formula 138
Exercises 142
Supplementary Exercises 143
Solutions to Exercises 144
8 A Function Is Worth Many Numbers. Generating Functions 149
8.1 Ordinary Generating Functions 149
8.1.1 Recurrence Relations and Generating Functions 149
8.1.2 Products of Generating Functions 156
8.1.3 Compositions of Generating Functions 163
8.2 Exponential Generating Functions 166
8.2.1 Recurrence Relations and Exponential Generating Functions 166
8.2.2 Products of Exponential Generating Functions 168
8.2.3 Compositions of Exponential Generating Functions 171
Exercises 174
Supplementary Exercises 176
Solutions to Exercises 178
III Graph Theory
9 Dots and Lines. The Origins of Graph Theory 189
9.1 The Notion of Graphs. Eulerian Trails 189
9.2 Hamiltonian Cycles 194
9.3 Directed Graphs 196
9.4 The Notion of Isomorphisms 199
Exercises 202
Supplementary Exercises 205
Solutions to Exercises 208
10 Staying Connected. Trees 215
10.1 Minimally Connected Graphs 215
10.2 Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm 221
10.3 Graphs and Matrices 225
10.3.1 Adjacency Matrices of Graphs 225
10.4 The Number of Spanning Trees of a Graph 228
Exercises 233
Supplementary Exercises 236
Solutions to Exercises 238
11 Finding A Good Match. Coloring and Matching 247
11.1 Introduction 247
11.2 Bipartite Graphs 249
11.3 Matchings in Bipartite Graphs 254
11.4 More Than Two Color 260
11.5 Matchings in Graphs That Are Not Bipartite 262
Exercises 266
Supplementary Exercises 267
Solutions to Exercises 269
12 Do Not Cross. Planar Graphs 275
12.1 Euler's Theorem for Planar Graphs 275
12.2 Polyhedra 278
12.3 Coloring Maps 285
Exercises 287
Supplementary Exercises 288
Solutions to Exercises 290
IV Horizons
13 Does It Clique? Ramsey Theory 293
13.1 Ramsey Theory for Finite Graphs 293
13.2 Generalizations of the Ramsey Theorem 298
13.3
Exercises 304
Supplementary Exercises 305
Solutions to Exercises 307
14 So Hard To Avoid. Subsequence Conditions on Permutations 313
14.1 Pattern Avoidance 313
14.2 Stack Sortable Permutations 322
Exercises 334
Supplementary Exercises 335
Solutions to Exercises 338
15 Who Knows What It Looks Like, But It Exists. The Probabilistic Method 349
15.1 The Notion of Probability 349
15.2 Non-constructive Proofs 352
15.3 Independent Events 355
15.3.1 The Notion of Independence and Bayes' Theorem 355
15.3.2 More Than Two Events 359
15.4 Expected Values 360
15.4.1 Linearity of Expectation 361
15.4.2 Existence Proofs Using Expectation 364
15.4.3 Conditional Expectation 365
Exercises 367
Supplementary Exercises 370
Solutions to Exercises 373
16 At Least Some Order. Partial Orders and Lattices 381
16.1 The Notion of Partially Ordered Sets 381
16.2 The Möbius Function of a Poset 387
16.3 Lattices 394
Exercises 401
Supplementary Exercises 403
Solutions to Exercises 406
17 As Evenly As Possible. Block Designs and Error Correcting Codes 413
17.1 Introduction 413
17.1.1 Moto-cross Races 413
17.1.2 Incompatible Computer Programs 415
17.2 Balanced Incomplete Block Designs 417
17.3 New Designs From Old 419
17.4 Existence of Certain BIBDs 424
17.4.1 A Derived Design of a Projective Plane 426
17.5 Codes and Designs 427
17.5.1 Coding Theory 427
17.5.2 Error Correcting Codes 427
17.5.3 Formal Definitions on Codes 429
Exercises 436
Supplementary Exercises 438
Solutions to Exercises 440
18 Are They Really Different? Counting Unlabeled Structures 447
18.1 Enumeration Under Group Action 447
18.1.1 Introduction 447
18.1.2 Groups 448
18.1.3 Permutation Groups 450
18.2 Counting Unlabeled Trees 457
18.2.1 Counting Rooted Non-plane 1-2 trees 457
18.2.2 Counting Rooted Non-plane Trees 460
18.2.3 Counting Unrooted Trees 463
Exercises 469
Supplementary Exercises 472
Solutions to Exercises 474
19 The Sooner The Better Combinatorial Algorithms 481
19.1 In Lieu of Definitions 481
19.1.1 The Halting Problem 482
19.2 Sorting Algorithms 483
19.2.1 BubbleSort 483
19.2.2 MergeSort 486
19.2.3 Comparing the Growth of Functions 490
19.3 Algorithms on Graphs 491
19.3.1 Minimum-cost Spanning Trees, Revisited 491
19.3.2 Finding the Shortest Path 495
Exercises 500
Supplementary Exercises 502
Solutions to Exercises 503
20 Does Many Mean More Than One? Computational Complexity 509
20.1 Turing Machines 509
20.2 Complexity Classes 512
20.2.1 The Class P 512
20.2.2 The Class NP 514
20.2.3 NP-complete Problems 521
20.2.4 Other Complexity Classes 526
Exercises 529
Supplementary Exercises 531
Solutions to Exercises 532
Bibliography 537
Index 541
