Combinatorial Enumeration

by Goulden, Ian P.; Jackson, David M.

• ISBN13: 9780486435978
• ISBN10: 0486435970
• Format: Paperback
• Copyright: 2004-06-23
• Publisher: Dover Publications

Summary

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.

Table of Contents

Notation	xxiii
1 MATHEMATICAL PRELIMINARIES
1.1 The Ring of Formal Power Series
1.1.1 Formal Power Series,	1	(1)
1.1.2 The Coefficient Operator,	1	(1)
1.1.3 Infinite Sums and Products,	2	(1)
1.1.4 Compositional and Multiplicative Inverses,	2	(1)
1.1.5 The Formal Derivative and Integral,	3	(1)
1.1.6 The Logarithmic, Exponential, and Binomial Power Series,	4	(3)
1.1.7 Circular and Hyperbolic Power Series,	7	(1)
1.1.8 Formal Differential Equations,	8	(1)
1.1.9 Roots of a Power Series,	9	(1)
1.1.10 Matrices Over the Ring of Formal Power Series,	10	(1)
1.1.11 Formal Laurent Series,	11	(1)
Notes and References	12	(1)
Exercises	12	(3)
1.2 The Lagrange Theorem for Implicit Functions	15	(14)
1.2.1 Proposition,	15	(1)
1.2.2 Theorem (Residue Composition),	15	(1)
1.2.3 An Identity (by Residue Composition),	16	(1)
1.2.4 Theorem (Lagrange),	17	(1)
1.2.5 A Functional Equation,	18	(1)
1.2.6 The Central Trinomial Numbers,	19	(1)
1.2.7 Abel's Extension of the Binomial Theorem,	19	(1)
1.2.8 Theorem (Multivariate Residue Composition),	19	(2)
1.2.9 Theorem (Multivariate Lagrange),	21	(1)
1.2.10 A Functional Equation in Two Variables,	22	(1)
1.2.11 Theorem (MacMahon Master Theorem),	23	(1)
1.2.12 Dixon's Identity,	23	(2)
1.2.13 Corollary (Lagrange Theorem for Monomials),	25	(1)
Notes and References	26	(1)
Exercises	26	(3)
2 THE COMBINATORICS OF THE ORDINARY GENERATING FUNCTION	29	(129)
2.1 Introduction	29	(2)
2.1.1 The Elementary Counting Lemmas,	29	(1)
2.1.2 Decompositions and Weight Functions,	30	(1)
2.1.3 Direct and Indirect Decompositions, Combinatorial Marking, and Multivariate Generating Functions,	30	(1)
2.1.4 A Classical Application of Enumerative Arguments,	31	(1)
2.1.5 Recursive and "At-Least" Decompositions,	31	(1)
2.2 The Elementary Counting Lemmas	31	(17)
2.2.1 Definition (Distinguishability),	32	(1)
2.2.2 Definition (Weight Function, Weight),	32	(1)
2.2.3 Remark (The General Enumerative Problem),	32	(1)
2.2.4 Example (Enumerative Problems),	32	(1)
2.2.5 Definition (Ordinary Generating Function),	33	(1)
2.2.6 Remark (s-Objects),	33	(1)
2.2.7 Example (a Generating Function),	33	(1)
2.2.8 Proposition,	34	(1)
2.2.9 Definition (Decomposition, ω-Preserving),	34	(1)
2.2.10 Proposition,	34	(1)
2.2.11 Example (Terquem Problem: Decomposition),	35	(1)
2.2.12 Lemma (Sum),	36	(1)
2.2.13 Example (Sum),	36	(1)
2.2.14 Lemma (Product),	36	(1)
2.2.15 Example (Terquem Problem: Generating Function),	37	(1)
2.2.16 Definition (Additively Weight-Preserving Decomposition),	38	(1)
2.2.17 Remark (Direct, Indirect, Recursive Decompositions),	39	(1)
2.2.18 Example (an Indirect Decomposition),	39	(1)
2.2.19 Example (a Recursive Decomposition),	40	(1)
2.2.20 Definition (Composition),	41	(1)
2.2.21 Example (Composition),	41	(1)
2.2.22 Lemma (Composition),	42	(1)
2.2.23 Example (Composition),	43	(1)
2.2.24 Definition (s-Derivative),	44	(1)
2.2.25 Example (s-Derivative of a Set of Permutations),	44	(1)
2.2.26 Lemma (Differentiation),	45	(1)
2.2.27 Example (s-Derivative),	45	(1)
2.2.28 Definition ("Exact," "At-Least" Generating Functions),	46	(1)
2.2.29 Lemma (the Principle of Inclusion and Exclusion),	47	(1)
2.2.30 Example (Derangements),	48	(1)
Notes and References	48	(1)
2.3 Preliminary Examples	48	(14)
2.3.1 Decomposition (Subsets),	48	(1)
2.3.2 Subsets,	49	(1)
2.3.3 Recurrence Equation for Binomial Coefficients,	49	(1)
2.3.4 Decomposition (Multisets),	50	(1)
2.3.5 Multisets,	50	(1)
2.3.6 Definition (Composition of an Integer),	51	(1)
2.3.7 Decomposition (Compositions of an Integer),	51	(1)
2.3.8 Compositions of an Integer,	51	(1)
2.3.9 Correspondence (Multisets-Compositions),	52	(1)
2.3.10 Compositions and Parts,	53	(1)
2.3.11 Recurrence Equation for Compositions and Parts,	53	(1)
2.3.12 An Identity from Compositions,	54	(1)
2.3.13 Definition (Succession in a Set),	54	(1)
2.3.14 Decomposition (Subsets),	55	(1)
2.3.15 Subsets with Successions,	55	(1)
2.3.16 Definition (Skolem Subsets),	55	(1)
2.3.17 Decomposition (Skolem Subsets),	56	(1)
2.3.18 The Skolem Problem,	56	(1)
2.3.19 Definition (Circular Succession),	56	(1)
2.3.20 Decomposition (Subsets),	57	(1)
2.3.21 Example (Circular Successions),	57	(1)
2.3.22 Subsets and Circular Successions,	58	(1)
Notes and References	59	(1)
Exercises	59	(3)
2.4 Sequences	62	(18)
2.4.1 Definition (Substring, Subsequence, Block),	63	(1)
2.4.2 Definition (Maximal Block),	63	(1)
2.4.3 Decomposition ({0,1}-Sequences),	63	(1)
2.4.4 {0,1}-Sequences and Maximal Blocks of 1's,	63	(1)
2.4.5 Decomposition ({0,1}-Sequences),	64	(1)
2.4.6 {0,1}-Sequences and Maximal Blocks of 0's and 1's,	64	(1)
2.4.7 Definition (Type of a Sequence),	65	(1)
2.4.8 Sequences and Type,	65	(1)
2.4.9 Sequences and Type Restrictions,	65	(1)
2.4.10 Compositions and Part Restrictions,	66	(1)
2.4.11 Remark (Sequences and Compositions),	67	(1)
2.4.12 Ordered Factorizations,	67	(1)
2.4.13 Definition (Rise, Level, Fall),	68	(1)
2.4.14 Definition (Smirnov Sequence),	68	(1)
2.4.15 Decomposition (Smirnov Sequences),	68	(1)
2.4.16 The Smimov Problem,	69	(1)
2.4.17 Sequences and Levels,	69	(1)
2.4.18 Sequences and Maximal Blocks,	70	(1)
2.4.19 Decomposition (Sequences and Falls),	71	(1)
2.4.20 The Simon Newcomb Problem,	71	(1)
2.4.21 Permutations and Falls,	72	(1)
2.4.22 Definition (Sequence with Strictly Increasing Support),	73	(1)
2.4.23 Decomposition (Sequences with Strictly Increasing Support),	73	(1)
2.4.24 Sequences of Type (2,...,2) with Strictly Increasing Support,	73	(1)
2.4.25 Definition (Dirichlet Generating Function),	74	(1)
2.4.26 Lemma (Product),	74	(1)
2.4.27 Definition (Multiplicatively Weight-Preserving Decomposition),	75	(1)
2.4.28 Ordered Factorizations and Dirichlet Generating Functions,	75	(1)
2.4.29 Remark (Sequences and Ordered Factorizations),	76	(1)
Notes and References	76	(1)
Exercises	76	(4)
2.5 Partitions of an Integer	80	(16)
2.5.1 Definition (Partition),	80	(1)
2.5.2 Decomposition (Partitions),	80	(1)
2.5.3 The Number of Partitions,	81	(1)
2.5.4 Example (Calculation of ρ(6)),	81	(1)
2.5.5 Distinct Parts,	81	(1)
2.5.6 Largest Part Exactly m,	82	(1)
2.5.7 Definition (Conjugate),	82	(1)
2.5.8 Decomposition (Partitions with Given Largest Part),	82	(1)
2.5.9 All Partitions-Euler's Theorem,	82	(1)
2.5.10 Definition (Ferrers Graph, Durfee Square),	83	(1)
2.5.11 Definition (Abutment),	84	(1)
2.5.12 Decomposition (All Partitions),	84	(1)
2.5.13 All Partitions-q-Analogue of Kummer's Theorem,	85	(1)
2.5.14 All Partitions-Euler's Theorem,	85	(1)
2.5.15 Definition-Maximal Triangle,	86	(1)
2.5.16 Decomposition (Partitions with Distinct Parts),	86	(1)
2.5.17 Partitions with Distinct Parts-An Identity,	86	(1)
2.5.18 Partitions with Distinct Parts-Euler's Theorem,	87	(1)
2.5.19 Decomposition (Self-conjugate Partitions),	87	(1)
2.5.20 Decomposition (Self-conjugate Partitions),	88	(1)
2.5.21 Self-conjugate Partitions-An Identity,	88	(1)
2.5.22 Self-conjugate Partitions-Euler's Theorem,	89	(1)
2.5.23 Decomposition (Sylvester: All Partitions),	89	(2)
2.5.24 The Jacobi Triple Product Identity,	91	(1)
2.5.25 Euler's Theorem for Pentagonal Numbers,	92	(1)
Notes and References	93	(1)
Exercises	93	(3)
2.6 Inversions in Permutations and q-Identities	96	(13)
2.6.1 Definition (Inversion),	96	(1)
2.6.2 Algorithm (Inversion),	96	(1)
2.6.3 Proposition,	97	(1)
2.6.4 Lemma (Inversions),	97	(1)
2.6.5 Example (Between-Set and Within-Set Inversions),	98	(1)
2.6.6 Lemma (Between-Set and Within-Set Generating Functions),	98	(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