Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

I'm concerned here with Cataln 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 Cataln 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.

Thanks for any idea or pointer. G.

share|improve this question
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? – Hendrik Jan Nov 9 '12 at 17:00
The question is a little bit ambiguous. Are these the pairs that you want to count for $N=2$? (()), [()], ([]), [[]], ()(), [](), ()[], and [][]. – Brian M. Scott Nov 9 '12 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 – Gianfranco OLDANI Nov 10 '12 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". – Marc van Leeuwen Mar 4 at 6:06

1 Answer

up vote 0 down vote

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.

share|improve this answer
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 – Gianfranco OLDANI Nov 9 '12 at 17:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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