Overview

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.

Full Product Details

Author:   Nicholas Loehr (Virginia Technical University, Blacksburg, USA)
Publisher:   Taylor & Francis Inc
Imprint:   Taylor & Francis Inc
Volume:   63
Dimensions:   Width: 17.80cm , Height: 3.30cm , Length: 25.40cm
Weight:   1.202kg
ISBN:  

9781439848845

ISBN 10:   143984884
Pages:   612
Publication Date:   10 February 2011
Audience:   College/higher education ,  General/trade ,  Tertiary & Higher Education ,  General
Replaced By:   9781498780254
Format:   Hardback
Publisher's Status:   Out of Stock Indefinitely
Availability:   In Print  
Limited stock is available. It will be ordered for you and shipped pending supplier's limited stock.

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 Moebius Inversion Partially Ordered Sets Moebius 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 Polya'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 Moebius 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.

Reviews

A rule I have found to be true is that any book claiming to be suitable for beginners and yet leading to the frontiers of unsolved research problems does neither well. This book is the exception to that rule. ! I found this book engaging. The proofs are very clear, and in many cases several proofs are offered. ! This book could serve several purposes. By focusing on the first half of the book, it could be an excellent choice for a first course in combinatorics for senior undergraduates. By selecting topics and/or moving quickly, it could work well for a more mature audience. ! it also makes a great reference for people who use combinatorics but are not specialists. ! This is a very nice book that deserves serious consideration. --Peter Rabinovitch, MAA Reviews, September 2011

Author Information

Nicholas A. Loehr teaches in the Department of Mathematics at Virginia Tech. His research interests include enumerative and algebraic combinatorics; symmetric and quasisymmetric functions; integer partitions, lattice paths, parking functions, and tableaux; bijective methods; and algorithm analysis.

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions