Introduction to Enumerative and Analytic Combinatorics (Discrete Mathematics and Its Applications)

Cover
	Half Title
Series Page
Title Page
Copyright Page
Dedication
Contents
Foreword to the first edition
Preface to the third edition
Acknowledgments
Frequently used notation
I. Methods
	1. Basicmethods
		1.1. When we add and when we subtract
			1.1.1. When we add
			1.1.2. When we subtract
			Quick Check
		1.2. When we multiply
			1.2.1. The product principle
			1.2.2. Using several counting principles
			1.2.3. When repetitions are not allowed
			Quick Check
		1.3. When we divide
			1.3.1. The division principle
			1.3.2. Subsets
			Quick Check
		1.4. Applications of basic counting principles
			1.4.1. Bijective proofs
			1.4.2. Properties of binomial coefficients
			1.4.3. Permutations with repetition
			Quick Check
		1.5. The pigeonhole principle
			Quick Check
		1.6. Notes
		1.7. Chapter review
		1.8. Exercises
		1.9. Solutions to exercises
		1.10. Supplementary exercises
	2. Applications of basic methods
		2.1. Multisets and compositions
			2.1.1. Weak compositions
			2.1.2. Compositions
			Quick Check
		2.2. Set partitions
			2.2.1. Stirling numbers of the second kind
			2.2.2. Recurrence relations for Stirling numbers of the second kind
			2.2.3. When the number of blocks is not fixed
			Quick Check
		2.3. Partitions of integers
			2.3.1. Nonincreasing finite sequences of positive integers
			2.3.2. Ferrers shapes and their applications
			2.3.3. Excursion: Euler’s pentagonal number theorem
			Quick Check
		2.4. The inclusion–exclusion principle
			2.4.1. Two intersecting sets
			2.4.2. Three intersecting sets
			2.4.3. Any number of intersecting sets
			Quick Check
		2.5. The twelvefold way
			Quick Check
		2.6. Notes
		2.7. Chapter review
		2.8. Exercises
		2.9. Solutions to exercises
		2.10. Supplementary exercises
	3. Generating functions
		3.1. Power series
			3.1.1. Generalized binomial coefficients
			3.1.2. Formal power series
			Quick Check
		3.2. Warming up: Solving recurrence relations
			3.2.1. Ordinary generating functions
			3.2.2. Exponential generating functions
			Quick Check
		3.3. Products of generating functions
			3.3.1. Ordinary generating functions
			3.3.2. Exponential generating functions
			Quick Check
		3.4. Compositions of generating functions
			3.4.1. Ordinary generating functions
			3.4.2. Exponential generating functions
			Quick Check
		3.5. A different type of generating functions
			Quick Check
		3.6. Notes
		3.7. Chapter review
		3.8. Exercises
		3.9. Solutions to exercises
		3.10. Supplementary exercises
II. Topics
	4. Counting permutations
		4.1. Eulerian numbers
			Quick Check
		4.2. The cycle structure of permutations
			4.2.1. Stirling numbers of the first kind
			4.2.2. Permutations of a given type
			Quick Check
		4.3. Cycle structure and exponential generating functions
			Quick Check
		4.4. Inversions
			4.4.1. Counting permutations with respect to inversions
			Quick Check
		4.5. Advanced applications of generating functions to permutation enumeration
			4.5.1. The combinatorial meaning of the derivative
			4.5.2. Multivariate generating functions
			Quick Check
		4.6. Notes
		4.7. Chapter review
		4.8. Exercises
		4.9. Solutions to exercises
		4.10. Supplementary exercises
	5. Counting graphs
		5.1. Trees and forests
			5.1.1. Trees
			5.1.2. The notion of graph isomorphisms
			5.1.3. Counting trees on labeled vertices
			5.1.4. Forests
			Quick Check
		5.2. Graphs and functions
			5.2.1. Acyclic functions
			5.2.2. Parking functions
			Quick Check
		5.3. When the vertices are not freely labeled
			5.3.1. Rooted plane trees
			5.3.2. Decreasing binary trees
			Quick Check
		5.4. Graphs on colored vertices
			5.4.1. Chromatic polynomials
			5.4.2. Colored graphs
			Quick Check
		5.5. Graphs and generating functions
			5.5.1. Trees counted by Cayley’s formula
			5.5.2. Rooted trees
			5.5.3. Connected graphs
			5.5.4. Eulerian graphs
			Quick Check
		5.6. The Lagrange Inversion Formula
			Quick Check
		5.7. Notes
		5.8. Chapter review
		5.9. Exercises
		5.10. Solutions to exercises
		5.11. Supplementary exercises
	6. Extremal combinatorics
		6.1. Extremal graph theory
			6.1.1. Bipartite graphs
			6.1.2. Turán’s theorem
			6.1.3. Graphs excluding cycles
			6.1.4. Graphs excluding complete bipartite graphs
			Quick Check
		6.2. Hypergraphs
			6.2.1. Hypergraphs with pairwise intersecting edges
			6.2.2. Hypergraphs with pairwise incomparable edges
			Quick Check
		6.3. Something is more than nothing: Existence proofs
			6.3.1. Property B
			6.3.2. Excluding monochromatic arithmetic progressions
			6.3.3. Codes over finite alphabets
			Quick Check
		6.4. Notes
		6.5. Chapter review
		6.6. Exercises
		6.7. Solutions to exercises
		6.8. Supplementary exercises
III. An Advanced Method
	7. Analytic combinatorics
		7.1. Exponential growth rates
			7.1.1. Rational functions
			7.1.2. Singularity analysis
			Quick Check
		7.2. Polynomial precision
			7.2.1. Rational functions again
			Quick Check
		7.3. More precise asymptotics
			7.3.1. Entire functions divided by (1 − x)
			7.3.2. Rational functions one more time
			Quick Check
		7.4. Notes
		7.5. Chapter review
		7.6. Exercises
		7.7. Solutions to exercises
		7.8. Supplementary exercises
IV. Special Topics
	8. Symmetric structures
		8.1. Designs
			Quick Check
		8.2. Finite projective planes
			8.2.1. Finite projective planes of prime power order
			Quick Check
		8.3. Error-correcting codes
			8.3.1. Words far apart
			8.3.2. Codes from designs
			8.3.3. Perfect codes
			Quick Check
		8.4. Counting symmetric structures
			Quick Check
		8.5. Notes
		8.6. Chapter review
		8.7. Exercises
		8.8. Solutions to exercises
		8.9. Supplementary exercises
	9. Sequences in combinatorics
		9.1. Unimodality
			Quick Check
		9.2. Log-concavity
			9.2.1. Log-concavity implies unimodality
			9.2.2. The product property
			9.2.3. Injective proofs
			Quick Check
		9.3. The real zeros property
			Quick Check
		9.4. Notes
		9.5. Chapter review
		9.6. Exercises
		9.7. Solutions to exercises
		9.8. Supplementary exercises
	10. Counting magic squares and magic cubes
		10.1. A distribution problem
			Quick Check
		10.2. Magic squares of fixed size
			10.2.1. The case of n=3
			10.2.2. The function Hn(r) for fixed n
			Quick Check
		10.3. Magic squares of fixed line sum
			Quick Check
		10.4. Why magic cubes are different
			Quick Check
		10.5. Notes
		10.6. Chapter review
		10.7. Exercises
		10.8. Solutions to exercises
		10.9. Supplementary exercises
Appendix The method of mathematical induction
	A.1. Weak induction
	A.2. Strong induction
Bibliography
Index