Take the 2-minute tour ×
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.

Preliminaries

There are many equivalent definitions of the Catalan Numbers. I'll use this one:

A Dyck Word is a string consisting on $n$ X's and $n$ Y's such that no initial segment of the string has more Y's than X's. For example, XXYYXY is a Dyck Word, but XXYYYX is not, because of the leading substring XXYYY. The $n^{th}$ Catalan number $C_n$ is equal to the number of Dyck Words of length $2n$.

There are a number of well-known formulas for computing the Catalan numbers. One is $C_n = \frac{1}{n+1} {2n \choose n}$.

My Question

I want to generalize the Catalan Numbers as follows: Suppose a Dyck Word is allowable if no leading substring has $k$ or more Y's than X's. Then $D^k_n$ gives the number of (modified) Dyck Words of length $2n$. So $C_n = D^1_n$.

What is a formula for $D^k_n$?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Your generalized Catalan numbers have a combinatorial interpretation. Just as the Dyck words encode Dyck paths, your generalized Catalan numbers $D_n^k$ is the number of Dyck-like paths which lie at most $k-1$ steps below the $x$-axis.

Therefore $D_n^2$ is the number of paths from $(0,\ 0)$ to $(2n,\ 0)$ which lie above $y=-1$. From the reflection principle for lattice paths, if we have a path which at some point intercepts $y=-k$ then the number of such paths is equal to the number of paths which end at $(2n,\ -2k)$. Therefore the number of such paths is $\binom{2n}{n-k}$.

The number of paths which lie above $y=-1$ can then be seen as composed of the following groups $$\{\text{# paths above $y=0$}\} + \{\text{# paths intercepting $y=-1$}\} - \{\text{# paths intercepting $y=-2$}\}$$ which gives $$D_n^2 = D_n^1 + \binom{2n}{n-1} - \binom{2n}{n-2}$$ This is a shifted Catalan number as helopticor has noticed. For $D_n^3$, we similarly have $$D_n^3 = D_n^1 + D_n^2 + \binom{2n}{n-2} - \binom{2n}{n-3} = D_n^1 + \binom{2n}{n-1} - \binom{2n}{n-3}$$ You can verify that continuing in this manner, the full generalization is $$D_n^k = \binom{2n}{n} - \binom{2n}{n-k}$$

share|improve this answer

We can modify the standard recursion satisfied by the Catalan numbers.

First, consider the case $k=2$. A $k=2$ word is either already a Dyck word (which can happen in $D^1_n$ ways), or there's a first place where there are more Ys than Xs. In the latter case, the word looks like $w_1YXw_2$ where $w_1$ is a Dyck word (since we're referring to the first place where Ys overtake Xs) and $w_2$ is any $k=2$ word of the appropriate size (since the Xs and Ys have been evened out before w_2). Thus, $D_{n}^{2}=D_{n}^{1}+\sum_{i=0}^{n-1}D_{i}^{1}D_{n-1-i}^{2}$. Notice that if we define $D_{-1}^{2}=1$, this is really the recursion for the Catalan numbers, with a shift, so that $D_{n}^{2}=D_{n+1}^{1}$, but that fact won't generalize, so we press on.

For $k>2$, either the word is actually a $k-1$ word, or there's a first place where the word gets maximum initial Ys. I had wanted to say "so it begins with a $k-1$ word that is not a $k-2$ word, followed by YX" to get the recursion $D_{n}^{k}=D_{n}^{k-1}+\sum_{i=0}^{n-1}(D_{i}^{k-1}-D_{i}^{k-2})D_{n-1-i}^{k}$ for $k\ge2$ if we follow the convention that $D_{n}^{0}=0$". But that's flawed, because a $k-1$ word ends with enough Xs to cancel out any initial Ys. (Incidentally, for $k=3$ anyway this potentially incorrect sequence seems to be a Catalan transform of the fibonacci numbers as listed on OEIS.)

Edit: Upon thinking things over some more, I found an uglier recursion for $k=3$ manually. As before, either the word is a $k=2$ word (so a count of $D_{n}^{2}$), or it has an initial string with two un-Xed Ys in a row. The first time this happens, it may be a YYXX, so we have $w_1$YYXX$w_2$ where $w_1$ is a $k=2$ word and $w_2$ is a $k=3$ word. However, it may be that the first time this happens we have YYXYXX, or YYXYXYXX, etc. If $i$ is the number of intervening "XY"s, then we can sum over $i$ to get all of the possibilities: $D_{n}^{3}=D_{n}^{2}+\sum_{i=0}^{n-2}\sum_{j=0}^{n-2-i}D_{j}^{2}D_{n-2-i-j}^{3}$. This appears to be the second differences of the Catalan numbers.

The problem is that for $k$ beyond three this gets very hairy very fast, so I'd hope there's a better approach that can get something that works for all k. My bet is that maybe some recursion can be gotten by adding another parameter to allow partial modified Dyck words to be counted, as that's what needs to be done inside of YYYX...X for the $k=4$ case. I don't have any more insight right now.

share|improve this answer

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.