2
$\begingroup$

I did a lot of research on Catalan Numbers and I came across one interesting fact that the nth Catalan numbers never exceeds the nth Bell number. I know that the nth bell numbers counts the number of partitions of a set with n elements.

My question is : Is there an easy way to prove that the nth Catalan number never exceeds the nth Bell number ? or is there an easy way to see it (with out even proof)

$\endgroup$
1
  • $\begingroup$ Both have a representation in terms of the factorial function.... perhaps Stirling's Approximation would help? $\endgroup$ Dec 12 '15 at 22:37
4
$\begingroup$

Among the many things counted by the $n$th Catalan number is the number of non-crossing partitions of an ordered set of $n$ elements.

Since every non-crossing partition is, in particular, a partition, the number of non-crossing partitions cannot exceed the number of partitions, which is the $n$th Bell number.


More concretely, here is a way to encode a Dyck word of length $2n$ as a partition of $\{1,2,\ldots,n\}$: Split the Dyck words up into $n$ groups of two symbols, and substitute each group as follows: $$ \begin{align} \mathtt{((} &\mapsto \mathtt{[*} \\ \mathtt{))} &\mapsto \mathtt{*]} \\ \mathtt{()} &\mapsto \mathtt{[*]} \\ \mathtt{)(} &\mapsto \mathtt{*} \end{align} $$

The result of this substitution is a string with $n$ instances of $\mathtt{*}$ and some well-nested square brackets such that every $\mathtt{*}$ is inside at least one set of square brackets.

Each $\mathtt{*}$ represents one of the base element $\{1,2,\ldots,n\}$, and there will be one set in the partition for each set of square brackets, containing exactly those stars that are within the brackets and not within any internal set of brackets. The rules guarantee that each of the sets is non-empty.

This representation is unique: If we're given a partition that comes from this process we can reconstruct the Dyck word it comes from uniquely: Go through the base set $\{1,2,\ldots,n\}$ from left to right and follow these rules:

  • If you're looking at the only element in some set, put down $\mathtt{()}$.
  • If you're looking at the smallest element in some set, put down $\mathtt{((}$.
  • If you're looking at the largest element in some set, put down $\mathtt{))}$.
  • If you're looking at an element that is neither smallest nor largest in its set, put down $\mathtt{)(}$.

(A non-crossing partition of $\{1,2,\ldots,n\}$ is exactly one that can be produced by this construction.)

$\endgroup$
3
  • $\begingroup$ I actually read about that yes, But can you please give a simple definition and example of what it means to be a non-crossing partition, The wikipedia definition makes me confused $\endgroup$
    – alkabary
    Dec 12 '15 at 22:50
  • $\begingroup$ @alkabary: I've tried to edit with a more concrete description. $\endgroup$ Dec 12 '15 at 23:10
  • 1
    $\begingroup$ @alkabary: Imagine that $1,\ldots,n$ label the vertices of a regular $n$-gon in order, and you have a partition of those vertices. Let $P$ and $Q$ be two parts of the partition. The parts $P$ and $Q$ cross if there are $i,j\in P$ and $k,\ell\in Q$ such that the diagonals $ij$ and $k\ell$ intersect. A crossing partition of the vertices is one that has two parts that cross. Every other partition is a non-crossing partition. $\endgroup$ Dec 13 '15 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.