Generalized Catalan Numbers

665 Views Asked by At

I'm concerned here with Catalan numbers.

There are many combinatorial interpretation of these numbers. Here I would focus on the interpretation around words build with 2 symbols, let say [ and ]. The Nth Catalan number for such pair of symbols gives the number of words of length 2N such that any sub words never contains more [ than ].

I'm interested what we can say if we take not only 2 symbols but 4 for example. Let say [, ] and (, ).

Then Nth "Generalized" Catalan number would be interpreted as the number of words of length 2N build with these 4 symbols such that any sub word is, let say "simple Catalan" for the pair [,], or "simple Catalan" for the pair (,) or both. In other words for any sub words, there is a pair of symbols which are "simple Catalan" for this sub word.

Hope I'm clear enough.

1

There are 1 best solutions below

1
On

For two different types of parenthesis this the sequence is listed in the OEIS here.

Words with balanced $k$-type parentheses are known as $\text{Dyck}(k)$ words. Maybe this helps for further investigations.