Combinatorial Enumeration

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780486435978 | 0486435970
Cover: Paperback
Copyright: 6/23/2004

Rent

(Recommended)

$28.80

Term

Due

Price

Semester

Dec 11

$28.80

Quarter

Oct 7

$27.36

Short Term

Sep 7

$25.91

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping bag.
Buy New

Usually Ships in 3-5 Business Days

$36.87

This graduate-level text presents mathematical theory and problem-solving techniques associated with enumeration problems. Subjects include the combinatorics of the ordinary generating function and the exponential generating function, the combinatorics of sequences, and the combinatorics of paths. The text is complemented by approximately 350 exercises with full solutions. 1983 edition. Foreword by Gian-Carlo Rota. References. Index.

Notation

xxiii

1 MATHEMATICAL PRELIMINARIES

1.1 The Ring of Formal Power Series

1.1.1 Formal Power Series,

(1)

1.1.2 The Coefficient Operator,

(1)

1.1.3 Infinite Sums and Products,

(1)

1.1.4 Compositional and Multiplicative Inverses,

(1)

1.1.5 The Formal Derivative and Integral,

(1)

1.1.6 The Logarithmic, Exponential, and Binomial Power Series,

(3)

1.1.7 Circular and Hyperbolic Power Series,

(1)

1.1.8 Formal Differential Equations,

(1)

1.1.9 Roots of a Power Series,

(1)

1.1.10 Matrices Over the Ring of Formal Power Series,

(1)

1.1.11 Formal Laurent Series,

(1)

Notes and References

(1)

Exercises

(3)

1.2 The Lagrange Theorem for Implicit Functions

(14)

1.2.1 Proposition,

(1)

1.2.2 Theorem (Residue Composition),

(1)

1.2.3 An Identity (by Residue Composition),

(1)

1.2.4 Theorem (Lagrange),

(1)

1.2.5 A Functional Equation,

(1)

1.2.6 The Central Trinomial Numbers,

(1)

1.2.7 Abel's Extension of the Binomial Theorem,

(1)

1.2.8 Theorem (Multivariate Residue Composition),

(2)

1.2.9 Theorem (Multivariate Lagrange),

(1)

1.2.10 A Functional Equation in Two Variables,

(1)

1.2.11 Theorem (MacMahon Master Theorem),

(1)

1.2.12 Dixon's Identity,

(2)

1.2.13 Corollary (Lagrange Theorem for Monomials),

(1)

Notes and References

(1)

Exercises

(3)

2 THE COMBINATORICS OF THE ORDINARY GENERATING FUNCTION

(129)

2.1 Introduction

(2)

2.1.1 The Elementary Counting Lemmas,

(1)

2.1.2 Decompositions and Weight Functions,

(1)

2.1.3 Direct and Indirect Decompositions, Combinatorial Marking, and Multivariate Generating Functions,

(1)

2.1.4 A Classical Application of Enumerative Arguments,

(1)

2.1.5 Recursive and "At-Least" Decompositions,

(1)

2.2 The Elementary Counting Lemmas

(17)

2.2.1 Definition (Distinguishability),

(1)

2.2.2 Definition (Weight Function, Weight),

(1)

2.2.3 Remark (The General Enumerative Problem),

(1)

2.2.4 Example (Enumerative Problems),

(1)

2.2.5 Definition (Ordinary Generating Function),

(1)

2.2.6 Remark (s-Objects),

(1)

2.2.7 Example (a Generating Function),

(1)

2.2.8 Proposition,

(1)

2.2.9 Definition (Decomposition, ω-Preserving),

(1)

2.2.10 Proposition,

(1)

2.2.11 Example (Terquem Problem: Decomposition),

(1)

2.2.12 Lemma (Sum),

(1)

2.2.13 Example (Sum),

(1)

2.2.14 Lemma (Product),

(1)

2.2.15 Example (Terquem Problem: Generating Function),

(1)

2.2.16 Definition (Additively Weight-Preserving Decomposition),

(1)

2.2.17 Remark (Direct, Indirect, Recursive Decompositions),

(1)

2.2.18 Example (an Indirect Decomposition),

(1)

2.2.19 Example (a Recursive Decomposition),

(1)

2.2.20 Definition (Composition),

(1)

2.2.21 Example (Composition),

(1)

2.2.22 Lemma (Composition),

(1)

2.2.23 Example (Composition),

(1)

2.2.24 Definition (s-Derivative),

