Enumerative combinatorics, vol. 1

Cover......Page 1
Enumerative Combinatorics, Volume 1......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
“Yes, wonderful things.”......Page 8
Contents......Page 9
Preface......Page 13
Acknowledgments......Page 15
1.1 How to Count......Page 17
1.2 Sets and Multisets......Page 31
1.3 Cycles and Inversions......Page 38
1.4 Descents......Page 47
1.5 Geometric Representations of Permutations......Page 57
1.6.1 Basic Properties......Page 62
1.6.2 Flip Equivalence of Increasing Binary Trees......Page 65
1.6.3 Min-Max Trees and the cd-Index......Page 66
1.7 Permutations of Multisets......Page 70
1.8 Partition Identities......Page 77
1.9 The Twelvefold Way......Page 87
1.10 Two q-Analogues of Permutations......Page 96
1.10.1 A q-Analogue of Permutations as Bijections......Page 97
1.10.2 A q-Analogue of Permutations as Words......Page 108
1.10.3 The Connection Between the Two q-Analogues......Page 110
Notes......Page 113
Bibliography......Page 116
Exercises for Chapter 1......Page 119
Solutions to Exerrcises......Page 157
2.1 Inclusion-Exclusion......Page 211
2.2 Examples and Special Cases......Page 214
2.3 Permutations with Restricted Position......Page 218
2.4 Ferrers Boards......Page 223
2.5 V-Partitions and Unimodal Sequences......Page 225
2.6 Involutions......Page 228
2.7 Determinants......Page 231
Notes......Page 234
Bibliography......Page 235
Exercises for Chapter 2......Page 236
Solutions Exercises......Page 247
3.1 Basic Concepts......Page 257
3.2 New Posets from Old......Page 262
3.3 Lattices......Page 264
3.4 Distributive Lattices......Page 268
3.5 Chains in Distributive Lattices......Page 272
3.6 Incidence Algebras......Page 277
3.7 The Möbius Inversion Formula......Page 280
3.8 Techniques for Computing Möbius Functions......Page 282
3.9 Lattices and Their Möbius Functions......Page 290
3.10 The Möbius Function of a Semimodular Lattice......Page 293
3.11.1 Basic Definitions......Page 296
3.11.2 The Intersection Poset and Characteristic Polynomial......Page 298
3.11.3 Regions......Page 301
3.11.4 The Finite Field Method......Page 304
3.12 Zeta Polynomials......Page 307
3.13 Rank Selection......Page 309
3.14 R-Labelings......Page 311
3.15.1 The Main Generating Function......Page 314
3.15.2 Specializations......Page 318
3.15.3 Reciprocity......Page 319
3.15.4 Natural Labelings......Page 322
3.16 Eulerian Posets......Page 326
3.17 The cd-Index of an Eulerian Poset......Page 331
3.18 Binomial Posets and Generating Functions......Page 336
3.19 An Application to Permutation Enumeration......Page 343
3.20 Promotion and Evacuation......Page 346
3.21 Differential Posets......Page 350
Notes......Page 361
Bibliography......Page 365
Exercises for Chapter 3......Page 369
Solutions to Exercises......Page 424
4.1 Rational Power Series in One Variable......Page 480
4.2 Further Ramifications......Page 483
4.3 Polynomials......Page 487
4.4 Quasipolynomials......Page 490
4.5 Linear Homogeneous Diophantine Equations......Page 491
4.6.1 Magic Squares......Page 504
4.6.2 The Ehrhart Quasipolynomial of a Rational Polytope......Page 509
4.7.1 Basic Principles......Page 516
4.7.2 Undirected Graphs......Page 518
4.7.3 Simple Applications......Page 519
4.7.4 Factorization in Free Monoids......Page 523
4.7.5 Some Sums Over Compositions......Page 535
Notes......Page 539
Bibliography......Page 542
Exercises for Chapter 4......Page 544
Solutions to Exercises......Page 564
Appendix: Graph Theory Terminology......Page 587
First Edition Numbering......Page 591
List of Notation (Partial)......Page 597
Index......Page 601