Bijective proofs are some of the most elegant and powerful techniques in all of mathematics. Suitable for readers without prior background in algebra or combinatorics, Bijective Combinatorics presents a general introduction to enumerative and algebraic combinatorics that emphasizes bijective methods. The text systematically develops the mathematical tools, such as basic counting rules, recursions, inclusion-exclusion techniques, generating functions, bijective proofs, and linear-algebraic methods, needed to solve enumeration problems. These tools are used to analyze many combinatorial structures, including words, permutations, subsets, functions, compositions, integer partitions, graphs, trees, lattice paths, multisets, rook placements, set partitions, Eulerian tours, derangements, posets, tilings, and abaci. The book also delves into algebraic aspects of combinatorics, offering detailed treatments of formal power series, symmetric groups, group actions, symmetric polynomials, determinants, and the combinatorial calculus of tableaux. Each chapter includes summaries and extensive problem sets that review and reinforce the material. Lucid, engaging, yet fully rigorous, this text describes a host of combinatorial techniques to help solve complicated enumeration problems. It covers the basic principles of enumeration, giving due attention to the role of bijective proofs in enumeration theory.

Table of Contents:
Introduction Basic Counting Review of Set Theory Sum Rule Product Rule Words, Permutations, and Subsets Functions Bijections, Cardinality, and Counting Subsets, Binary Words, and Compositions Subsets of a Fixed Size Anagrams Lattice Paths Multisets Probability Games of Chance Conditional Probability and Independence Combinatorial Identities and Recursions Generalized Distributive Law Multinomial and Binomial Theorems Combinatorial Proofs Recursions Recursions for Multisets and Anagrams Recursions for Lattice Paths Catalan Recursions Integer Partitions Set Partitions Surjections Stirling Numbers and Rook Theory Linear Algebra Review Stirling Numbers and Polynomials Combinatorial Proofs of Polynomial Identities Counting Problems in Graph Theory Graphs and Digraphs Walks and Matrices DAG’s and Nilpotent Matrices Vertex Degrees Functional Digraphs Cycle Structure of Permutations Counting Rooted Trees Connectedness and Components Forests Trees Counting Trees Pruning Maps Ordered Trees and Terms Ordered Forests and Lists of Terms Graph Coloring Spanning Trees Matrix-Tree Theorem Eulerian Tours Inclusion-Exclusion and Related Techniques Involutions The Inclusion-Exclusion Formula More Proofs of Inclusion-Exclusion Applications of the Inclusion-Exclusion Formula Derangements Coefficients of Chromatic Polynomials Classical Möbius Inversion Partially Ordered Sets Möbius Inversion for Posets Product Posets Ranking and Unranking Ranking, Unranking, and Related Problems Bijective Sum Rule Bijective Product Rule Ranking Words Ranking Permutations Ranking Subsets Ranking Anagrams Ranking Integer Partitions Ranking Set Partitions Ranking Card Hands Ranking Dyck Paths Ranking Trees Successors and Predecessors Random Selection Counting Weighted Objects Weighted Sets Inversions Weight-Preserving Bijections Sum and Product Rules for Weighted Sets Inversions and Quantum Factorials Descents and Major Index Quantum Binomial Coefficients Quantum Multinomial Coefficients Foata’s Map Quantum Catalan Numbers Formal Power Series The Ring of Formal Power Series Finite Products and Powers of Formal Series Formal Polynomials Order of Formal Power Series Formal Limits, Infinite Sums, and Infinite Products Multiplicative Inverses in K[x] and K[[x]] Formal Laurent Series Formal Derivatives Composition of Polynomials Composition of Formal Power Series Generalized Binomial Expansion Generalized Powers of Formal Series Partial Fraction Expansions Application to Recursions Formal Exponentiation and Formal Logarithms Multivariable Polynomials and Formal Series The Combinatorics of Formal Power Series Sum Rule for Infinite Weighted Sets Product Rule for Infinite Weighted Sets Generating Functions for Trees Compositional Inversion Formulas Generating Functions for Partitions Partition Bijections Euler’s Pentagonal Number Theorem Stirling Numbers of the First Kind Stirling Numbers of the Second Kind The Exponential Formula Permutations and Group Actions Definition and Examples of Groups Basic Properties of Groups Notation for Permutations Inversions and Sign Determinants Multilinearity and Laplace Expansions Cauchy-Binet Formula Subgroups Automorphism Groups of Graphs Group Homomorphisms Group Actions Permutation Representations Stable Subsets and Orbits Cosets The Size of an Orbit Conjugacy Classes in Sn Applications of the Orbit Size Formula The Number of Orbits Pólya’s Formula Tableaux and Symmetric Polynomials Partition Diagrams and Skew Shapes Tableaux Schur Polynomials Symmetric Polynomials Homogeneous Symmetric Polynomials Symmetry of Schur Polynomials Orderings on Partitions Schur Bases Tableau Insertion Reverse Insertion Bumping Comparison Theorem Pieri Rules Schur Expansion of hα Schur Expansion of eα Algebraic Independence Power-Sum Symmetric Polynomials Relations between e’s and h’s Generating Functions for e’s and h’s Relations between p’s, e’s, and h’s Power-Sum Expansion of hn and en The Involution ω Permutations and Tableaux Words and Tableaux Matrices and Tableaux Cauchy Identities Dual Bases Abaci and Antisymmetric Polynomials Abaci and Integer Partitions Jacobi Triple Product Identity Ribbons and k-Cores k-Quotients and Hooks Antisymmetric Polynomials Labeled Abaci Pieri Rule for pk Pieri Rule for ek Pieri Rule for hk Antisymmetric Polynomials and Schur Polynomials Rim-Hook Tableaux Abaci and Tableaux Skew Schur Polynomials Jacobi-Trudi Formulas Inverse Kostka Matrix Schur Expansion of Skew Schur Polynomials Products of Schur Polynomials Additional Topics Cyclic Shifting of Paths Chung-Feller Theorem Rook-Equivalence of Ferrers Boards Parking Functions Parking Functions and Trees Möbius Inversion and Field Theory Quantum Binomial Coefficients and Subspaces Tangent and Secant Numbers Tournaments and the Vandermonde Determinant Hook-Length Formula Knuth Equivalence Pfaffians and Perfect Matchings Domino Tilings of Rectangles Answers and Hints to Selected Exercises Bibliography Index A Summary and Exercises appear at the end of each chapter.