Preface 1
Chapter 1. What is Combinatorics? 1
1.1 Example. Perfect covers of chessboards 4
1.2 Example. Cutting a cube 8
1.3 Example. Magic squares 10
1.4 Example. The 4-color problem 13
1.5 Example. The problem of the 36 officers 14
1.6 Example. Shortest-route problem 16
1.7 Example. The game of Nim 18
1.8 Exercises 21
2.1 Pigeonhole principle: Simple form 27
Chapter 2. The Pigeonhole Principle 27
2.2 Pigeonhole principle: Strong form 32
2.3 A theorem of Ramsey 36
2.4 Exercises 41
Chapter 3. Permutations and Combinations 45
3.1 Two basic counting principles 45
3.2 Permutations of sets 53
3.3 Combinations of Sets 60
3.4 Permutations of multisets 64
3.5 Combinations of multisets 70
3.6 Exercises 75
Chapter 4. Generating Permutations and Combinations 81
4.1 Generating permutations 81
4.2 Inversions in permutations 87
4.3 Generating combinations 93
4.5 Partial orders and equivalence relations 109
4.6 Exercises 116
Chapter 5. The Binomial Coefficients 122
5.1 Pascal s formula 122
5.2 The binomial theorem 127
5.3 Identities 130
5.4 Unimodality of binomial coefficients 137
5.5 The multinomial theorem 143
5.6 Newton s binomial theorem 147
5.7 More on partially ordered sets 149
5.8 Exercises 152
Chapter 6. The Inclusion-Exclusion Principle and Applications 159
6.1 The inclusion-exclusion principle 159
6.2 Combinations with repetition 168
6.3 Derangements 172
6.4 Permutations with forbidden positions 178
6.5 Another forbidden position problem 183
6.6 Exercises 185
Chapter 7. Recurrence Relations and Generating Functions 190
7.1 Some number sequences 191
7.2 Linear homogeneous recurrence relations 202
7.3 Non-homogeneous recurrence relations 213
7.4 Generating functions 220
7.5 Recurrences and generating functions 227
7.6 A geometry example 235
7.7 Exponential generating functions 240
7.8 Exercises 246
Chapter 8. Special Counting Sequences 252
8.1 Catalan numbers 252
8.2 Difference sequences and Stirling numbrs 261
8.3 Partition numbers 281
8.4 A geometric problem 285
8.5 Exercises 290
Chapter 9. Matchings in Bipartite Graphs 294
9.1 General problem formulation 295
9.2 Matchings 302
9.3 Systems of distinct representatives 319
9.4 Stable marriages 324
9.5 Exercises 332
Chapter 10. Combinatorial Designs 337
10.1 Modular arithmetic 337
10.2 Block designs 350
10.3 Steiner triple systems 362
10.4 Latin squares 369
10.5 Exercises 393
Chapter 11. Introduction to Graph Theory 400
11.1 Basic properties 401
11.2 Eulerian trails 412
11.3 Hamilton chains and cycles 422
11.4 Bipartite multigraphs 429
11.5 Trees 436
11.6 The Shannon switching game 443
11.7 More on trees 450
11.8 Exercises 463
Chapter 12. Digraphs and Networks 475
12.1 Digraphs 475
12.2 Networks 488
12.3 Exercises 496
Chapter 13. More on Graph Theory 501
13.1 Chromatic number 502
13.2 Plane and planar graphs 514
13.3 A 5-color theorem 519
13.4 Independence number and clique number 523
13.5 Connectivity 533
13.6 Exercises 540
Chapter 14. Polya Counting 546
14.1 Permutation and Symmetry groups 547
14.2 Burnside s theorem 559
14.3 Polya s counting formula 566
14.4 Exercises 586
Answers and Hints to Exercises 592
Bibliography 607
Index 609