Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
A First Course in Enumerative Combinatorics
 
Carl G. Wagner University of Tennessee, Knoxville, TN
A First Course in Enumerative Combinatorics
Softcover ISBN:  978-1-4704-5995-6
Product Code:  AMSTEXT/49
List Price: $85.00
MAA Member Price: $76.50
AMS Member Price: $68.00
eBook ISBN:  978-1-4704-6262-8
Product Code:  AMSTEXT/49.E
List Price: $85.00
MAA Member Price: $76.50
AMS Member Price: $68.00
Softcover ISBN:  978-1-4704-5995-6
eBook: ISBN:  978-1-4704-6262-8
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
A First Course in Enumerative Combinatorics
Click above image for expanded view
A First Course in Enumerative Combinatorics
Carl G. Wagner University of Tennessee, Knoxville, TN
Softcover ISBN:  978-1-4704-5995-6
Product Code:  AMSTEXT/49
List Price: $85.00
MAA Member Price: $76.50
AMS Member Price: $68.00
eBook ISBN:  978-1-4704-6262-8
Product Code:  AMSTEXT/49.E
List Price: $85.00
MAA Member Price: $76.50
AMS Member Price: $68.00
Softcover ISBN:  978-1-4704-5995-6
eBook ISBN:  978-1-4704-6262-8
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 Details
     
     
    Pure and Applied Undergraduate Texts
    Volume: 492020; 272 pp
    MSC: 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 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.

    Readership

    Undergraduate 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 twenty-fold 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 real-valued solutions to difference equations with obviously real-valued 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. *Quasi-orders 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
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Desk Copy – for instructors who have adopted an AMS textbook for a course
    Instructor's Manual – for instructors who have adopted an AMS textbook for a course and need the instructor's manual
    Examination Copy – for faculty considering an AMS textbook for a course
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
Volume: 492020; 272 pp
MSC: 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 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.

Readership

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 twenty-fold 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 real-valued solutions to difference equations with obviously real-valued 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. *Quasi-orders 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
Review Copy – for publishers of book reviews
Desk Copy – for instructors who have adopted an AMS textbook for a course
Instructor's Manual – for instructors who have adopted an AMS textbook for a course and need the instructor's manual
Examination Copy – for faculty considering an AMS textbook for a course
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
You may be interested in...
Please select which format for which you are requesting permissions.