Generalized Catalan Numbers

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.

• As you can read in the answer by A.Schulz and its OEIS link for length $N$ there are $2^N$ as many properly nested words on two bracket pairs compared to Catalan. Be careful how to define those words. If you only test subwords on each of the bracket pairs separately, you might end up with ([)] which probably is not what you want? Nov 9, 2012 at 17:00
• The question is a little bit ambiguous. Are these the pairs that you want to count for $N=2$? (()), [()], ([]), [[]], ()(), [](), ()[], and [][]. Nov 9, 2012 at 19:09
• Hi Brian. No not exactly. In your set for N=2: The following are OK: (()), [()], ([]), [[]] The other ()(), [](), ()[], [][] are not because you have always balanced initial sub words. For example in this one ()[] you have the balanced initial subword (). Maybe 2 things are no clear in my first question: 1) I ask that in any INITIAL subword (and not any subword) there is at least one pair of symbols which are not balanced. 2) I realize that it's not exactly linked to Catalan number as is but quite the same, just a shift of index. Hope it's less ambiguous Gianfranco Nov 10, 2012 at 16:45
• 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". Mar 4, 2013 at 6:06

1 Answer

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.

• 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 again Nov 9, 2012 at 17:19