I know that Dyck words are related to Catalan numbers, they actually count the Dyck words with equal number of X's and Y's.
I need to compute the cardinality of the set of strings of length k of X's and Y's such that no initial substring contains more Y's than X's. Ie. Like Dyck words but without specifying the total number of X's and Y's, but instead requiring that the sum of X's and Y's equals an integer k.
Any clever idea?
(I am assuming xxyyy, xyxyy, xyyxx etc. are invalid and xyxyx, xxxyy, xxyyx etc. are valid)
We may define a recurrence relation
\begin{align*} f(m,n)=\begin{cases} & 1 &\text{ if } m>=0, n=0 \\ & 0 &\text{ if } m=0, n>0 \lor m<n\\ & f(m-1,n)+f(m,n-1)&\text{ if } m>=n, m>0, n>0 \end{cases} \end{align*}
Then evaluate \begin{align*} S(k) &= \sum_{i=0}^k f(k-i,i) \end{align*}
From OEIS, we find that the sequence is A001405
Thus \begin{align*} S(k) &= \binom{k}{\lfloor k/2 \rfloor} \end{align*}
Update
We can get the enumeration using Chomsky-Schützenberger theorem, refer Gruber, Lee & Shallit
To summarize,
the grammar that generates the words is
\begin{align*} S &\to B \;|\; U \\ B &\to x\, B\, y\, B\; |\; \epsilon \\ U &\to x\, S \;| \;x\, B\, y\, U \\ \end{align*}
and we form the following formal power series \begin{align*} S(z) &= B(z) + U(z)\\ B(z) &= B(z)^2 z^2 + 1\\ U(z) &= S(z) z + B(z) U(z) z^2\\ \implies S(z) &= \frac{-1+2\,z+\sqrt{1-4\,z^2}}{2\,z-4\,z^2} \end{align*}
and to answer the question, we need to find $[z^k]S(z)$, which is $\dbinom{k}{\lfloor k/2\rfloor}$