Combinatorial Enumeration,9780486435978

Combinatorial Enumeration

by ;
ISBN13: 9780486435978
ISBN10: 0486435970
Format: Paperback
Pub. Date: 2004-06-23
Publisher(s): Dover Publications
List Price: $39.88

Buy New

Usually Ships in 5-7 Business Days
$37.98
Add to Cart

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $99.00

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

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

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.