(1)

2.2.25 Example (s-Derivative of a Set of Permutations),

(1)

2.2.26 Lemma (Differentiation),

(1)

2.2.27 Example (s-Derivative),

(1)

2.2.28 Definition ("Exact," "At-Least" Generating Functions),

(1)

2.2.29 Lemma (the Principle of Inclusion and Exclusion),

(1)

2.2.30 Example (Derangements),

(1)

Notes and References

(1)

2.3 Preliminary Examples

(14)

2.3.1 Decomposition (Subsets),

(1)

2.3.2 Subsets,

(1)

2.3.3 Recurrence Equation for Binomial Coefficients,

(1)

2.3.4 Decomposition (Multisets),

(1)

2.3.5 Multisets,

(1)

2.3.6 Definition (Composition of an Integer),

(1)

2.3.7 Decomposition (Compositions of an Integer),

(1)

2.3.8 Compositions of an Integer,

(1)

2.3.9 Correspondence (Multisets-Compositions),

(1)

2.3.10 Compositions and Parts,

(1)

2.3.11 Recurrence Equation for Compositions and Parts,

(1)

2.3.12 An Identity from Compositions,

(1)

2.3.13 Definition (Succession in a Set),

(1)

2.3.14 Decomposition (Subsets),

(1)

2.3.15 Subsets with Successions,

(1)

2.3.16 Definition (Skolem Subsets),

(1)

2.3.17 Decomposition (Skolem Subsets),

(1)

2.3.18 The Skolem Problem,

(1)

2.3.19 Definition (Circular Succession),

(1)

2.3.20 Decomposition (Subsets),

(1)

2.3.21 Example (Circular Successions),

(1)

2.3.22 Subsets and Circular Successions,

(1)

Notes and References

(1)

Exercises

(3)

2.4 Sequences

(18)

2.4.1 Definition (Substring, Subsequence, Block),

(1)

2.4.2 Definition (Maximal Block),

(1)

2.4.3 Decomposition ({0,1}-Sequences),

(1)

2.4.4 {0,1}-Sequences and Maximal Blocks of 1's,

(1)

2.4.5 Decomposition ({0,1}-Sequences),

(1)

2.4.6 {0,1}-Sequences and Maximal Blocks of 0's and 1's,

(1)

2.4.7 Definition (Type of a Sequence),

(1)

2.4.8 Sequences and Type,

(1)

2.4.9 Sequences and Type Restrictions,

(1)

2.4.10 Compositions and Part Restrictions,

(1)

2.4.11 Remark (Sequences and Compositions),

(1)

2.4.12 Ordered Factorizations,

(1)

2.4.13 Definition (Rise, Level, Fall),

(1)

2.4.14 Definition (Smirnov Sequence),

(1)

2.4.15 Decomposition (Smirnov Sequences),

(1)

2.4.16 The Smimov Problem,

(1)

2.4.17 Sequences and Levels,

(1)

2.4.18 Sequences and Maximal Blocks,

(1)

2.4.19 Decomposition (Sequences and Falls),

(1)

2.4.20 The Simon Newcomb Problem,

(1)

2.4.21 Permutations and Falls,

(1)

2.4.22 Definition (Sequence with Strictly Increasing Support),

(1)

2.4.23 Decomposition (Sequences with Strictly Increasing Support),

(1)

2.4.24 Sequences of Type (2,...,2) with Strictly Increasing Support,

(1)

2.4.25 Definition (Dirichlet Generating Function),

(1)

2.4.26 Lemma (Product),

(1)

2.4.27 Definition (Multiplicatively Weight-Preserving Decomposition),

(1)

2.4.28 Ordered Factorizations and Dirichlet Generating Functions,

(1)

2.4.29 Remark (Sequences and Ordered Factorizations),

(1)

Notes and References

(1)

Exercises

(4)

2.5 Partitions of an Integer

(16)

2.5.1 Definition (Partition),

(1)

2.5.2 Decomposition (Partitions),

(1)

2.5.3 The Number of Partitions,

(1)

2.5.4 Example (Calculation of ρ(6)),

(1)

2.5.5 Distinct Parts,

(1)

2.5.6 Largest Part Exactly m,

(1)

2.5.7 Definition (Conjugate),

(1)

2.5.8 Decomposition (Partitions with Given Largest Part),

(1)

2.5.9 All Partitions-Euler's Theorem,

(1)

