This textbook provides an introduction to the Catalan numbers and their remarkable properties, along with their various applications in combinatorics. Intended to be accessible to students new to the subject, the book begins with more elementary topics before progressing to more mathematically sophisticated topics. Each chapter focuses on a specific combinatorial object counted by these numbers, including paths, trees, tilings of a staircase, null sums in Zn 1, interval structures, partitions, permutations, semiorders, and more. Exercises are included at the end of book, along with hints and solutions, to help students obtain a better grasp of the material. The text is ideal for undergraduate students studying combinatorics, but will also appeal to anyone with a mathematical background who has an interest in learning about the Catalan numbers. “Roman does an admirable job of providing an introduction to Catalan numbers of a different nature from the previous ones. He has made an excellent choice of topics in order to convey the flavor of Catalan combinatorics. [Readers] will acquire a good feeling for why so many mathematicians are enthralled by the remarkable ubiquity and elegance of Catalan numbers.” - From the foreword by Richard Stanley 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
