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)
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:
(A non-crossing partition of $\{1,2,\ldots,n\}$ is exactly one that can be produced by this construction.)