2
$\begingroup$

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.

  • 0
    Unless you restate this question more clearly, you will not get any satisfactory answers. You never define what property defines "simple Catalan" for one pair of symbols, but assuming this means "balanced after throwing out all all symbols not belonging to that pair", you are allowing things like ][][()() because, even though it is nonsense for [,], is "simple Catalan" for (,). You said "or", not "and".2013-03-04

1 Answers 1

2

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.

  • 0
    Thanks Shulz and Hendrik. IN fact at step 2N yes I want a balanced pattern like ([)] for example. But before 2N I don't. I mean at any step before 2N I want a pair of unbalanced symbols () unbalanced or [] unbalanced. Example: [((]))[] is not good because it's balanced for all pairs at final step but also in a previous step. [((])[)] is good, only at the end all pairs are simultaneously balanced. Thanks again2012-11-09