TITLE: Let $n ≥ 3$. Find the number of NE lattice paths from $(0, 0)$ to $(n, n)$ that touch the diagonal $y = x$ at least twice
QUESTION [4 upvotes]: Let $n ≥ 3$. Find the number of NE lattice paths from $(0, 0)$ to $(n, n)$ that touch the
diagonal $y = x$ at least twice (other than at the starting and ending points). Your final answer should not include $\sum$ but may include binomial coefficients.
My idea is to take all of the lattice paths from $(0,0)$ to $(n,n)$ and then subtract off any paths that do not touch the line $y=x$ at all and all of the paths that hit $y=x$ exactly once (other than at the end points). The number of lattice paths from $(0,0)$ to $(n,n)$ is
$$\binom{2n}{n}$$
We can see that the number of paths that never hit the line $y=x$ are simply the number of Dyck paths with $2n-2$ steps (i.e get rid of the first and last step, and you're left with a paths that are contained in the upper half-place $y \geq x+1$). Because we can either start below or above the line $y=x$ and never hit it, we have exactly
$$2C_{n-1}$$
paths that never hit the line $y=x$. To determine the number of paths that hit the line $y=x$ exactly once, we split our path into two. If we reflect the portion of the graph below $y=x$, we are left with a ballot sequence of length $2n$. We know that ballot sequences split uniquely into two ballot sequences by removing the first number and the first point at which the partial sum is exactly $0$. This leave us with two new Dyck paths, one with $2k$ steps and one with $2l$ steps, where $k+l=n-1$. The number of paths of $2k$ steps is exactly the number of Dyck paths of length $2k$ contained in the upper-half plane $y\geq x+1$, and he number of paths of $2l$ steps is exactly the number of Dyck paths of length $2l$ contained in the upper-half plane $y\geq x+1$. This is exactly
$$C_{k-1}C_{l-1}$$
If we index over all $k+l=n-1$, we recover
$$\sum_{k+l=n-1}C_{k-1}C_{l-1}$$
This is exactly the recurrence for the Catalan numbers, so by induction we see that
$$C_{n-1}=\sum_{k+l=n-1}C_{k-1}C_{l-1}$$
Because we can either start below or above the line $y=x$ and never hit it, we have exactly
$$2C_{n-1}$$
paths that hit the line $y=x$ exactly once. Thus, the number of lattice paths from $(0, 0)$ to $(n, n)$ that touch the diagonal $y = x$ at least twice (other than at the starting and ending points) is
$$\binom{2n}{n}-4C_{n-1}$$
For the simple case $n=3$, the correct answer should be $8$, but my formula doesn't yield that. Any help would be amazing!

REPLY [2 votes]: Well done. Notice that the second symmetry is not $2C_{n-1}$ but $4C_{n-1}$ because when you touch the line $x=y$ you either rebound or go to the other side. That gives $2$ possibilities and then you can either start below or above, that gives $2$ so $4.$ In that way you have $$\binom{2n}{n}-2C_{n-1}-4C_{n-1}=\binom{2n}{n}-6C_{n-1}.$$

REPLY [2 votes]: There are $2C_{n-1}$ paths that never touch the diagonal between the endpoints. A path that touches the diagonal exactly once between the endpoints, at $\langle k,k\rangle$, is the union of a Dyck path of length $k-1$ and a Dyck path of length $n-k-1$, and there are $2$ choices for each of these paths, one above and one below the diagonal. Thus, there are
$$4\sum_{k=1}^{n-1}C_{k-1}C_{n-k-1}=4\sum_{k=0}^{n-2}C_kC_{n-2-k}=4C_{n-1}$$
paths that hit the diagonal exactly once between the endpoints, and the desired number is therefore
$$\binom{2n}n-6C_{n-1}\,.$$
As a quick minimal sanity check, for for $n=2$ this is $\binom42-6C_1=0$, and for $n=3$ it is $\binom63-6C_2=20-6\cdot 2=8$, both of which are correct.
{"set_name": "stack_exchange", "score": 4, "question_id": 3867135}