Preface ...................................................... xiii
Epigraph ....................................................... xv
Introduction ................................................. xvii
1 Basic Counting ............................................... 1
1.1 Review of Set Theory .................................... 1
1.2 Sum Rule ................................................ 2
1.3 Product Rule ............................................ 3
1.4 Words, Permutations, and Subsets ........................ 4
1.5 Functions ............................................... 6
1.6 Bijections, Cardinality, and Counting ................... 9
1.7 Subsets, Binary Words, and Compositions ................ 11
1.8 Subsets of a Fixed Size ................................ 12
1.9 Anagrams ............................................... 14
1.10 Lattice Paths .......................................... 16
1.11 Multisets .............................................. 19
1.12 Probability ............................................ 21
1.13 Games of Chance ........................................ 24
1.14 Conditional Probability and Independence ............... 29
Summary ..................................................... 32
Exercises ................................................... 33
2 Combinatorial Identities and Recursions ..................... 41
2.1 Generalized Distributive Law ........................... 41
2.2 Multinomial and Binomial Theorems ...................... 44
2.3 Combinatorial Proofs ................................... 47
2.4 Recursions ............................................. 51
2.5 Recursions for Multisets and Anagrams .................. 55
2.6 Recursions for Lattice Paths ........................... 57
2.7 Catalan Recursions ..................................... 61
2.8 Integer Partitions ..................................... 65
2.9 Set Partitions ......................................... 71
2.10 Surjections ............................................ 74
2.11 Stirling Numbers and Rook Theory ....................... 75
2.12 Linear Algebra Review .................................. 79
2.13 Stirling Numbers and Polynomials ....................... 80
2.14 Combinatorial Proofs of Polynomial Identities .......... 84
Summary ..................................................... 86
Exercises ................................................... 89
3 Counting Problems in Graph Theory ........................... 97
3.1 Graphs and Digraphs .................................... 97
3.2 Walks and Matrices ..................................... 99
3.3 DAGs and Nilpotent Matrices ........................... 102
3.4 Vertex Degrees ........................................ 105
3.5 Functional Digraphs ................................... 107
3.6 Cycle Structure of Permutations ....................... 109
3.7 Counting Rooted Trees ................................. 111
3.8 Connectedness and Components .......................... 113
3.9 Forests ............................................... 116
3.10 Trees ................................................. 117
3.11 Counting Trees ........................................ 119
3.12 Pruning Maps .......................................... 121
3.13 Ordered Trees and Terms ............................... 123
3.14 Ordered Forests and Lists of Terms .................... 125
3.15 Graph Coloring ........................................ 127
3.16 Spanning Trees ........................................ 131
3.17 Matrix-Tree Theorem ................................... 134
3.18 Eulerian Tours ........................................ 137
Summary .................................................... 140
Exercises .................................................. 143
4 Inclusion-Exclusion and Related Techniques ................. 153
4.1 Involutions ........................................... 153
4.2 The Inclusion-Exclusion Formula ....................... 156
4.3 More Proofs of Inclusion-Exclusion .................... 158
4.4 Applications of the Inclusion-Exclusion Formula ....... 160
4.5 Derangements .......................................... 163
4.6 Coefficients of Chromatic Polynomials ................. 165
4.7 Classical Möbius Inversion ............................ 165
4.8 Partially Ordered Sets ................................ 168
4.9 Möbius Inversion for Posets ........................... 169
4.10 Product Posets ........................................ 172
Summary .................................................... 173
Exercises .................................................. 175
5 Ranking and Unranking ...................................... 181
5.1 Ranking, Unranking, and Related Problems .............. 181
5.2 Bijective Sum Rule .................................... 182
5.3 Bijective Product Rule ................................ 183
5.4 Ranking Words ......................................... 187
5.5 Ranking Permutations .................................. 189
5.6 Ranking Subsets ....................................... 190
5.7 Ranking Anagrams ...................................... 192
5.8 Ranking Integer Partitions ............................ 193
5.9 Ranking Set Partitions ................................ 194
5.10 Ranking Card Hands .................................... 196
5.11 Ranking Dyck Paths .................................... 199
5.12 Ranking Trees ......................................... 201
5.13 Successors and Predecessors ........................... 201
5.14 Random Selection ...................................... 203
Summary .................................................... 205
Exercises .................................................. 206
6 Counting Weighted Objects .................................. 213
6.1 Weighted Sets ......................................... 213
6.2 Inversions ............................................ 216
6.3 Weight-Preserving Bijections .......................... 217
6.4 Sum and Product Rules for Weighted Sets ............... 218
6.5 Inversions and Quantum Factorials ..................... 220
6.6 Descents and Major Index .............................. 221
6.7 Quantum Binomial Coefficients ......................... 223
6.8 Quantum Multinomial Coefficients ...................... 227
6.9 Foata's Map ........................................... 230
6.10 Quantum Catalan Numbers ............................... 233
Summary .................................................... 235
Exercises .................................................. 237
7 Formal Power Series ........................................ 243
7.1 The Ring of Formal Power Series ....................... 244
7.2 Finite Products and Powers of Formal Series ........... 247
7.3 Formal Polynomials .................................... 248
7.4 Order of Formal Power Series .......................... 251
7.5 Formal Limits, Infinite Sums, and Infinite Products ... 252
7.6 Multiplicative Inverses in K[x] and K[[x]] ............ 255
7.7 Formal Laurent Series ................................. 257
7.8 Formal Derivatives .................................... 259
7.9 Composition of Polynomials ............................ 261
7.10 Composition of Formal Power Series .................... 262
7.11 Generalized Binomial Expansion ........................ 265
7.12 Generalized Powers of Formal Series ................... 268
7.13 Partial Fraction Expansions ........................... 270
7.14 Application to Recursions ............................. 274
7.15 Formal Exponentiation and Formal Logarithms ........... 277
7.16 Multivariable Polynomials and Formal Series .......... 279
Summary .................................................... 281
Exercises .................................................. 284
8 The Combinatorics of Formal Power Series ................... 291
8.1 Sum Rule for Infinite Weighted Sets ................... 291
8.2 Product Rule for Infinite Weighted Sets ............... 292
8.3 Generating Functions for Trees ........................ 294
8.4 Compositional Inversion Formulas ...................... 296
8.5 Generating Functions for Partitions ................... 298
8.6 Partition Bijections .................................. 300
8.7 Euler's Pentagonal Number Theorem ..................... 303
8.8 Stirling Numbers of the First Kind .................... 306
8.9 Stirling Numbers of the Second Kind ................... 307
8.10 The Exponential Formula .............................. 309
Summary .................................................... 311
Exercises .................................................. 313
9 Permutations and Group Actions ............................. 319
9.1 Definition and Examples of Groups ..................... 319
9.2 Basic Properties of Groups ............................ 321
9.3 Notation for Permutations ............................. 322
9.4 Inversions and Sign ................................... 325
9.5 Determinants .......................................... 329
9.6 Multilinearity and Laplace Expansions ................. 331
9.7 Cauchy-Binet Formula .................................. 334
9.8 Subgroups ............................................. 336
9.9 Automorphism Groups of Graphs ......................... 338
9.10 Group Homomorphisms ................................... 341
9.11 Group Actions ......................................... 344
9.12 Permutation Representations ........................... 347
9.13 Stable Subsets and Orbits ............................. 349
9.14 Cosets ................................................ 351
9.15 The Size of an Orbit .................................. 354
9.16 Conjugacy Classes in Sn ............................... 356
9.17 Applications of the Orbit Size Formula ................ 357
9.18 The Number of Orbits .................................. 359
9.19 Polya's Formula ....................................... 362
Summary .................................................... 364
Exercises .................................................. 367
10 Tableaux and Symmetric Polynomials ......................... 377
10.1 Partition Diagrams and Skew Shapes .................... 377
10.2 Tableaux .............................................. 379
10.3 Schur Polynomials ..................................... 380
10.4 Symmetric Polynomials ................................. 383
10.5 Homogeneous Symmetric Polynomials ..................... 385
10.6 Symmetry of Schur Polynomials ......................... 387
10.7 Orderings on Partitions ............................... 389
10.8 Schur Bases ........................................... 392
10.9 Tableau Insertion ..................................... 394
10.10 Reverse Insertion .................................... 397
10.11 Bumping Comparison Theorem ........................... 399
10.12 Pieri Rules .......................................... 401
10.13 Schur Expansion of hα ................................ 403
10.14 Schur Expansion of eα ................................ 406
10.15 Algebraic Independence ............................... 407
10.16 Power-Sum Symmetric Polynomials ...................... 408
10.17 Relations between e's and h's ........................ 410
10.18 Generating Functions for e's and h's ................. 411
10.19 Relations between p's, e's, and h's .................. 413
10.20 Power-Sum Expansion of hn and en ..................... 414
10.21 The Involution ω ..................................... 417
10.22 Permutations and Tableaux ............................ 419
10.23 Words and Tableaux ................................... 424
10.24 Matrices and Tableaux ................................ 427
10.25 Cauchy Identities .................................... 429
10.26 Dual Bases ........................................... 431
Summary .................................................... 433
Exercises .................................................. 436
11 Abaci and Antisymmetric Polynomials ........................ 445
11.1 Abaci and Integer Partitions .......................... 445
11.2 Jacobi Triple Product Identity ........................ 447
11.3 Ribbons and k-Cores ................................... 448
11.4 k-Quotients and Hooks ................................. 454
11.5 Antisymmetric Polynomials ............................. 457
11.6 Labeled Abaci ......................................... 460
11.7 Pieri Rule for pk ..................................... 462
11.8 Pieri Rule for ek ..................................... 465
11.9 Pieri Rule for hk ..................................... 467
11.10 Antisymmetric Polynomials and Schur Polynomials ...... 469
11.11 Rim-Hook Tableaux .................................... 470
11.12 Abaci and Tableaux ................................... 474
11.13 Skew Schur Polynomials ............................... 477
11.14 Jacobi-Trudi Formulas ................................ 478
11.15 Inverse Kostka Matrix ................................ 482
11.16 Schur Expansion of Skew Schur Polynomials ............ 485
11.17 Products of Schur Polynomials ........................ 489
Summary .................................................... 491
Exercises .................................................. 493
12 Additional Topics .......................................... 497
12.1 Cyclic Shifting of Paths .............................. 497
12.2 Chung-Feller Theorem .................................. 499
12.3 Rook-Equivalence of Ferrers Boards .................... 503
12.4 Parking Functions ..................................... 505
12.5 Parking Functions and Trees ........................... 507
12.6 Möbius Inversion and Field Theory ..................... 511
12.7 Quantum Binomial Coefficients and Subspaces ........... 513
12.8 Tangent and Secant Numbers ............................ 517
12.9 Tournaments and the Vandermonde Determinant ........... 520
12.10 Hook-Length Formula .................................. 523
12.11 Knuth Equivalence .................................... 527
12.12 Pfaffians and Perfect Matchings ...................... 533
12.13 Domino Tilings of Rectangles ......................... 539
Summary .................................................... 545
Exercises .................................................. 547
Answers and Hints to Selected Exercises ....................... 555
Bibliography .................................................. 569
Index ......................................................... 577
|
