內容大鋼
本書的第一部分涵蓋了基本的計數工具，包括和與乘積的規則、二項式係數、遞歸、組合恆等式的雙射證明、圖論中的枚舉問題、包含一排除公式、生成函數、評秩演算法和後繼演算法。閱讀這部分內容需要的數學先決條件最少，可用於本科高年級或研究生初級階段的一個學期的組合學課程。這些材料對電腦科學家、統計學家、工程師、物理學家以及數學家來說都是有趣且有用的。
本書的第二部分包含了對代數組合學的介紹，討論了群、群作用、排列統計、表格、對稱多項式和形式冪級數。這裡對對稱多項式的表述比標準參考文獻[84]更具有組合性(希望更易於讀者理解)。特別是一種基於反對稱多項式和算盤的新方法對一些高級結果給出了基本組合證明，例如倍增的舒爾(Schur)對稱多項式的皮耶里(Pieri)規則和利特爾伍德一理查森(Littlewood-Richardson)規則。第二部分假設讀者擁有更多、更複雜的數學知識(主要是線性代數的一些知識)，可用於研究生在數學和相關領域的一個學期的課程中。關於抽象代數和線性代數的一些相關背景材料在附錄中進行了回顧。最後一章由關於可選主題的獨立部分組成，補充了正文中的材料。在許多章節中，章節的後面部分中的一些較難的材料可以省略，不會使閱讀失去連續性。
目錄
Preface to the Second Edition
Introduction
I Counting
1 Basic Counting
1.1 The Product Rule
1.2 The Sum Rule
1.3 Counting Words and Permutations
1.4 Counting Subsets
1.5 Counting Anagrams
1.6 Counting Rules for Set Operations
1.7 Probability
1.8 Lotteries and Card Games
1.9 Conditional Probability and Independence
1.10 Counting Functions
1.11 Cardinality and the Bijection Rule
1.12 Counting Multisets and Compositions
1.13 Counting Balls in Boxes
1.14 Counting Lattice Paths
1.15 Proofs of the Sum Rule and the Product Rule
Summary
Exercises
2 Combinatorial Identities and Recursions
2.1 Initial Examples of Combinatorial Proofs
2.2 The Geometric Series Formula
2.3 The Binomial Theorem
2.4 The Multinomial Theorem
2.5 More Binomial Coefficient Identities
2.6 Sums of Powers of Integers
2.7 Recursions
2.8 Recursions for Multisets and Anagrams
2.9 Recursions for Lattice Paths
2.10 Catalan Recursions
2.11 Integer Partitions
2.12 Set Partitions
2.13 Surjections, Balls in Boxes, and Equivalence Relations
2.14 Stirling Numbers and Rook Theory
2.15 Stirling Numbers and Polynomials
2.16 Solving Recursions with Constant Coefficients
Summary
Exercises
3 Counting Problems in Graph Theory
3.1 Graphs and Digraphs
3.2 Walks and Matrices
3.3 Directed Acyclic Graphs 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 Bipartite Graphs
3.14 Matchings and Vertex Covers
3.15 Two Matching Theorems
3.16 Graph Coloring
3.17 Spanning Trees
3.18 The Matrix-Tree Theorem
3.19 Eulerian Tours
Summary
Exercises
4 Inclusion-Exclusion, Involutions, and M6bius Inversion
4.1 The Inclusion-Exclusion Formula
4.2 Examples of the Inclusion-Exclusion Formula
4.3 Surjections and Stirling Numbers
4.4 Euler's φ Function
4.5 Derangements
4.6 Involutions
4.7 Involutions Related to Inclusion-Exclusion
4.8 Generalized Inclusion-Exclusion Formulas
4.9 MSbius Inversion in Number Theory
4.10 Partially Ordered Sets
4.11 M6bius Inversion for Posets
4.12 Product Posers
Summary
Exercises
5 Generating Functions
5.1 What is a Generating Function?
5.2 Convergence of Power Series
5.3 Examples of Analytic Power Series
5.4 Operations on Power Series
5.5 Solving Recursions with Generating Functions
5.6 Evaluating Summations with Generating Functions
5.7 Generating Function for Derangements
5.8 Counting Rules for Weighted Sets
5.9 Examples Of the Product Rule for Weighted Sets
5.10 Generating Functions for Trees
5.11 Tree Bijections
5.12 Exponential Generating Functions
5.13 Stirling Numbers of the First Kind
5.14 Stirling Numbers of the Second Kind
5.15 Generating Functions for Integer Partitions
5.16 Partition Bijections
5.17 Euler's Pentagonal Number Theorem
Summary
Exercises
6 Ranking, Unranking, and Successor Algorithms
6.1 Introduction to Ranking and Successor Algorithms
6.2 The Bijective Sum Rule
6.3 The Bijective Product Rule for Two Sets
6.4 The Bijective Product Rule
6.5 Ranking Words
6.6 Ranking Permutations
6.7 Ranking Subsets
6.8 Ranking Anagrams
6.9 Ranking Integer Partitions
6.10 Ranking Set Partitions
6.11 Ranking Trees
6.12 The Successor Sum Rule
6.13 Successor Algorithms for Anagrams
6.14 The Successor Product Rule
6.15 Successor Algorithms for Set Partitions
6.16 Successor Algorithms for Dyck Paths
Summary
Exercises
II Algebraic Combinatorics
7 Groups, Permutations, and Group Actions
7.1 Definition and Examples of Groups
7.2 Basic Properties of Groups
7.3 Notation for Permutations
7.4 Inversions and Sign of a Permutation
7.5 Subgroups
7.6 Automorphism Groups of Graphs
7.7 Group Homomorphisms
7.8 Group Actions
7.9 Permutation Representations
7.10 Stable Subsets and Orbits
7.11 Cosets
7.12 The Size of an Orbit
7.13 Conjugacy Classes in Sn
7.14 Applications of the Orbit Size Formula
7.15 The Number of Orbits
7.16 Polya's Formula
Summary
Exercises
8 Permutation Statistics and q-Analogues
8.1 Statistics cn Finite Sets
8.2 Counting Rules for Finite Weighted Sets
8.3 Inversions
8.4 q-Factorials and Inversions
8.5 Descents and Major Index
8.6 q-Binomial Coefficients
8.7 Combinatorial Interpretations of q-Binomial Coefficients
8.8 q-Binomial Coefficient Identities
8.9 q-Multinomial Coefficients
8.10 Foata's Bijection
8.11 q-Catalan Numbers
8.12 Set Partitions and q-Stirling Numbers
Summary
Exercises
9 Tableaux and Symmetric Polynomials
9.1 Fillings and Tableaux
9.2 Schur Polynomials
9.3 Symmetric Polynomials
9.4 Vector Spaces of Symmetric Polynomials
9.5 Symmetry of Schur Polynomials
9.6 Orderings on Partitions
9.7 Schur Bases
9.8 Tableau Insertion
9.9 Reverse Insertion
9.10 The Bumping Compariscn Theorem
9.11 The Pieri Rules
9.12 Schur Expansion of hα
9.13 Schur Expansion of eα
9.14 Algebraic Independence
9.15 Power-Sum Symmetric Polynomials
9.16 Relations between e's and h's
9.17 Generating Functions for e's and h's
9.18 Relations between p's, e's, and h's
9.19 Power-Sum Expansions of hn and en
9.20 The Involution ω
9.21 Permutations and Tableaux
9.22 Inversion Property of RSK
9.23 Words and Tableaux
9.24 Matrices and Tableaux
9.25 Cauehy's Identities
9.26 Dual Bases
9.27 Skew Schur Polynomials
9.28 Abstract Symmetric Functions
Summary
Exercises
10 Abaci and Antisymmetric Polynomials
10.1 Abaci and Integer Partitions
10.2 The Jacobi Triple Product Identity
10.3 Ribbons and k-Cores
10.4 k-Quotients of a Partition
10.5 k-Quotients and Hooks
10.6 Antisymmetric Polynomials
10.7 Labeled Abaci
10.8 The Pieri Rule for pk
10.9 The Pieri Rule for ek
10.10 The Pieri Rule for hk
10.11 Antisymmetric Polynomials and Schur Polynomials
10.12 Rim-Hook Tableaux
10.13 Abaci and Tableaux
10.14 Skew Schur Polynomials
10.15 The Jacobi-Trudi Formulas
10.16 The Inverse Kostka Matrix
10.17 Schur Expansion of Skew Schur Polynomials
10.18 Products of Schur Polynomials
Summary
Exercises
11 Algebraic Aspects of Generating Functions
11.1 Limit Concepts for Formal Power Series
11.2 The Infinite Sum and Product Rules
11.3 Multiplicative Inverses of Formal Power Series
11.4 Partial Fraction Expansions
11.5 Generating Functions for Recursively Defined Sequences
11.6 Formal Composition and Derivative Rules
11.7 Formal Exponentials and Logarithms
11.8 The Exponential Formula
11.9 Examples of the Exponential Formula
11.10 Ordered Trees and Terms
11.11 Ordered Forests and Lists of Terms
11.12 Compositional Inversion
Summary
Exercises
12 Additional Topics
12.1 Cyclic Shifting of Paths
12.2 The Chung Feller Theorem
12.3 Rook-Equivalence of Ferrers Boards
12.4 Parking Functions
12.5 Parking Functions and Trees
12.6 M5bius Inversion and Field Theory
12.7 q-Binomial Coefficients and Subspaces
12.8 Tangent and Secant Numbers
12.9 Combinatorial Definition of Determinants
12.10 The Cauchy-Binet Theorem
12.11 Tournaments and the Vandermonde Determinant
12.12 The Hook-Length Formula
12.13 Knuth Equivalence
12.14 Quasisymmetric Polynomials
12.15 Pfaffians and Perfect Matchings
12.16 Domino Tilings of Rectangles
Summary
Exercises
Appendix: Definitions from Algebra
Rings and Fields
Vector Spaces and Algebras
Linear Algebra Concepts
Bibliography
Index
編輯手記
[