**Pure and Applied Undergraduate Texts**

Volume: 49;
2020;
272 pp;
Softcover

MSC: Primary 05; 06; 11;

**Print ISBN: 978-1-4704-5995-6
Product Code: AMSTEXT/49**

List Price: $85.00

AMS Member Price: $68.00

MAA Member Price: $76.50

**Electronic ISBN: 978-1-4704-6262-8
Product Code: AMSTEXT/49.E**

List Price: $85.00

AMS Member Price: $68.00

MAA Member Price: $76.50

#### You may also like

#### Supplemental Materials

# A First Course in Enumerative Combinatorics

Share this page
*Carl G. Wagner*

A First
Course in Enumerative Combinatorics provides an introduction to
the fundamentals of enumeration for advanced undergraduates and
beginning graduate students in the mathematical sciences. The book
offers a careful and comprehensive account of the standard tools of
enumeration—recursion, generating functions, sieve and inversion
formulas, enumeration under group actions—and their application
to counting problems for the fundamental structures of discrete
mathematics, including sets and multisets, words and permutations,
partitions of sets and integers, and graphs and trees. The author's
exposition has been strongly influenced by the work of Rota and
Stanley, highlighting bijective proofs, partially ordered sets, and an
emphasis on organizing the subject under various unifying themes,
including the theory of incidence algebras. In addition, there are
distinctive chapters on the combinatorics of finite vector spaces, a
detailed account of formal power series, and combinatorial number
theory.

The reader is assumed to have a knowledge of basic
linear algebra and some familiarity with power series. There are over
200 well-designed exercises ranging in difficulty from straightforward
to challenging. There are also sixteen large-scale honors projects on
special topics appearing throughout the text. The author is a
distinguished combinatorialist and award-winning teacher, and he is
currently Professor Emeritus of Mathematics and Adjunct Professor of
Philosophy at the University of Tennessee. He has published widely in
number theory, combinatorics, probability, decision theory, and formal
epistemology. His Erdős number is 2.

An instructor's manual for this title is available electronically
to those instructors who have adopted the textbook for classroom use.
Please send email to textbooks@ams.org for more
information.

#### Readership

Undergraduate and graduate students interested in combinatorics.

#### Table of Contents

# Table of Contents

## A First Course in Enumerative Combinatorics

Table of Contents pages: 1 2

- Cover Cover11
- Title page iii5
- Copyright iv6
- Contents vii9
- Preface xiii15
- Notation xvii19
- Chapter 1. Prologue: Compositions of an integer 121
- 1.1. Counting compositions 222
- 1.2. The Fibonacci numbers from a combinatorial perspective 323
- 1.3. Weak compositions 525
- 1.4. Compositions with arbitrarily restricted parts 525
- 1.5. The fundamental theorem of composition enumeration 626
- 1.6. Basic tools for manipulating finite sums 727
- Exercises 828

- Chapter 2. Sets, functions, and relations 1131
- 2.0. Notation and terminology 1131
- 2.1. Functions 1232
- 2.2. Finite sets 1636
- 2.3. Cartesian products and their subsets 1939
- 2.4. Counting surjections: A recursive formula 2141
- 2.5. The domain partition induced by a function 2242
- 2.6. The pigeonhole principle for functions 2444
- 2.7. Relations 2545
- 2.8. The matrix representation of a relation 2747
- 2.9. Equivalence relations and partitions 2747
- References 2747
- Exercises 2848
- Project 3050
- 2.A 3050

- Chapter 3. Binomial coefficients 3151
- Chapter 4. Multinomial coefficients and ordered partitions 4969
- Chapter 5. Graphs and trees 5777
- Chapter 6. Partitions: Stirling, Lah, and cycle numbers 6989
- 6.1. Stirling numbers of the second kind 6989
- 6.2. Restricted growth functions 7292
- 6.3. The numbers 𝜎(𝑛,𝑘) and 𝑆(𝑛,𝑘) as connection constants 7393
- 6.4. Stirling numbers of the first kind 7595
- 6.5. Ordered occupancy: Lah numbers 7696
- 6.6. Restricted ordered occupancy: Cycle numbers 7898
- 6.7. Balls and boxes: The twenty-fold way 82102
- References 82102
- Exercises 83103
- Projects 85105
- 6.A 85105
- 6.B 85105

- Chapter 7. Intermission: Some unifying themes 87107
- Chapter 8. Combinatorics and number theory 97117
- 8.1. Arithmetic functions 97117
- 8.2. Circular words 100120
- 8.3. Partitions of an integer 101121
- 8.4. *Power sums 109129
- 8.5. 𝑝-orders and Legendre’s theorem 112132
- 8.6. Lucas’s congruence for binomial coefficients 114134
- 8.7. *Restricted sums of binomial coefficients 115135
- References 116136
- Exercises 117137
- Project 118138
- 8.A 118138

