Bijective combinatorics / Nicholas A. Loehr

Author:: Loehr, Nicholas A.
Published:: Boca Raton, FL : Chapman & Hall/CRC, [2011]
Copyright Date:: ©2011
Physical Description:: xxii, 590 pages : illustrations ; 27 cm.

Availability

I Want It

Finding items...

Series:

Discrete mathematics and its applications

Contents:

Machine generated contents note: 1.Basic Counting -- 1.1.Review of Set Theory -- 1.2.Sum Rule -- 1.3.Product Rule -- 1.4.Words, Permutations, and Subsets -- 1.5.Functions -- 1.6.Bijections, Cardinality, and Counting -- 1.7.Subsets, Binary Words, and Compositions -- 1.8.Subsets of a Fixed Size -- 1.9.Anagrams -- 1.10.Lattice Paths -- 1.11.Multisets -- 1.12.Probability -- 1.13.Games of Chance -- 1.14.Conditional Probability and Independence -- Summary -- Exercises -- 2.Combinatorial Identities and Recursions -- 2.1.Generalized Distributive Law -- 2.2.Multinomial and Binomial Theorems -- 2.3.Combinatorial Proofs -- 2.4.Recursions -- 2.5.Recursions for Multisets and Anagrams -- 2.6.Recursions for Lattice Paths -- 2.7.Catalan Recursions -- 2.8.Integer Partitions -- 2.9.Set Partitions -- 2.10.Surjections -- 2.11.Stirling Numbers and Rook Theory -- 2.12.Linear Algebra Review -- 2.13.Stirling Numbers and Polynomials -- 2.14.Combinatorial Proofs of Polynomial Identities -- Summary -- Exercises -- 3.Counting Problems in Graph Theory -- 3.1.Graphs and Digraphs -- 3.2.Walks and Matrices -- 3.3.DAGs and Nilpotent Matrices -- 3.4.Vertex Degrees -- 3.5.Functional Digraphs -- 3.6.Cycle Structure of Permutations -- 3.7.Counting Rooted Trees -- 3.8.Connectedness and Components -- 3.9.Forests -- 3.10.Trees -- 3.11.Counting Trees -- 3.12.Pruning Maps -- 3.13.Ordered Trees and Terms -- 3.14.Ordered Forests and Lists of Terms -- 3.15.Graph Coloring -- 3.16.Spanning Trees -- 3.17.Matrix-Tree Theorem -- 3.18.Eulerian Tours -- Summary -- Exercises -- 4.Inclusion-Exclusion and Related Techniques -- 4.1.Involutions -- 4.2.The Inclusion-Exclusion Formula -- 4.3.More Proofs of Inclusion-Exclusion -- 4.4.Applications of the Inclusion-Exclusion Formula -- 4.5.Derangements -- 4.6.Coefficients of Chromatic Polynomials -- 4.7.Classical Mobius Inversion -- 4.8.Partially Ordered Sets -- 4.9.Mobius Inversion for Posets -- 4.10.Product Posets -- Summary -- Exercises -- 5.Ranking and Unranking -- 5.1.Ranking, Unranking, and Related Problems -- 5.2.Bijective Sum Rule -- 5.3.Bijective Product Rule -- 5.4.Ranking Words -- 5.5.Ranking Permutations -- 5.6.Ranking Subsets -- 5.7.Ranking Anagrams -- 5.8.Ranking Integer Partitions -- 5.9.Ranking Set Partitions -- 5.10.Ranking Card Hands -- 5.11.Ranking Dyck Paths -- 5.12.Ranking Trees -- 5.13.Successors and Predecessors -- 5.14.Random Selection -- Summary -- Exercises -- 6.Counting Weighted Objects -- 6.1.Weighted Sets -- 6.2.Inversions -- 6.3.Weight-Preserving Bijections -- 6.4.Sum and Product Rules for Weighted Sets -- 6.5.Inversions and Quantum Factorials -- 6.6.Descents and Major Index -- 6.7.Quantum Binomial Coefficients -- 6.8.Quantum Multinomial Coefficients -- 6.9.Foata's Map -- 6.10.Quantum Catalan Numbers -- Summary -- Exercises -- 7.Formal Power Series -- 7.1.The Ring of Formal Power Series -- 7.2.Finite Products and Powers of Formal Series -- 7.3.Formal Polynomials -- 7.4.Order of Formal Power Series -- 7.5.Formal Limits, Infinite Sums, and Infinite Products -- 7.6.Multiplicative Inverses in K[x] and K[[x]] -- 7.7.Formal Laurent Series -- 7.8.Formal Derivatives -- 7.9.Composition of Polynomials -- 7.10.Composition of Formal Power Series -- 7.11.Generalized Binomial Expansion -- 7.12.Generalized Powers of Formal Series -- 7.13.Partial Fraction Expansions -- 7.14.Application to Recursions -- 7.15.Formal Exponentiation and Formal Logarithms -- 7.16.Multivariable Polynomials and Formal Series -- Summary -- Exercises -- 8.The Combinatorics of Formal Power Series -- 8.1.Sum Rule for Infinite Weighted Sets -- 8.2.Product Rule for Infinite Weighted Sets -- 8.3.Generating Functions for Trees -- 8.4.Compositional Inversion Formulas -- 8.5.Generating Functions for Partitions -- 8.6.Partition Bijections -- 8.7.Euler's Pentagonal Number Theorem -- 8.8.Stirling Numbers of the First Kind -- 8.9.Stirling Numbers of the Second Kind -- 8.10.The Exponential Formula -- Summary -- Exercises -- 9.Permutations and Group Actions -- 9.1.Definition and Examples of Groups -- 9.2.Basic Properties of Groups -- 9.3.Notation for Permutations -- 9.4.Inversions and Sign -- 9.5.Determinants -- 9.6.Multilinearity and Laplace Expansions -- 9.7.Cauchy-Binet Formula -- 9.8.Subgroups -- 9.9.Automorphism Groups of Graphs -- 9.10.Group Homomorphisms -- 9.11.Group Actions -- 9.12.Permutation Representations -- 9.13.Stable Subsets and Orbits -- 9.14.Cosets -- 9.15.The Size of an Orbit -- 9.16.Conjugacy Classes in Sn -- 9.17.Applications of the Orbit Size Formula -- 9.18.The Number of Orbits -- 9.19.Polya's Formula -- Summary -- Exercises -- 10.Tableaux and Symmetric Polynomials -- 10.1.Partition Diagrams and Skew Shapes -- 10.2.Tableaux -- 10.3.Schur Polynomials -- 10.4.Symmetric Polynomials -- 10.5.Homogeneous Symmetric Polynomials -- 10.6.Symmetry of Schur Polynomials -- 10.7.Orderings on Partitions -- 10.8.Schur Bases -- 10.9.Tableau Insertion -- 10.10.Reverse Insertion -- 10.11.Bumping Comparison Theorem -- 10.12.Pieri Rules -- 10.13.Schur Expansion of hα -- 10.14.Schur Expansion of eα -- 10.15.Algebraic Independence -- 10.16.Power-Sum Symmetric Polynomials -- 10.17.Relations between e's and h's -- 10.18.Generating Functions for e's and h's -- 10.19.Relations between p's, e's, and h's -- 10.20.Power-Sum Expansion of hn and en -- 10.21.The Involution ω -- 10.22.Permutations and Tableaux -- 10.23.Words and Tableaux -- 10.24.Matrices and Tableaux -- 10.25.Cauchy Identities -- 10.26.Dual Bases -- Summary -- Exercises -- 11.Abaci and Antisymmetric Polynomials -- 11.1.Abaci and Integer Partitions -- 11.2.Jacobi Triple Product Identity -- 11.3.Ribbons and k-Cores -- 11.4.k-Quotients and Hooks -- 11.5.Antisymmetric Polynomials -- 11.6.Labeled Abaci -- 11.7.Pieri Rule for pk -- 11.8.Pieri Rule for ek -- 11.9.Pieri Rule for hk -- 11.10.Antisymmetric Polynomials and Schur Polynomials -- 11.11.Rim-Hook Tableaux -- 11.12.Abaci and Tableaux -- 11.13.Skew Schur Polynomials -- 11.14.Jacobi-Trudi Formulas -- 11.15.Inverse Kostka Matrix -- 11.16.Schur Expansion of Skew Schur Polynomials -- 11.17.Products of Schur Polynomials -- Summary -- Exercises -- 12.Additional Topics -- 12.1.Cyclic Shifting of Paths -- 12.2.Chung-Feller Theorem -- 12.3.Rook-Equivalence of Ferrers Boards -- 12.4.Parking Functions -- 12.5.Parking Functions and Trees -- 12.6.Mobius Inversion and Field Theory -- 12.7.Quantum Binomial Coefficients and Subspaces -- 12.8.Tangent and Secant Numbers -- 12.9.Tournaments and the Vandermonde Determinant -- 12.10.Hook-Length Formula -- 12.11.Knuth Equivalence -- 12.12.Pfaffians and Perfect Matchings -- 12.13.Domino Tilings of Rectangles -- Summary -- Exercises.

Summary:

"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"--
"This book presents a general introduction to enumerative combinatorics that emphasizes bijective methods. The text contains a systematic development of the mathematical tools needed to solve enumeration problems: basic counting rules, recursions, inclusion-exclusion techniques, generating functions, bijective proofs, and linear-algebraic methods. 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. Later chapters delve into some of the algebraic aspects of combinatorics, including detailed treatments of formal power series, symmetric groups, group actions, symmetric polynomials, determinants, and the combinatorial calculus of tableaux"--

Subject(s):

Combinatorial analysis

ISBN:

9781439848845 (hardback)
143984884X (hardback)

Bibliography Note:

Includes bibliographical references and index.

Source of Acquisition:

UP-PAMS copy: Purchased for Student 1,000 hours award - Andrew Rizk; 2011.

View MARC record | catkey: 6966224