Foreword
Preface
Contents
1: Introduction
The Binary Decomposition Model
Counting by Characterization
Words Over an Alphabet
Some Notation
2: Dyck Words
Definition 2.1
Theorem 2.1
Bertrandยดs Ballot Problem
Corollary 2.1
Counting Paths
Monotonic Paths
Dyck Paths
3: The Catalan Numbers
Definition 3.1
Corollary 3.1
Basic Properties of the Catalan Numbers
Theorem 3.1
Integral Representation
Theorem 3.2
Recurrence Relation and Generating Function
Generating Function
Theorem 3.3
Theorem 3.4
4: Catalan Numbers and Paths
Monotone Paths
Theorem 4.1
Dyck Paths
Theorem 4.2
Path Summary
Theorem 4.3
5: Catalan Numbers and Trees
Ordered Trees
Theorem 5.1
Binary Trees
Theorem 5.2
Full Binary Trees
Theorem 5.3
Noncrossing, Alternating Trees
Theorem 5.4
Tree Summary
Theorem 5.5
6: Catalan Numbers and Geometric Widgits
Nonintersecting Chords
Theorem 6.1
Tilings of a Staircase
Theorem 6.2
Noncrossing, Alternating Chords
Theorem 6.3
Triangulations of a Convex Polygon
Theorem 6.4
Disk Stacking
Theorem 6.5
Geometric Widgit Summary
Theorem 6.6
7: Catalan Numbers and Algebraic Widgits
Correct Parenthesizing Under a Nonassociative Binary Operation
Theorem 7.1
Balanced Parentheses
Theorem 7.2
Theorem 7.3
Null Sums in
Theorem 7.4
Algebraic Widgit Summary
Theorem 7.5
8: Catalan Numbers and Interval Structures
Separated Families of Intervals
Definition 8.1
Theorem 8.1
Covering Antichains in Int([n])
Theorem 8.2
Antichains in Int([n-1])
Theorem 8.3
Interval Summary
Theorem 8.4
9: Catalan Numbers and Partitions
Noncrossing Partitions
Definition 9.1
Definition 9.2
Theorem 9.1
Theorem 9.2
Theorem 9.3
Theorem 9.4
Noncrossing Partitions and Davenport-Schinzel Sequences
Definition 9.3
DS Sequences and Partitions
Counting MNDS Sequences
Theorem 9.5
Theorem 9.6
Partition Summary
Theorem 9.7
10: Catalan Numbers and Permutations
Permutations Obtained from Stacks and Queues
Stack Permutations
Theorem 10.1
Theorem 10.2
Stack-Sortable Permutations
Theorem 10.3
321-Avoiding and 123-Avoiding Permutations
Definition 10.1
Theorem 10.4
Theorem 10.5
Theorem 10.6
Permutation Summary
Theorem 10.7
11: Catalan Numbers and Semiorders
The Definition of Semiorder
Definition 11.1
Definition 11.2 (Semiorder as a Special Type of Partial Order)
Characterization by Maximal Completely Indifferent Subsets
Canonical Forms for Semiordered Sets
Theorem 11.1
More on Semiorders
Characterization by Forbidden Subposet
Theorem 11.2
Characterization by Unit Interval Order
Definition 11.3
Theorem 11.3 (Scott-Suppes Theorem)
Semiorder Summary
Theorem 11.4
Recap
Theorem 1
Exercises
Paths
Trees
Geometry
Integer Sequences
Permutations
Partitions
Miscellaneous
Solutions and Hints
Appendix
A Brief Introduction to Partially Ordered Sets
Definition 1
The Product and Sum of Posets
Induced Subposets
Strict Orders
Chains and Antichains
Maximal and Minimal Elements
Upper and Lower Bounds
Topological Sorting
Down-Sets
Monotone Maps
A Brief Introduction to Graphs and Trees
Adjacency, Incidence, and Degree
Subgraphs
Walks, Trails, and Paths
Connectedness
Theorem 2
Trees
Theorem 3
Rooted Trees
Subtrees
Binary Trees
Ordered Trees
Index