nach oben

2015 | Buch

Kapitel lesen Erstes Kapitel lesen

An Introduction to Catalan Numbers

verfasst von: Steven Roman

Verlag: Springer International Publishing

Buchreihe : Compact Textbooks in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract

Speaking very generally, many finitary combinatorial objects are stitched together in some orderly manner from smaller objects of the same type. For instance, the Cartesian product $ A\times B $ of two finite sets A and B is a simple example of stitching together smaller objects to make a larger object of the same type.

Steven Roman

2. Dyck Words

Abstract

The German mathematician Walther Franz Anton von Dyck (1856–1934) studied words in $ {\mathcal{W}}_{a,b} $ for $ a=b $ with the property that the -count is at all times greater than or equal to the -count, that is, for which

$$ {\Delta}_{A,B}\left({\left[w\right]}_k\right)\ge 0 $$

for all k. Those words have since become known as Dyck words.

Steven Roman

3. The Catalan Numbers

Abstract

The most important special case of Dyck words comes when $ a=b $ so that the words have the same number of dominant and nondominant letters. A slight variation on these Dyck words is ballot , which we also define here for completeness.

Steven Roman

4. Catalan Numbers and Paths

Abstract

We begin our examination of the types of objects that are counted by the Catalan numbers with paths, because the work has already been done.

Steven Roman

5. Catalan Numbers and Trees

Abstract

The Catalan numbers excel at counting a variety of types of trees. (The Appendix of this book contains a brief introduction to the subject of trees for those who are interested.)

Steven Roman

6. Catalan Numbers and Geometric Widgits

Abstract

Catalan numbers can also count a variety of geometric objects.

Steven Roman

7. Catalan Numbers and Algebraic Widgits

Abstract

Consider a binary operation defined on a set $ \mathcal{A} $ that is represented by juxtaposition. If the operation is not associative, then a word of the form abcd is not well defined unless we insert parentheses. For the word abcd, there are five ways this can be done:

$$ \begin{array}{lllll}\left((ab)c\right)d,\hfill & (ab)\;(cd),\hfill & \left(a(bc)\right)d,\hfill & a\left((bc)d\right),\hfill & a\left(b(cd)\right)\hfill \end{array} $$

We would like to count the number of ways there are to a word

$$ w={a}_1{a}_2\cdots {a}_n $$

of length n. We will assume that a full parenthesizing does not include parentheses surrounding the entire word, as in (a(bc)) or parentheses surrounding a single letter, as in a((b)c). A full parenthesization contains just enough parentheses to disambiguate the expression.

Steven Roman

8. Catalan Numbers and Interval Structures

Abstract

There are many interesting families of intervals counted by the Catalan numbers. First, however, let us make a remark about antichains in the poset Int([n]) of intervals on [n]. If $ \mathcal{A} $ is such an antichain, then no two intervals in $ \mathcal{A} $ can share a common left endpoint or a common right endpoint. Moreover, if we order the intervals so that the left endpoints are strictly increasing, then the right endpoints must also be strictly increasing. In fact, a family

$$ \mathrm{\mathcal{F}}=\left\{\left[{a}_i,{b}_i\right]\Big|1\le i\le n\right\} $$

of intervals in Int([n]) is an antichain if and only if both the left endpoint sequence $ {a}_1\cdots {a}_n $ and the right endpoint sequence $ {b}_1\cdots {b}_n $ can be ordered at the same time in strictly increasing order, in symbols, ℱ is an antichain if and only if (after reindexing if necessary)

$$ {a}_1<\cdots <{a}_n, {b}_1<\cdots <{b}_n, {a}_i\le {b}_i $$

for all i.

Steven Roman

9. Catalan Numbers and Partitions

Abstract

Catalan numbers count the number of partitions of the set [n].

Steven Roman

10. Catalan Numbers and Permutations

Abstract

We turn now to a vast subject called that is currently the subject of much research. Let S _n denote the set of all permutations of [n].

Steven Roman

11. Catalan Numbers and Semiorders

Abstract

(The Appendix of this book contains a brief introduction to the subject of partial orders for those who are interested.)

Steven Roman

Backmatter

Titel: An Introduction to Catalan Numbers
verfasst von: Steven Roman
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-22144-1
Print ISBN: 978-3-319-22143-4
DOI: https://doi.org/10.1007/978-3-319-22144-1