Generalizing Catalan numbers: number of ways where we cross the diagonal $k$ times.

Question

Let's say we have a square grid with n steps each. One starts at the lower left corner, takes $2n$ steps; $n$ of them to the right and $n$ of them to the upwards and ends up at the upper right corner. If we want to count the number of paths that don't cross the main diagonal and stay on a particular side of it, we get the Catalan numbers, $C_n=\frac{2n \choose n}{(n+1)}$. Accounting for both sides, the total paths that don't cross the main diagonal then become $2 C_n$. A natural question to ask is: how many paths cross the main diagonal exactly $k$ times? Let's call this number $R_{k,n}$. I want to find a closed-form expression for $R_{k,n}$. Obviously, $R_{0,n}=2C_n$

---

My attempt and some thoughts

The question here: Using the Catalan numbers provides a warm-up. Both @joriki and @robjohn calculate the number of paths that have a segment that is positive (possibly empty) followed by a segment that is negative (possibly empty). Let's denote this sequence, $G_n$ as joriki does. They do this by noting that conditional on some cut-off point, we simply get two Catalan sequences. Hence, the number of such paths becomes the convolution of the Catalan numbers with themselves. joriki notes that this sequence will have a generating function that is the square of the generating function of the Catalan numbers. He uses this to determine that it is simply the $n+1$th Catalan number. Another way to go about finding this would have been to use the general formula here: Proof of identity about generalized binomial sequences. with $k=2$. The two yield the same answer. This can be used to get $R_{1,n}$ per the following equation (we divide $R_{1,n}$ by 2 because the sequence only considers paths which were negative first and then positive while $R_{1,n}$ includes sequences that were positive first):

$$G_n=C_{n+1}=2C_n+\frac{R_{1,n}}{2}$$ $$=> R_{1,n}=2C_{n+1}-4C_n$$

Now, can we apply this "convolution trick" to get $R_{k,n}$?

One way is to consider paths that have three sections. They start off with a section (possibly empty) below the main diagonal. Then, they cross it and there is a section (possibly empty) above the main diagonal. Then, they cross it again and there is a third section (possibly empty) that stays below the main diagonal. Unlike before, there are two cut-off points and it seems we have a three-way convolution of the Catalan numbers with themselves. The first thought is that the number of such paths (say $H_n$) will have a generating function that is the cube of that of the Catalan numbers. And if we increase the number of segments further, we get higher and higher powers of the generating function. But this can't be right since as we keep increasing the number of such segments, the number of paths should keep increasing per equation (5.70) here: Proof of identity about generalized binomial sequences.. In reality, we'll reach an upper bound at some point when we simply cover all ${2n \choose n}$ paths. So, what is the error in the "three way convolution leading to a generating function becoming the cube of the Catalan number generating function" argument? One resolution might be that the argument is fine, but increasing the cut-off points starts double and triple counting the paths.

Answer 1

Instead of allowing possibly empty sections, we split a path at points of crossing the diagonal, and ignore possible touch points (where the path goes from above/below and bounces back). This gives $$R_{0,n}=2C_n,\qquad R_{k,n}=\sum_{m=1}^{n-1}C_m R_{k-1,n-m}\qquad(k,n>0)$$ ($R_{0,n}$ counts "Catalan" $n$-paths above/below the diagonal (not strictly); to get an $(k,n)$-path, we take an $(k-1,n-m)$-path and append a "Catalan" $m$-path which extends the last step). Then, in the notation of your question, $$R_{k}(z):=\sum_{n=1}^{\infty}R_{k,n}z^n=2\big(B_2(z)-1\big)^{k+1}=2z^{k+1}B_2(z)^{2k+2}.$$ Using the identity $(5.70)$ from the question, we get $$R_{k-1}(z)=2z^k\sum_{t=0}^{\infty}\binom{2t+2k}{t}\frac{2k}{2t+2k}z^t\underset{n:=t+k}{\quad=\quad}2\sum_{n=k}^{\infty}\binom{2n}{n-k}\frac{k}{n}z^n,$$ that is, $R_{k-1,n}=\frac{2k}{n}\binom{2n}{n-k}$ for $1\leqslant k\leqslant n$.

Answer 2

I don't have a closed form yet, but I did manage to extend @joriki's answer here: Using the Catalan numbers to find a recurrence that is $k$ in length.

Joriki noted that if we assume one cut-off point where the path crosses the main diagonal, we get a convolution of the Catalan numbers with themselves with generating function the square of the Catalans. We can extend this and say that if there are $k$ cut-off points, we get the convolution of the Catalan numbers with themselves $k+1$ times and the generating function becomes that of the Catalan numbers raised to the power $(k+1)$. We know a lot about this generating function via the answer here: Proof of identity about generalized binomial sequences.. Let's call $C_n^{(k)}$ the $n$th element of the sequence resulting from raising the Catalan generating function to the power $k$. From the second link, we know:

$$C_n^{(k)} = {2n+k \choose n} \frac{k}{2n+k} \tag{1}$$

The catch is that the segments formed by the cut-off points can be empty. So, we have to account for the empty segments causing double and triple counting in the expression above.

For example, consider $n=3$, $k=2$. Now, $C_3^{(2+1)}$ will include:

1. Paths where all of the orange, green and blue segments in the figure below survive.
2. Paths where two of the three segments survive.
3. Paths where just one of the three segments survive.

For example, if only the green and orange segments in the figure below are to survive, we move the two points at the ends of the green segment together. If the blue is to survive, we move the two points forming the green segment all the way to the left. If we choose a set of segments to survive, we can always make it happen in a unique way by moving the points appropriately. It's just a matter of choosing which segments survive. When there are two cut-off points, either none of the segments will survive, or two of them will survive (choose 2 out of 3) or one will survive (choose 1 out of 3).

$$2 C_3^{(2+1)} = {3 \choose 1} R_{0,3}+{3 \choose 2}R_{1,3}+{3 \choose 3}R_{2,3}\tag{2}$$

Where we added a $2$ to the LHS because of the symmetry of paths above and below the main diagonal.

From the expression in the question:

$$R_{1,3}=2C_4-4C_3$$

we get $R_{1,3}=8$ and $R_{0,3}=2C_3=10$. Plugging into the equation above and computing the LHS using (1), we get $R_{2,3}=2$. And it is very easy to see this is true. In fact, $R_{n-1,n}=2$ since we get only two zig-zag paths, one that starts above and one below the main diagonal. We can generalize equation (2) as follows:

$$2C_{n}^{(k+1)} = \sum\limits_{j=0}^{k}{k+1 \choose j+1}R_{j,n} \tag{3}$$