Advertisement
Published in:
2015 | OriginalPaper | Chapter
8. Catalan Numbers and Interval Structures
Author : Steven Roman
Published in: An Introduction to Catalan Numbers
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 familyof 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)for all i.
$$ \mathrm{\mathcal{F}}=\left\{\left[{a}_i,{b}_i\right]\Big|1\le i\le n\right\} $$
$$ {a}_1<\cdots <{a}_n, {b}_1<\cdots <{b}_n, {a}_i\le {b}_i $$