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
    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?2012-11-09
  • 0
    The question is a little bit ambiguous. Are these the pairs that you want to count for $N=2$? (()), [()], ([]), [[]], ()(), [](), ()[], and [][].2012-11-09
  • 0
    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 Gianfranco2012-11-10
  • 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