Softcover ISBN:  9781470459956 
Product Code:  AMSTEXT/49 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $68.00 
eBook ISBN:  9781470462628 
Product Code:  AMSTEXT/49.E 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $68.00 
Softcover ISBN:  9781470459956 
eBook: ISBN:  9781470462628 
Product Code:  AMSTEXT/49.B 
List Price:  $170.00 $127.50 
MAA Member Price:  $153.00 $114.75 
AMS Member Price:  $136.00 $102.00 
Softcover ISBN:  9781470459956 
Product Code:  AMSTEXT/49 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $68.00 
eBook ISBN:  9781470462628 
Product Code:  AMSTEXT/49.E 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $68.00 
Softcover ISBN:  9781470459956 
eBook ISBN:  9781470462628 
Product Code:  AMSTEXT/49.B 
List Price:  $170.00 $127.50 
MAA Member Price:  $153.00 $114.75 
AMS Member Price:  $136.00 $102.00 

Book DetailsPure and Applied Undergraduate TextsVolume: 49; 2020; 272 ppMSC: Primary 05; 06; 11
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 welldesigned exercises ranging in difficulty from straightforward to challenging. There are also sixteen largescale honors projects on special topics appearing throughout the text. The author is a distinguished combinatorialist and awardwinning 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.
ReadershipUndergraduate and graduate students interested in combinatorics.

Table of Contents

Cover

Title page

Copyright

Contents

Preface

Notation

Chapter 1. Prologue: Compositions of an integer

1.1. Counting compositions

1.2. The Fibonacci numbers from a combinatorial perspective

1.3. Weak compositions

1.4. Compositions with arbitrarily restricted parts

1.5. The fundamental theorem of composition enumeration

1.6. Basic tools for manipulating finite sums

Exercises

Chapter 2. Sets, functions, and relations

2.0. Notation and terminology

2.1. Functions

2.2. Finite sets

2.3. Cartesian products and their subsets

2.4. Counting surjections: A recursive formula

2.5. The domain partition induced by a function

2.6. The pigeonhole principle for functions

2.7. Relations

2.8. The matrix representation of a relation

2.9. Equivalence relations and partitions

References

Exercises

Project

2.A

Chapter 3. Binomial coefficients

3.1. Subsets of a finite set

3.2. Distributions, words, and lattice paths

3.3. Binomial inversion and the sieve formula

3.4. Problème des ménages

3.5. An inversion formula for set functions

3.6. *The Bonferroni inequalities

References

Exercises

Chapter 4. Multinomial coefficients and ordered partitions

4.1. Multinomial coefficients and ordered partitions

4.2. Ordered partitions and preferential rankings

4.3. Generating functions for ordered partitions

Reference

Exercises

Chapter 5. Graphs and trees

5.1. Graphs

5.2. Connected graphs

5.3. Trees

5.4. *Spanning trees

5.5. *Ramsey theory

5.6. *The probabilistic method

References

Exercises

Project

5.A

Chapter 6. Partitions: Stirling, Lah, and cycle numbers

6.1. Stirling numbers of the second kind

6.2. Restricted growth functions

6.3. The numbers 𝜎(𝑛,𝑘) and 𝑆(𝑛,𝑘) as connection constants

6.4. Stirling numbers of the first kind

6.5. Ordered occupancy: Lah numbers

6.6. Restricted ordered occupancy: Cycle numbers

6.7. Balls and boxes: The twentyfold way

References

Exercises

Projects

6.A

6.B

Chapter 7. Intermission: Some unifying themes

7.1. The exponential formula

7.2. Comtet’s theorem

7.3. Lancaster’s theorem

References

Exercises

Project

7.A

Chapter 8. Combinatorics and number theory

8.1. Arithmetic functions

8.2. Circular words

8.3. Partitions of an integer

8.4. *Power sums

8.5. 𝑝orders and Legendre’s theorem

8.6. Lucas’s congruence for binomial coefficients

8.7. *Restricted sums of binomial coefficients

References

Exercises

Project

8.A

Chapter 9. Differences and sums

9.1. Finite difference operators

9.2. Polynomial interpolation

9.3. The fundamental theorem of the finite difference calculus

9.4. The snake oil method

9.5. * The harmonic numbers

9.6. Linear homogeneous difference equations with constant coefficients

9.7. Constructing visibly realvalued solutions to difference equations with obviously realvalued solutions

9.8. The fundamental theorem of rational generating functions

9.9. Inefficient recursive formulae

9.10. Periodic functions and polynomial functions

9.11. A nonlinear recursive formula: The Catalan numbers

References

Exercises

Project

9.A

Chapter 10. Enumeration under group action

10.1. Permutation groups and orbits

10.2. Pólya’s first theorem

10.3. The pattern inventory: Pólya’s second theorem

10.4. Counting isomorphism classes of graphs

