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$?
Best Answer
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}$$