- Chapter 9. Differences and sums 119139
- 9.1. Finite difference operators 119139
- 9.2. Polynomial interpolation 121141
- 9.3. The fundamental theorem of the finite difference calculus 122142
- 9.4. The snake oil method 123143
- 9.5. * The harmonic numbers 126146
- 9.6. Linear homogeneous difference equations with constant coefficients 127147
- 9.7. Constructing visibly real-valued solutions to difference equations with obviously real-valued solutions 131151
- 9.8. The fundamental theorem of rational generating functions 132152
- 9.9. Inefficient recursive formulae 134154
- 9.10. Periodic functions and polynomial functions 135155
- 9.11. A nonlinear recursive formula: The Catalan numbers 136156
- References 139159
- Exercises 140160
- Project 141161
- 9.A 141161

- Chapter 10. Enumeration under group action 143163
- 10.1. Permutation groups and orbits 143163
- 10.2. Pólya’s first theorem 145165
- 10.3. The pattern inventory: Pólya’s second theorem 148168
- 10.4. Counting isomorphism classes of graphs 150170
- 10.5. 𝐺-classes of proper subsets of colorings / group actions 154174
- 10.6. De Bruijn’s generalization of Pólya theory 155175
- 10.7. Equivalence classes of boolean functions 157177
- References 159179
- Exercises 160180

- Chapter 11. Finite vector spaces 163183
- 11.1. Vector spaces over finite fields 163183
- 11.2. Linear spans and linear independence 164184
- 11.3. Counting subspaces 165185
- 11.4. The 𝑞-binomial coefficients are Comtet numbers 167187
- 11.5. 𝑞-binomial inversion 169189
- 11.6. The 𝑞-Vandermonde identity 171191
- 11.7. 𝑞-multinomial coefficients of the first kind 172192
- 11.8. 𝑞-multinomial coefficients of the second kind 173193
- 11.9. The distribution polynomials of statistics on discrete structures 175195
- 11.10. Knuth’s analysis 180200
- 11.11. The Galois numbers 182202
- References 183203
- Exercises 184204
- Projects 185205
- 11.A 185205
- 11.B 185205

- Chapter 12. Ordered sets 187207
- 12.1. Total orders and their generalizations 187207
- 12.2. *Quasi-orders and topologies 188208
- 12.3. *Weak orders and ordered partitions 189209
- 12.4. *Strict orders 191211
- 12.5. Partial orders: basic terminology and notation 192212
- 12.6. Chains and antichains 194214
- 12.7. Matchings and systems of distinct representatives 198218
- 12.8. *Unimodality and logarithmic concavity 200220
- 12.9. Rank functions and Sperner posets 203223
- 12.10. Lattices 203223
- References 205225
- Exercises 206226
- Projects 207227
- 12.A 207227
- 12.B 207227
- 12.C 207227
- 12.D 207227

- Chapter 13. Formal power series 209229
- 13.1. Semigroup algebras 209229
- 13.2. The Cauchy algebra 210230
- 13.3. Formal power series and polynomials over ℂ 211231
- 13.4. Infinite sums in ℂ^{ℕ} 215235
- 13.5. Summation interchange 217237
- 13.6. Formal derivatives 219239
- 13.7. The formal logarithm 221241
- 13.8. The formal exponential function 222242
- References 223243
- Exercises 223243
- Projects 224244
- 13.A 224244
- 13.B 224244
- 13.C 224244

- Chapter 14. Incidence algebra: The grand unified theory of enumerative combinatorics 227247
- 14.1. The incidence algebra of a locally finite poset 227247
- 14.2. Infinite sums in ℂ^{Int (ℙ)} 229249
- 14.3. The zeta function and the enumeration of chains 231251
- 14.4. The chi function and the enumeration of maximal chains 232252
- 14.5. The Möbius function 233253
- 14.6. Möbius inversion formulas 235255
- 14.7. The Möbius functions of four classical posets 237257
- 14.8. Graded posets and the Jordan–Dedekind chain condition 239259
- 14.9. Binomial posets 240260
- 14.10. The reduced incidence algebra of a binomial poset 243263
- 14.11. Modular binomial lattices 247267
- References 249269
- Exercises 249269
- Projects 250270
- 14.A 250270
- 14.B 250270

- Appendix A. Analysis review 251271
- Appendix B. Topology review 255275
- Appendix C. Abstract algebra review 261281

Table of Contents pages: 1 2