2.5.10 Definition (Ferrers Graph, Durfee Square),

(1)

2.5.11 Definition (Abutment),

(1)

2.5.12 Decomposition (All Partitions),

(1)

2.5.13 All Partitions-q-Analogue of Kummer's Theorem,

(1)

2.5.14 All Partitions-Euler's Theorem,

(1)

2.5.15 Definition-Maximal Triangle,

(1)

2.5.16 Decomposition (Partitions with Distinct Parts),

(1)

2.5.17 Partitions with Distinct Parts-An Identity,

(1)

2.5.18 Partitions with Distinct Parts-Euler's Theorem,

(1)

2.5.19 Decomposition (Self-conjugate Partitions),

(1)

2.5.20 Decomposition (Self-conjugate Partitions),

(1)

2.5.21 Self-conjugate Partitions-An Identity,

(1)

2.5.22 Self-conjugate Partitions-Euler's Theorem,

(1)

2.5.23 Decomposition (Sylvester: All Partitions),

(2)

2.5.24 The Jacobi Triple Product Identity,

(1)

2.5.25 Euler's Theorem for Pentagonal Numbers,

(1)

Notes and References

(1)

Exercises

(3)

2.6 Inversions in Permutations and q-Identities

(13)

2.6.1 Definition (Inversion),

(1)

2.6.2 Algorithm (Inversion),

(1)

2.6.3 Proposition,

(1)

2.6.4 Lemma (Inversions),

(1)

2.6.5 Example (Between-Set and Within-Set Inversions),

(1)

2.6.6 Lemma (Between-Set and Within-Set Generating Functions),

(2)

2.6.7 Recurrence Equation for q-Binomial Coefficients,

100

(1)

2.6.8 Definition (Increasing, Decreasing, Cup-, Cap-permutations),

100

(1)

2.6.9 Lemma (Cup- and Cap-permutations),

101

(1)

2.6.10 Theorem (Bimodal Permutation),

102

(1)

2.6.11 Corollary (q-Analogue of the Binomial Theorem),

103

(1)

2.6.12 Three Finite Product Identities,

104

(1)

2.6.13 Proposition,

104

(1)

2.6.14 Four Infinite Product Identities,

105

(1)

Notes and References

106

(1)

Exercises

106

(3)

2.7 Planted Plane Trees

109

(19)

2.7.1 Definition (Branch, Branch List),

110

(1)

2.7.2 Decomposition (Planted Plane Cubic Trees),

110

(1)

2.7.3 Planted Plane Cubic Trees and Nonroot Monovalent Vertices,

111

(1)

2.7.4 Decomposition (Branch),

111

(1)

2.7.5 Planted Plane Trees and Nonroot Vertices,

112

(1)

2.7.6 Definition (Degree Sequence),

112

(1)

2.7.7 Planted Plane Trees and Degree Sequence,

112

(1)

2.7.8 Planted Plane Trees and Bivalent Vertices,

113

(1)

2.7.9 Decomposition (Planted Plane Trees),

114

(1)

2.7.10 Planted Plane Trees and Bivalent Vertices, by Composition,

114

(1)

2.7.11 Planted Plane Trees with No Isolated Bivalent Vertices,

115

(1)

2.7.12 Definition (2-Chromatic Tree),

116

(1)

2.7.13 Decomposition (Planted Plane 2-Chromatic Trees),

116

(1)

2.7.14 Planted Plane 2-Chromatic Trees,

116

(1)

2.7.15 Definition (Height of a Vertex),

117

(1)

2.7.16 Vertices of Given Degree and Height in Planted Plane Trees (First Method),

118

(2)

2.7.17 Decomposition (Planted Plane Trees with a Single Distinguished Vertex of Degree d and Height h),

120

(1)

2.7.18 Vertices of Given Degree and Height in Planted Plane Trees (Second Method),

121

(1)

2.7.19 Remark (Finding Decompositions),

121

(1)

2.7.20 Definition (Left-most Path),

122

(1)

2.7.21 Decomposition (Left-most Path),

122

(1)

2.7.22 Planted Plane Trees, Left-most Paths, and Degree Sequence,

122

(2)

Notes and References

124

(1)

Exercises

125

(3)

2.8 Sequences with Distinguished Substrings

128

(10)

2.8.1 Definition (Α-Type of a Sequence),

128

(1)

2.8.2 Definition (kappa-Cluster),

128

(1)

2.8.3 Definition (Cluster Generating Function),

