**Graduate Studies in Mathematics**

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 page
*Bruce 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