Introductory Combinatorics (5th Edition)

Cover......Page 1
Preface......Page 6
Contents......Page 10
1 What Is Combinatorics?......Page 14
1.1 Example : Perfect Covers of Chessboards......Page 16
1.2 Example : Magic Squares......Page 20
1.3 Example : The Four-Color Problem......Page 23
1.4 Example : The Problem of the 36 Officers......Page 24
1.5 Example : Shortest-Route Problem......Page 27
1.6 Example : Mutually Overlapping Circles......Page 28
1.7 Example : The Game of Nim......Page 30
1.8 Exercises......Page 33
2.1 Four Basic Counting Principles......Page 40
2.2 Permutations of Sets......Page 48
2.3 Combinations (Subsets) of Sets......Page 54
2.4 Permutations of Multisets......Page 59
2.5 Combinations of Multisets......Page 65
2.6 Finite Probability......Page 69
2.7 Exercises......Page 73
3.1 Pigeonhole Principle : Simple Form......Page 82
3.2 Pigeonhole Principle : Strong Form......Page 86
3.3 A Theorem of Ramsey......Page 90
3.4 Exercises......Page 95
4.1 Generating Permutations......Page 100
4.2 Inversions in Permutations......Page 106
4.3 Generating Combinations......Page 111
4.4 Generating r-Subsets......Page 122
4.5 Partial Orders & Equivalence Relations......Page 126
4.6 Exercises......Page 131
5.1 Pascal's Triangle......Page 140
5.2 The Binomial Theorem......Page 143
5.3 Unimodality of Binomial Coefficients......Page 152
5.4 The Multinomial Theorem......Page 156
5.5 Newton's Binomial Theorem......Page 159
5.6 More on Partially Ordered Sets......Page 162
5.7 Exercises......Page 167
6.1 The Inclusion-Exclusion Principle......Page 174
6.2 Combinations with Repetition......Page 181
6.3 Derangements......Page 185
6.4 Permutations with Forbidden Positions......Page 190
6.5 Another Forbidden Position Problem......Page 194
6.6 Mobius Inversion......Page 196
6.7 Exercises......Page 211
7 Recurrence Relations & Generating Functions......Page 218
7.1 Some Number Sequences......Page 219
7.2 Generating Functions......Page 228
7.3 Exponential Generating Functions......Page 235
7.4 Solving Linear Homogeneous Recurrence Relations......Page 241
7.5 Nonhomogeneous Recurrence Relations......Page 258
7.6 A Geometry Example......Page 266
7.7 Exercises......Page 270
8.1 Catalan Numbers......Page 278
8.2 Difference Sequences & Stirling Numbers......Page 287
8.3 Partition Numbers......Page 304
8.4 A Geometric Problem......Page 311
8.5 Lattice Paths & Schroder Numbers......Page 314
8.6 Exercises......Page 328
9 Systems of Distinct Representatives......Page 334
9.1 General Problem Formulation......Page 335
9.2 Existence of SDRs......Page 339
9.3 Stable Marriages......Page 343
9.4 Exercises......Page 350
10.1 Modular Arithmetic......Page 354
10.2 Block Designs......Page 366
10.3 Steiner Triple Systems......Page 375
10.4 Latin Squares......Page 381
10.5 Exercises......Page 401
11 Introduction to Graph Theory......Page 408
11.1 Basic Properties......Page 409
11.2 Eulerian Trails......Page 419
11.3 Hamilton Paths & Cycles......Page 427
11.4 Bipartite Multigraphs......Page 432
11.5 Trees......Page 439
11.6 The Shannon Switching Game......Page 445
11.7 More on Trees......Page 451
11.8 Exercises......Page 462
12 More on Graph Theory......Page 474
12.1 Chromatic Number......Page 475
12.2 Plane & Planar Graphs......Page 485
12.3 A Five-Color Theorem......Page 489
12.4 Independence Number & Clique Number......Page 493
12.5 Matching Number......Page 501
12.6 Connectivity......Page 506
12.7 Exercises......Page 511
13.1 Digraphs......Page 518
13.2 Networks......Page 529
13.3 Matchings in Bipartite Graphs Revisited......Page 536
13.4 Exercises......Page 546
14 Polya Counting......Page 554
14.1 Permutation & Symmetry Groups......Page 555
14.2 Burnside's Theorem......Page 565
14.3 Polya's Counting Formula......Page 572
14.4 Exercises......Page 589
Answers & Hints to Exercises......Page 595
Bibliography......Page 609
Index......Page 611