Introduction to Enumerative Combinatorics (Walter Rudin Student Series in Advanced Mathematics)

Cover......Page 1
Title......Page 2
Contents......Page 6
Foreword......Page 12
Preface......Page 14
Acknowledgments......Page 16
I How: Methods......Page 18
1.1.1 When We Add......Page 20
1.1.2 When We Subtract......Page 21
1.2.1 The Product Principle......Page 23
1.2.2 Using Several Counting Principles......Page 26
1.2.3 When Repetitions Are Not Allowed......Page 27
1.3.1 The Division Principle......Page 31
1.3.2 Subsets......Page 34
1.4.1 Bijective Proofs......Page 37
1.4.2 Properties of Binomial Coefficients......Page 44
1.4.3 Permutations With Repetition......Page 48
1.5 The Pigeonhole Principle......Page 52
1.6 Notes......Page 56
1.7 Chapter Review......Page 57
1.8 Exercises......Page 58
1.9 Solutions to Exercises......Page 63
1.10 Supplementary Exercises......Page 71
2.1.1 Weak Compositions......Page 76
2.1.2 Compositions......Page 79
2.2.1 Stirling Numbers of the Second Kind......Page 80
2.2.2 Recurrence Relations for Stirling Numbers of the Second Kind......Page 82
2.2.3 When the Number of Blocks Is Not Fixed......Page 86
2.3.1 Nonincreasing Finite Sequences of Integers......Page 87
2.3.2 Ferrers Shapes and Their Applications......Page 89
2.3.3 Excursion: Euler's Pentagonal Number Theorem .......Page 92
2.4.1 Two Intersecting Sets......Page 100
2.4.2 Three Intersecting Sets......Page 103
2.4.3 Any Number of Intersecting Sets......Page 107
2.5 The Twelvefold Way......Page 116
2.6 Notes......Page 119
2.7 Chapter Review......Page 120
2.8 Exercises......Page 121
2.9 Solutions to Exercises......Page 125
2.10 Supplementary Exercises......Page 137
3.1.1 Generalized Binomial Coefficients......Page 142
3.1.2 Formal Power Series......Page 144
3.2.1 Ordinary Generating Functions......Page 147
3.2.2 Exponential Generating Functions......Page 155
3.3 Products of Generating Functions......Page 158
3.3.1 Ordinary Generating Functions......Page 159
3.3.2 Exponential Generating Functions......Page 171
3.4.1 Ordinary Generating Functions......Page 177
3.4.2 Exponential Generating Functions......Page 182
3.5 Excursion: A Different Type of Generating Function......Page 190
3.6 Notes......Page 191
3.7 Chapter Review......Page 192
3.8 Exercises......Page 193
3.9 Solutions to Exercises......Page 196
3.10 Supplementary Exercises......Page 207
II What: Topics......Page 210
4.1 Eulerian Numbers......Page 212
4.2.1 Stirling Numbers of the First Kind......Page 221
4.2.2 Permutations of a Given Type......Page 229
4.3 Cycle Structure and Exponential Generating Functions . .......Page 234
4.4 Inversions......Page 239
4.4.1 Counting Permutations with Respect to Inversions......Page 244
4.5 Notes......Page 249
4.6 Chapter Review......Page 250
4.7 Exercises......Page 251
4.8 Solutions to Exercises......Page 256
4.9 Supplementary Exercises......Page 268
5 Counting Graphs......Page 272
5.1.1 Counting Trees......Page 275
5.2 The Notion of Graph Isomorphisms......Page 277
5.3 Counting Trees on Labeled Vertices......Page 282
5.3.1 Counting Forests......Page 291
5.4.1 Acyclic Functions......Page 295
5.4.2 Parking Functions......Page 296
5.5.1 Rooted Plane Trees......Page 300
5.5.2 Binary Plane Trees......Page 305
5.6 Excursion: Graphs on Colored Vertices......Page 309
5.6.1 Chromatic Polynomials......Page 311
5.6.2 Counting /c-colored Graphs......Page 318
5.7.1 Generating Functions of Trees......Page 322
5.7.2 Counting Connected Graphs......Page 323
5.7.3 Counting Eulerian Graphs......Page 324
5.8 Notes......Page 328
5.9 Chapter Review......Page 330
5.10 Exercises......Page 331
5.11 Solutions to Exercises......Page 336
5.12 Supplementary Exercises......Page 347
6.1.1 Bipartite Graphs......Page 352
6.1.2 Turan's Theorem......Page 357
6.1.3 Graphs Excluding Cycles......Page 361
6.1.4 Graphs Excluding Complete Bipartite Graphs......Page 371
6.2 Hypergraphs......Page 373
6.2.1 Hypergraphs with Pairwise Intersecting Edges . .......Page 374
6.2.2 Hypergraphs with Pairwise Incomparable Edges......Page 381
6.3 Something Is More Than Nothing: Existence Proofs......Page 383
6.3.1 Property В......Page 384
6.3.2 Excluding Monochromatic Arithmetic Progressions......Page 385
6.3.3 Codes Over Finite Alphabets......Page 386
6.4 Notes......Page 390
6.5 Chapter Review......Page 391
6.6 Exercises......Page 392
6.7 Solutions to Exercises......Page 398
6.8 Supplementary Exercises......Page 410
III What Else: Special Topics......Page 414
7.1 Hypergraphs with Symmetries......Page 416
7.2 Finite Projective Planes......Page 423
7.2.1 Excursion: Finite Projective Planes of Prime Power Order......Page 426
7.3.1 Words Far Apart......Page 428
7.3.2 Codes from Hypergraphs......Page 431
7.3.3 Perfect Codes......Page 432
7.4 Counting Symmetric Structures......Page 435
7.5 Notes......Page 444
7.6 Chapter Review......Page 445
7.7 Exercises......Page 446
7.8 Solutions to Exercises......Page 447
7.9 Supplementary Exercises......Page 452
8.1 Unimodality......Page 456
8.2.1 Log-Concavity Implies Unimodality......Page 459
8.2.2 The Product Property......Page 462
8.2.3 Injective Proofs......Page 464
8.3 The Real Zeros Property......Page 470
8.4 Notes......Page 474
8.6 Exercises......Page 475
8.7 Solutions to Exercises......Page 477
8.8 Supplementary Exercises......Page 483
9.1 An Interesting Distribution Problem......Page 486
9.2 Magic Squares of Fixed Size......Page 487
9.2.1 The Case of n = 3......Page 488
9.2.2 The Function tfn(r) for Fixed η......Page 491
9.3 Magic Squares of Fixed Line Sum......Page 502
9.4 Why Magic Cubes Are Different......Page 507
9.5 Notes......Page 510
9.6 Chapter Review......Page 512
9.7 Exercises......Page 513
9.8 Solutions to Exercises......Page 516
9.9 Supplementary Exercises......Page 526
A.l Weak Induction......Page 528
A.2 Strong Induction......Page 530
Bibliography......Page 532
Index......Page 538
Frequently Used Notation......Page 542