作者：(美)尼古拉斯·A.洛尔(Nichola
页数：16,627页
出版社：哈尔滨工业大学出版社
出版日期：2023
ISBN：9787576706215
电子书格式：pdf/epub/txt
内容简介
本书的第一部分涵盖了基本的计数工具，包括和与乘积的规则、二项式系数、递归、组合恒等式的双射证明、图论中的枚举问题、包含一排除公式、生成函数、评秩算法和后继算法。阅读这部分内容需要的数学先决条件最少，可用于本科高年级或研究生初级阶段的一个学期的组合学课程。这些材料对计算机科学家、统计学家、工程师、物理学家以及数学家来说都是有趣且有用的。
本书的第二部分包含了对代数组合学的介绍，讨论了群、群作用、排列统计、表格、对称多项式和形式幂级数。这里对对称多项式的表述比标准参考文献[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 Suc
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 Suc
