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.
Carl G Wagner, University of Tennessee, Knowxville, TN
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 C 13.4. Infinite sums in C^{N} 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 C^{Int (P)} 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