129

(1)

2.8.4 Definition,

130

(1)

2.8.5 Proposition,

131

(1)

2.8.6 Theorem (Distinguished Substring),

131

(1)

2.8.7 Sequences with No ρ th Powers of Strings of Length kappa,

132

(2)

2.8.8 Sequences and Strictly Increasing Substrings,

134

(1)

2.8.9 Definition (Connector Matrix),

135

(1)

2.8.10 Lemma (Cluster Generating Function for an Arbitrary Set),

135

(1)

2.8.11 Example,

136

(1)

Notes and References

137

(1)

Exercises

137

(1)

2.9 Rooted Planar Maps and the Quadratic Method

138

(20)

2.9.1 The Quadratic Method,

138

(1)

2.9.2 Definition (Planar Map),

139

(1)

2.9.3 Proposition (Euler's Polyhedral Formula),

140

(1)

2.9.4 Definition (Rooted Planar Map, Root Edge, Root Face, Root Vertex),

140

(1)

2.9.5 Decomposition (Rooted Near-triangulation; Root Edge),

141

(1)

2.9.6 Rooted Near-triangulations and Inner Faces,

142

(1)

2.9.7 Rooted Near-triangulations, Inner Faces, and Degree of Outer Face,

143

(2)

2.9.8 Decomposition (Rooted Planar Map; Root Edge),

145

(1)

2.9.9 Rooted Planar Maps,

146

(3)

2.9.10 Decomposition (2-Edge-Connected Rooted Planar Map),

149

(1)

2.9.11 2-Edge-Connected Rooted Planar Maps,

150

(1)

2.9.12 Decomposition (Nonseparable Rooted Planar Map),

151

(1)

2.9.13 Nonseparable Rooted Planar Maps,

152

(2)

Notes and References

154

(1)

Exercises

154

(4)

3 THE COMBINATORICS OF THE EXPONENTIAL GENERATING FUNCTION

158

(72)

3.1 Introduction

158

(2)

3.1.1 The Elementary Counting Lemmas,

158

(1)

3.1.2 The *-Product and *-Composition,

159

(1)

3.1.3 The *-Derivative,

159

(1)

3.1.4 The Τ-Series,

160

(1)

3.2 The Elementary Counting Lemmas

160

(10)

3.2.1 Definition (s-Tagged Configuration, Tag Set, Tag Weight),

160

(1)

3.2.2 Example (s-Tagged Configurations),

161

(1)

3.2.3 Definition (Exponential Generating Function),

161

(1)

3.2.4 Proposition,

161

(1)

3.2.5 Proposition,

161

(1)

3.2.6 Lemma (Sum),

162

(1)

3.2.7 Example (Exponential Generating Functions),

162

(1)

3.2.8 Example (Derangements),

162

(1)

3.2.9 Definition (* -Product),

163

(1)

3.2.10 Example (*-Product),

163

(1)

3.2.11 Lemma (* -Product),

163

(1)

3.2.12 Example (a Permutation Problem),

164

(1)

3.2.13 Example (a Sequence Problem),

165

(1)

3.2.14 Definition (* -Composition with Respect to s-Objects),

165

(1)

3.2.15 Example (* -Composition),

166

(1)

3.2.16 Lemma (* -Composition),

166

(1)

3.2.17 Partitions of a Set,

167

(1)

3.2.18 Definition (*-Differentiation),

167

(1)

3.2.19 Lemma (* -Differentiation),

168

(1)

3.2.20 Remark (a Construction for the * -Derivative),

168

(1)

3.2.21 Definition (Alternating Permutation),

168

(1)

3.2.22 André's Problem,

169

(1)

Notes and References

169

(1)

3.3 Trees and Cycles in Permutations and Functions

170

(27)

3.3.1 Decomposition (Derangements),

170

(1)

3.3.2 Derangements (Indirect Decomposition),

170

(1)

3.3.3 A Recurrence Equation for the Derangement Number,

171

(1)

3.3.4 Definition (Circular Permutation),

171

(1)

3.3.5 Decomposition (Cycle; for Permutations),

171

(1)

3.3.6 Derangements (Direct Decomposition),

172

(1)

3.3.7 Involutions,

172

(1)

3.3.8 Definition (Labeled Tree),

173

(1)

3.3.9 Decomposition (Labeled Branch),

174

(1)

3.3.10 Rooted Labeled Trees,

174

(1)

3.3.11 Proposition,

175

(1)

3.3.12 Decomposition (Cycle; for Functions),

176

(1)

3.3.13 Functions and Cycle Type,

176

(1)

3.3.14 Expectation of the Number of Cycles of Given Length in Functions,

176

(1)

3.3.15 Idempotent Functions,

177

(1)

3.3.16 Decomposition (Recursive Cycle; for Permutations),

178

(1)

3.3.17 Derangements and Involutions (Recursive Decomposition),

178

(1)

3.3.18 Remark (Distinguished Tagged s-Objects),

179

(1)

3.3.19 Correspondence (Functions from Nn to Nn-Rooted Labeled Trees),

179

(2)

3.3.20 Rooted Labeled Trees (Direct Decomposition),

181

(1)

3.3.21 Definition (Spanning Tree),

181

(1)

3.3.22 Lemma (Edge-Weighted Tree),

181

(1)

3.3.23 Theorem (Matrix-Tree),

182

(1)

3.3.24 In-Directed and Out-Directed Spanning Arborescences,

183

(2)

3.3.25 Matrix-Tree Theorem for Undirected Graphs,

185

(1)

3.3.26 Labeled Trees,

185

(1)

Notes and References

185

(1)

Exercises

186

(11)

3.4 2-Covers of a Set and Homeomorphically Irreducible Labeled Graphs

197

(16)

3.4.1 Decomposition ({0,1{-Matrices),

197

(1)

3.4.2 Example,

198

(1)

3.4.3 {0, 1}-Matrices with No Rows or Columns of 0's,

198

(1)

3.4.4 Recurrence Equation,

199

(1)

3.4.5 A Differential Decomposition for Matrices with No 0 Rows or Columns,

200

(1)

3.4.6 Definition (Proper kappa-Cover, Restricted Proper kappa-Cover),

201

(1)

3.4.7 Decomposition (Proper 2-Covers),

201

(1)

3.4.8 Proper 2-Covers,

202

(1)

3.4.9 Restricted Proper 2-Covers,

203

(1)

3.4.10 A Differential Equation for Restricted Proper 2-Covers,

204

(1)

3.4.11 A Differential Decomposition for Restricted Proper 2-Covers,

204

(2)

3.4.12 Decomposition (Simple Labeled h-Graphs),

206

(1)

3.4.13 Proposition,

207

(1)

3.4.14 Simple Labeled h-Graphs,

207

(2)

3.4.15 A Recurrence Equation for Simple Labeled h-Graphs,

209

(1)

Notes and References

209

(1)

Exercises

209

(4)

3.5 Coefficient Extraction for Symmetric Functions

213

(17)

3.5.1 Definition (ρ-Regular Graph),

213

(1)

3.5.2 The Ordinary Generating Function for Simple Labeled Graphs,

213

(1)

3.5.3 Definition (Monomial Symmetric Function),

214

(1)

3.5.4 Proposition,

214

(1)

3.5.5 A Differential Equation for Simple Labeled Graphs in Terms of Power Sum Symmetric Functions,

215

(1)

3.5.6 Proposition,

216

(1)

3.5.7 Theorem (Τ-Series),

217

(1)

3.5.8 The Τ-Series for Simple 3-Regular Labeled Graphs,

218

(1)

3.5.9 A Recurrence Equation for Simple 3-Regular Labeled Graphs,

219

(2)

3.5.10 Non-negative Integer Matrices with Line Sum Equal to 2,

221

(3)

3.5.11 Differential Decomposition for Simple 3-Regular Labeled Graphs,

224

(3)

Notes and References

227

(1)

Exercises

227

(3)

4 THE COMBINATORICS OF SEQUENCES

230

(60)

4.1 Introduction

230

(1)

4.2 The Maximal String Decomposition Theorem

231

(12)

4.2.1 Definition (Π1-String, Maximal v1-String Type),

231

(1)

4.2.2 Definition (Π1-String Enumerator, Maximal Π1-String Length Enumerator),

232

(1)

4.2.3 Theorem (Maximal String Decomposition),

232

(1)

4.2.4 Definition (Rises, Successions, c-Successions),

233

(1)

4.2.5 Lemma ([-Transformation, + -Transformation, Θ -Transformation), 233

4.2.6 Definition (Π1-Alternating Sequence),

234

(1)

4.2.7 Corollary (Π1-Alternating Sequences of Even Length),

234

(1)

4.2.8 [-Alternating Permutations of Even Length, 234

4.2.9 +-Alternating Permutations of Even Length,

234

(1)

4.2.10 Θ-Alternating Permutations of Even Length,

235

(1)

4.2.11 [-Alternating Permutations of Even Length, Inversions, 235

4.2.12 Corollary (Sequences, Type, Occurrences of Π1),

235

(1)

4.2.13 Sequences and Rises (Simon Newcomb Problem),

236

(1)

4.2.14 Sequences and Levels (Smirnov Problem),

236

(1)

4.2.15 Corollary (Sequences, Π1-Strings of Length ρ),

237

(1)

4.2.16 Sequences with vi-Strings of Length 3,

237

(1)

4.2.17 Permutations with [-Strings of Length 3, Inversions, 237

4.2.18 Permutations with Prescribed Product of Maximal [-String Lengths, 237

4.2.19 Theorem (Maximal String Decomposition; Distinguished Final String),

238

(1)

4.2.20 Corollary (Π1-Alternating Sequences of Odd Length),

238

(1)

4.2.21 [-Alternating Permutations of Odd Length, with Inversions, 239

4.2.22 [-Alternating Permutations of Odd Length, 239

Notes and References

239

(1)

Exercises

240

(3)

4.3 The Pattern Algebra

243

(25)

4.3.1 Definition (Pattern),

243

(1)

4.3.2 Definition (Incidence Matrix, Set of Encodings),

244

(1)

4.3.3 Definition (Fundamental Generating Functions),

245

(1)

4.3.4 Proposition (Incidence Matrices for Union and Product),

245

(1)

4.3.5 Lemma (Sum, Product for the Fundamental Generating Functions),

245

(1)

4.3.6 Proposition (Π1-String Enumerator),

246

(1)

4.3.7 Π1-Alternating Sequences of Odd Length,

247

(1)

4.3.8 Theorem (Elimination),

248

(1)

4.3.9 Definition (Left-, Right-Expansions),

249

(1)

4.3.10 Algorithm (Factored Expansion),

250

(1)

4.3.11 Remark (General Strategy),

250

(1)

4.3.12 Proof of the Maximal String Decomposition Theorem,

250

(1)

4.3.13 Definition (Sequence with Repeated Pattern),

251

(1)

4.3.14 Sequences with Repeated Pattern Π²1Π²2

252

(1)

4.3.15 Permutations with Repeated Pattern Π²1Π²2 for Rises,

253

(1)

4.3.16 Sequences with Fixed Pattern,

254

(1)

4.3.17 Permutations with Fixed Pattern and Inversions,

255

(1)

4.3.18 A Tripartite Problem,

256

(1)

4.3.19 A q-Identity for the Tangent Function,

257

(1)

4.3.20 A q-Identity from Permutations with Repeated Pattern,

258

(1)

Notes and References

259

(1)

Exercises

259

(9)

4.4 The Logarithmic Connection for Circular Permutations

268

(13)

4.4.1 Definition (Circular Sequence),

268

(2)

4.4.2 Theorem (Logarithmic Connection),

270

(1)

4.4.3 Theorem (Maximal String Decomposition for Circular Permutations),

271

(1)

4.4.4 Circular Permutations and Maxima,

272

(1)

4.4.5 Directed Hamiltonian Cycles of the Complete Directed Graph with Distinguished Hamiltonian Cycles,

273

(2)

4.4.6 Hamiltonian Cycles of the Complete Graph with a Distinguished Hamiltonian Cycle,

275

(1)

4.4.7 The Menage Problem,

275

(2)

Notes and References

277

(1)

Exercises

277

(4)

4.5 Permanents and Absolute Problems

281

(9)

4.5.1 Proposition (Permanent),

281

(1)

4.5.2 Definition (Absolute Partition for Permutations),

281

(1)

4.5.3 Lemma (Absolute Partition),

281

(1)

4.5.4 Derangements,

282

(1)

4.5.5 The Ménage Problem (Absolute),

282

(1)

4.5.6 Definition (kappa-Discordant Permutation),

283

(1)

4.5.7 3-Discordant Permutations,

283

(1)

4.5.8 Definition (Latin Rectangle),

284

(1)

4.5.9 Decomposition ((3 X n)-Latin Rectangles),

284

(1)

4.5.10 (3 X n)-Latin Rectangles,

285

(1)

4.5.11 A Correspondence for Sequences and Absolute Sequences,

286

(1)

4.5.12 Permutations Whose Cycles Have Repeated Pattern Π²1Π²2

287

(1)

Notes and References

287

(1)

Exercises

287

(3)

5 THE COMBINATORICS OF PATHS

290

(49)

5.1 Introduction

290

(1)

5.1.1 Continued Fractions,

290

(1)

5.1.2 Arbitrary Steps and Nonintersecting Paths,

291

(1)

5.1.3 A q-Analogue of the Lagrange Theorem,

291

(1)

5.2 Weighted Paths

291

(22)

5.2.1 Definition (J-Fraction, S-Fraction),

291

(1)

5.2.2 Proposition (Contraction),

292

(1)

5.2.3 Definition (Height of a Planted Plane Tree),

292

(1)

5.2.4 Proposition (Stieltjes-Rogers Polynomials),

292

(1)

5.2.5 Definition (Altitude, Path, Height),

293

(1)

5.2.6 Decomposition (Path),

294

(1)

5.2.7 Lemma (Path),

294

(1)

5.2.8 Definition (Addition Formula),

295

(1)

5.2.9 Decomposition (Path),

295

(1)

5.2.10 The Stieltjes-Rogers J-Fraction Theorem,

296

(1)

5.2.11 A Continued Fraction Associated with Factorials,

297

(1)

5.2.12 Lemma (Weighted Path),

298

(1)

5.2.13 Definition (Double Rise, Double Fall, Modified Maximum, Modified Minimum),

299

(1)

5.2.14 Algorithm (Associated Tree),

299

(1)

5.2.15 Decomposition (Francon-Viennot),

300

(1)

5.2.16 All Permutations,

301

(1)

5.2.17 > -Alternating Permutations of Odd Length, 302

5.2.18 Corollary (Right-most Element in a Permutation),

302

(1)

5.2.19 > -Alternating Permutations of Even Length,

302

(1)

5.2.20 > -Alternating Permutations of Even Length with Even-Valued Minima-the Jacobi Elliptic Function cn(χ, α),

303

(1)

5.2.21 Proposition (Recurrence Equation, Determinant Identity),

304

(1)

5.2.22 Theorem (Path Enumeration),

304

(1)

5.2.23 > -Alternating Permutations of Even Length with Respect to Height-Meixner Polynomial,

305

(1)

Notes and References

305

(1)

Exercises

306

(7)

5.3 Lattice Paths

313

(9)

5.3.1 Definition (Altitude, Path, Step),

313

(1)

5.3.2 Definition (Minus-, Zero-, Plus-path),

314

(1)

5.3.3 Decomposition (Lattice Path),

315

(1)

5.3.4 Theorem (Lattice Path),

316

(1)

5.3.5 Example,

317

(2)

5.3.6 Paths with an Oblique Barrier,

319

(2)

Notes and References

321

(1)

Exercises

321

(1)

5.4 Ordered Sets of Paths

322

(8)

5.4.1 Decomposition (Intersecting η-Path),

323

(1)

5.4.2 Theorem (Nonintersecting η-Path),

324

(1)

5.4.3 Definition (Column-Strict Plane Partition, Shape, Size),

325

(1)

5.4.4 Decomposition (η-Path: for Column-Strict Plane Partitions),

325

(1)

5.4.5 Theorem (Column-Strict Plane Partition: Shape, Size, Type),

325

(2)

5.4.6 Kreweras' Theorem for Dominance Systems,

327

(1)

5.4.7 Column-Strict Plane Partitions: Fixed Shape,

327

(1)

5.4.8 Young Tableaux: Fixed Shape,

327

(1)

Notes and References

328

(1)

Exercises

328

(2)

5.5 A q-Analogue of the Lagrange Theorem

330

(9)

5.5.1 Decomposition (Additive (for Sequences)),

330

(2)

5.5.2 A Proof of the Lagrange Theorem,

332

(1)

5.5.3 Proposition,

332

(1)

5.5.4 Theorem (q-Lagrange),

333

(2)

5.5.5 Corollary,

335

(1)

5.5.6 Lead Codes,

336

(1)

Notes and References

337

(1)

Exercises

337

(2)

SOLUTIONS

339

(203)

Chapter 1

339

(11)

Chapter 2

350

(64)

Chapter 3

414

(43)

Chapter 4

457

(56)

Chapter 5

513

(29)

References

542

(11)

Index

553

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Combinatorial Enumeration

Summary

Table of Contents

Supplemental Materials