Volume: 210; 2020; 304 pp; Softcover
MSC: Primary 05; Secondary 06
Print ISBN: 978-1-4704-6032-7
Product Code: GSM/210
List Price: $89.00
AMS Member Price: $71.20
MAA Member Price: $80.10
Electronic ISBN: 978-1-4704-6280-2
Product Code: GSM/210.E
List Price: $89.00
AMS Member Price: $71.20
MAA Member Price: $80.10
You may also like
Supplemental Materials
Combinatorics: The Art of Counting
Share this pageBruce E. Sagan
This book is a gentle introduction to the enumerative part of
combinatorics suitable for study at the advanced undergraduate or
beginning graduate level. In addition to covering all the standard
techniques for counting combinatorial objects, the text contains
material from the research literature which has never before appeared
in print, such as the use of quotient posets to study the Möbius
function and characteristic polynomial of a partially ordered set, or
the connection between quasisymmetric functions and pattern
avoidance.
The book assumes minimal background, and a first course in abstract
algebra should suffice. The exposition is very reader friendly:
keeping a moderate pace, using lots of examples, emphasizing recurring
themes, and frankly expressing the delight the author takes in
mathematics in general and combinatorics in particular.
Readership
Undergraduate and graduate students interested in combinatorics.
Table of Contents
Table of Contents
Combinatorics: The Art of Counting
- Cover Cover11
- Title page iii5
- Copyright iv6
- Contents vii9
- Preface xi13
- List of Notation xiii15
- Chapter 1. Basic Counting 123
- 1.1. The Sum and Product Rules for sets 123
- 1.2. Permutations and words 426
- 1.3. Combinations and subsets 527
- 1.4. Set partitions 1032
- 1.5. Permutations by cycle structure 1133
- 1.6. Integer partitions 1335
- 1.7. Compositions 1638
- 1.8. The twelvefold way 1739
- 1.9. Graphs and digraphs 1840
- 1.10. Trees 2244
- 1.11. Lattice paths 2547
- 1.12. Pattern avoidance 2850
- Exercises 3355
- Chapter 2. Counting with Signs 4163
- Chapter 3. Counting with Ordinary Generating Functions 7193
- 3.1. Generating polynomials 7193
- 3.2. Statistics and 𝑞-analogues 7496
- 3.3. The algebra of formal power series 81103
- 3.4. The Sum and Product Rules for ogfs 86108
- 3.5. Revisiting integer partitions 89111
- 3.6. Recurrence relations and generating functions 92114
- 3.7. Rational generating functions and linear recursions 96118
- 3.8. Chromatic polynomials 99121
- 3.9. Combinatorial reciprocity 106128
- Exercises 109131
- Chapter 4. Counting with Exponential Generating Functions 117139
- Chapter 5. Counting with Partially Ordered Sets 139161
- 5.1. Basic properties of partially ordered sets 139161
- 5.2. Chains, antichains, and operations on posets 145167
- 5.3. Lattices 148170
- 5.4. The Möbius function of a poset 154176
- 5.5. The Möbius Inversion Theorem 157179
- 5.6. Characteristic polynomials 164186
- 5.7. Quotients of posets 168190
- 5.8. Computing the Möbius function 174196
- 5.9. Binomial posets 178200
- Exercises 183205
- Chapter 6. Counting with Group Actions 189211
- Chapter 7. Counting with Symmetric Functions 219241
- 7.1. The algebra of symmetric functions, Sym 219241
- 7.2. The Schur basis of Sym 224246
- 7.3. Hooklengths 230252
- 7.4. 𝑃-partitions 235257
- 7.5. The Robinson–Schensted–Knuth correspondence 240262
- 7.6. Longest increasing and decreasing subsequences 244266
- 7.7. Differential posets 248270
- 7.8. The chromatic symmetric function 253275
- 7.9. Cyclic sieving redux 256278
- Exercises 259281
- Chapter 8. Counting with Quasisymmetric Functions 267289
- Appendix. Introduction to Representation Theory 287309
- Bibliography 293315
- Index 297319
- Back Cover Back Cover1328