10.5. 𝐺classes of proper subsets of colorings / group actions

10.6. De Bruijn’s generalization of Pólya theory

10.7. Equivalence classes of boolean functions

References

Exercises

Chapter 11. Finite vector spaces

11.1. Vector spaces over finite fields

11.2. Linear spans and linear independence

11.3. Counting subspaces

11.4. The 𝑞binomial coefficients are Comtet numbers

11.5. 𝑞binomial inversion

11.6. The 𝑞Vandermonde identity

11.7. 𝑞multinomial coefficients of the first kind

11.8. 𝑞multinomial coefficients of the second kind

11.9. The distribution polynomials of statistics on discrete structures

11.10. Knuth’s analysis

11.11. The Galois numbers

References

Exercises

Projects

11.A

11.B

Chapter 12. Ordered sets

12.1. Total orders and their generalizations

12.2. *Quasiorders and topologies

12.3. *Weak orders and ordered partitions

12.4. *Strict orders

12.5. Partial orders: basic terminology and notation

12.6. Chains and antichains

12.7. Matchings and systems of distinct representatives

12.8. *Unimodality and logarithmic concavity

12.9. Rank functions and Sperner posets

12.10. Lattices

References

Exercises

Projects

12.A

12.B

12.C

12.D

Chapter 13. Formal power series

13.1. Semigroup algebras

13.2. The Cauchy algebra

13.3. Formal power series and polynomials over ℂ

13.4. Infinite sums in ℂ^{ℕ}

13.5. Summation interchange

13.6. Formal derivatives

13.7. The formal logarithm

13.8. The formal exponential function

References

Exercises

Projects

13.A

13.B

13.C

Chapter 14. Incidence algebra: The grand unified theory of enumerative combinatorics

14.1. The incidence algebra of a locally finite poset

14.2. Infinite sums in ℂ^{Int (ℙ)}

14.3. The zeta function and the enumeration of chains

14.4. The chi function and the enumeration of maximal chains

14.5. The Möbius function

14.6. Möbius inversion formulas

14.7. The Möbius functions of four classical posets

14.8. Graded posets and the Jordan–Dedekind chain condition

14.9. Binomial posets

14.10. The reduced incidence algebra of a binomial poset

14.11. Modular binomial lattices

References

Exercises

Projects

14.A

14.B

Appendix A. Analysis review

A.1. Infinite series

A.2. Power series

A.3. Double sequences and series

References

Appendix B. Topology review

B.1. Topological spaces and their bases

B.2. Metric topologies

B.3. Separation axioms

B.4. Product topologies

B.5. The topology of pointwise convergence

References

Appendix C. Abstract algebra review

C.1. Algebraic structures with one composition

C.2. Algebraic structures with two compositions

C.3. 𝑅algebraic structures

C.4. Substructures

C.5. Isomorphic structures

References

Index

Back Cover


Additional Material

RequestsReview Copy – for publishers of book reviewsDesk Copy – for instructors who have adopted an AMS textbook for a courseInstructor's Manual – for instructors who have adopted an AMS textbook for a course and need the instructor's manualExamination Copy – for faculty considering an AMS textbook for a coursePermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Requests
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 welldesigned exercises ranging in difficulty from straightforward to challenging. There are also sixteen largescale honors projects on special topics appearing throughout the text. The author is a distinguished combinatorialist and awardwinning 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.
Undergraduate and graduate students interested in combinatorics.

Cover

Title page

Copyright

Contents

Preface

Notation

Chapter 1. Prologue: Compositions of an integer

1.1. Counting compositions

1.2. The Fibonacci numbers from a combinatorial perspective

1.3. Weak compositions

1.4. Compositions with arbitrarily restricted parts

1.5. The fundamental theorem of composition enumeration

1.6. Basic tools for manipulating finite sums

Exercises

Chapter 2. Sets, functions, and relations

2.0. Notation and terminology

2.1. Functions

2.2. Finite sets

2.3. Cartesian products and their subsets

2.4. Counting surjections: A recursive formula

2.5. The domain partition induced by a function

2.6. The pigeonhole principle for functions

2.7. Relations

2.8. The matrix representation of a relation

2.9. Equivalence relations and partitions

References

Exercises

Project

2.A

Chapter 3. Binomial coefficients

3.1. Subsets of a finite set

3.2. Distributions, words, and lattice paths

3.3. Binomial inversion and the sieve formula

3.4. Problème des ménages

3.5. An inversion formula for set functions

3.6. *The Bonferroni inequalities

References

Exercises

Chapter 4. Multinomial coefficients and ordered partitions

4.1. Multinomial coefficients and ordered partitions

4.2. Ordered partitions and preferential rankings

4.3. Generating functions for ordered partitions

Reference

Exercises

Chapter 5. Graphs and trees

5.1. Graphs

5.2. Connected graphs

5.3. Trees

5.4. *Spanning trees

5.5. *Ramsey theory

5.6. *The probabilistic method

References

Exercises

Project

5.A

Chapter 6. Partitions: Stirling, Lah, and cycle numbers

6.1. Stirling numbers of the second kind

6.2. Restricted growth functions

6.3. The numbers 𝜎(𝑛,𝑘) and 𝑆(𝑛,𝑘) as connection constants

6.4. Stirling numbers of the first kind

6.5. Ordered occupancy: Lah numbers

6.6. Restricted ordered occupancy: Cycle numbers

6.7. Balls and boxes: The twentyfold way

References

Exercises

Projects

6.A

6.B

Chapter 7. Intermission: Some unifying themes

7.1. The exponential formula

7.2. Comtet’s theorem

7.3. Lancaster’s theorem

References

Exercises

Project

7.A

Chapter 8. Combinatorics and number theory

8.1. Arithmetic functions

8.2. Circular words

8.3. Partitions of an integer

8.4. *Power sums

8.5. 𝑝orders and Legendre’s theorem

8.6. Lucas’s congruence for binomial coefficients

8.7. *Restricted sums of binomial coefficients

References

Exercises

Project

8.A

Chapter 9. Differences and sums

9.1. Finite difference operators

9.2. Polynomial interpolation

9.3. The fundamental theorem of the finite difference calculus

9.4. The snake oil method

9.5. * The harmonic numbers

9.6. Linear homogeneous difference equations with constant coefficients

9.7. Constructing visibly realvalued solutions to difference equations with obviously realvalued solutions

9.8. The fundamental theorem of rational generating functions

9.9. Inefficient recursive formulae

9.10. Periodic functions and polynomial functions

9.11. A nonlinear recursive formula: The Catalan numbers

References

Exercises

Project

9.A

Chapter 10. Enumeration under group action

10.1. Permutation groups and orbits

10.2. Pólya’s first theorem

10.3. The pattern inventory: Pólya’s second theorem

10.4. Counting isomorphism classes of graphs

10.5. 𝐺classes of proper subsets of colorings / group actions

10.6. De Bruijn’s generalization of Pólya theory

10.7. Equivalence classes of boolean functions

References

Exercises

Chapter 11. Finite vector spaces

11.1. Vector spaces over finite fields

11.2. Linear spans and linear independence

11.3. Counting subspaces

11.4. The 𝑞binomial coefficients are Comtet numbers

11.5. 𝑞binomial inversion

11.6. The 𝑞Vandermonde identity

11.7. 𝑞multinomial coefficients of the first kind

11.8. 𝑞multinomial coefficients of the second kind

11.9. The distribution polynomials of statistics on discrete structures

11.10. Knuth’s analysis

11.11. The Galois numbers

References

Exercises

Projects

11.A

11.B

Chapter 12. Ordered sets

12.1. Total orders and their generalizations

12.2. *Quasiorders and topologies

12.3. *Weak orders and ordered partitions

12.4. *Strict orders

12.5. Partial orders: basic terminology and notation

12.6. Chains and antichains

12.7. Matchings and systems of distinct representatives

12.8. *Unimodality and logarithmic concavity

12.9. Rank functions and Sperner posets

12.10. Lattices

References

Exercises

Projects

12.A

12.B

12.C

12.D

Chapter 13. Formal power series

13.1. Semigroup algebras

13.2. The Cauchy algebra

13.3. Formal power series and polynomials over ℂ

13.4. Infinite sums in ℂ^{ℕ}

13.5. Summation interchange

13.6. Formal derivatives

13.7. The formal logarithm

13.8. The formal exponential function

References

Exercises

Projects

13.A

13.B

13.C

Chapter 14. Incidence algebra: The grand unified theory of enumerative combinatorics

14.1. The incidence algebra of a locally finite poset

14.2. Infinite sums in ℂ^{Int (ℙ)}

14.3. The zeta function and the enumeration of chains

14.4. The chi function and the enumeration of maximal chains

14.5. The Möbius function

14.6. Möbius inversion formulas

14.7. The Möbius functions of four classical posets

14.8. Graded posets and the Jordan–Dedekind chain condition

14.9. Binomial posets

14.10. The reduced incidence algebra of a binomial poset

14.11. Modular binomial lattices

References

Exercises

Projects

14.A

14.B

Appendix A. Analysis review

A.1. Infinite series

A.2. Power series

A.3. Double sequences and series

References

Appendix B. Topology review

B.1. Topological spaces and their bases

B.2. Metric topologies

B.3. Separation axioms

B.4. Product topologies

B.5. The topology of pointwise convergence

References

Appendix C. Abstract algebra review

C.1. Algebraic structures with one composition

C.2. Algebraic structures with two compositions

C.3. 𝑅algebraic structures

C.4. Substructures

C.5. Isomorphic structures

References

Index

Back Cover