combinatoricsdiscrete mathematics
Consider a path on the coordinate plane that can only move up or right. Prove that the number of such paths of length $2n$ that don't ever touch (previously read: "cross") the diagonal is $\binom{2n}n$ by a bijection.
Attempt: Tried to implement a Catalan-style proof by considering the first point it crosses the diagonal. Reflecting across the diagonal doesn't do anything, since the endpoint of a path is not necessarily $(n,n)$. I have no other ideas to attempt… Help! 🙂
The two paths enclose an array of unit squares forming a convex polyomino. (Note that in this context convex has a special meaning.) Say that the region has $m$ columns, with $c_k$ squares in column $k$. For $k=1,\ldots,m-1$ let $r_k$ be the number of rows shared by columns $k$ and $k+1$. The upper righthand corner is at the point $\langle m,n+1-m\rangle$.
The idea is to use these numbers to construct a Dyck path (mountain range) of length $2n$. It will have $m$ peaks, of heights $c_1,\ldots,c_m$ from left to right. For $k=1,\ldots,m-1$ the descent after peak $k$ will have length $c_k-r_k+1$, while the descent after peak $m$ will of course have length $c_m$. The valley between peak $k$ and peak $k+1$ will have height $c_k-(c_k-r_k+1)=r_k-1$, so the ascent from it to peak $k+1$ will have length $c_{k+1}-r_k+1$.
Now $c_{k+1}-r_k$ is the number of squares by which the top of column $k+1$ rises above the top of column $k$, so
$$c_1+\sum_{k=1}^{m-1}(c_{k+1}-r_k)+c_m$$
is the height above the baseline of the top of column $m$, which is $n+1-m$, and
$$c_1+\sum_{k=1}^{m-1}(c_{k+1}-r_k+1)+c_m=n+1-m+(m-1)=n\;,$$
as desired.
I leave it to you to check that the total descents is also $n$, that the path never drops below the baseline, and that the convex polyomino and hence the original two paths can be recovered from the Dyck path.
There are a few ways to solve this question, each of which uses a different, but very useful, counting principle. We wish to count the paths that stay weakly below the line $y=x$ (they can touch the line, but not go above)
1) Reflection Principle
First, we consider the total number of paths that exist from $(0,0)$ to $(n,n)$, which is ${2n}\choose{n}$, since we must take exactly $n$ up steps, each of which we denote by a $u$, and $n$ right steps, each of which we denote by an $r$, and so this simply corresponds to the ${2n}\choose{n}$ ways we can rearrange a string with $n$ $u$s and $n$ $r$s.
Next, we consider the paths that DO go above the line $y=x$ (the bad paths). We note that for each such path, there exists a unique first upstep that brings the path above the line (it could even be the first step). We draw a line of slope $1$ passing through the end of this unique up step, and reflect the path up to that step about the line, giving a path from $(-1,1)$ to $(n,n)$. (See picture)
Now, we've shown that any bad path can be mapped onto a path from $(-1,1)$ to $(n,n)$. It is indeed true (but you should convince yourself of this) that any path from $(-1,1)$ to $(n,n)$ can be mapped onto a bad path from from $(0,0)$ to $(n,n)$. Hence, there are the same number of bad paths from from $(0,0)$ to $(n,n)$ as the number of all paths from $(-1,1)$ to $(n,n)$, which by the argument above is ${2n}\choose{n-1}$=${2n}\choose{n+1}$.
Hence the number of paths that stay below the line $y=x$ is (after some manipulation): $${{2n}\choose{n}} - {{2n}\choose{n-1}}=\dfrac{1}{n+1}{{2n}\choose{n}}$$
2) Generating Functions
If you are comfortable with generating functions, we can let $g(x)$ be the generating function for paths that stay below the line $y=x$. Let us call paths that stay below the line good paths. Then we can note that each path that is below the line $y=x$ can be broken into two after the first return to the axis.
Now if we let $x^{1/2}$ be the weight of each step, then the first part of the path can be written as $x g(x)$, as it is a right step ($x^{1/2}$), followed by a good path ($g(x)$), followed be an up step ($x^{1/2}$). The second part of the path is just another good path ($g(x)$). The only path that cannot be written this way is the lone good path that does not start with a right step, namely, the empty path from $(0,0)$ to $(0,0)$, who's generating series is just $x^0=1$. Hence we have that $$g(x) = x g(x) \cdot g(x)+1=x g(x)^2+1 $$
Solving for $g(x)$ gives: $$g(x) = \dfrac{1 \pm \sqrt{1-4x} }{2x}$$
One can then use the generalized binomial theorem to find the series:
$$g(x) = \sum_{n=0}^{\infty} a_n x^n$$
and you should get $a_n = \dfrac{1}{n+1} {{2n}\choose{n}}$, and of course by our construction, $a_n$ counts the good paths from $(0,0)$ to $(n,n)$.
3) Cycle Lemma
Using the Cycle Lemma (http://www.cs.tau.ac.il/~nachumd/papers/CL.pdf) one can map the good paths from $(0,0)$ to $(n,n)$ to dominating strings of $n+1$ $0$s and $n$ $1$s, where $0$s represent right steps and $1$s represent up steps. The cycle lemma tells us that of the $2n+1$ cyclic permutation of each such possible string, only $(n+1)-n=1$ of them are dominating. and hence since there are ${2n+1}\choose{n}$ possible strings, the total number of dominating strings, which corresponds to the good paths, is:
$$\dfrac{1}{2n+1} {{2n+1}\choose{n}} = \dfrac{1}{n+1} {{2n}\choose{n}}$$
Best Answer
There is a natural bijection between these paths and paths of length $2n$ that start at $\langle 0,0\rangle$, move in up-steps from $\langle x,y\rangle$ to $\langle x+1,y+1\rangle$ and down-steps from $\langle x,y\rangle$ to $\langle x+1,y-1\rangle$, and never drop below the $x$-axis. I find it easier to think in terms of these ‘mountain’ paths, so I’ll work with them.
I’ll describe the bijection that I found a few years ago in another context, but I’ll warn you that it’s pretty ugly. I’ll describe one direction and for now leave it to you to verify that what I’ve described really is a bijection.
Clearly there are $\binom{2n}n$ such paths of length $2n$ that end at $\langle 2n,0\rangle$, so we want a bijection between those paths and the paths of length $2n$ that do not hit the $x$-axis after leaving $\langle 0,0\rangle$. Let $P$ be a path of length $2n$ that ends at $\langle 2n,0\rangle$. If $P$ never drops below the $x$-axis, let $P'=P$. Otherwise, let $-m<0$ be the minimum $y$-coordinate of any point on $P$, and let $\langle h,-m\rangle$ be the first point on $P$ at height $-m$. Construct a new path $P'$ as follows.
Let the $k$-th step of $P$ be to $\langle k,y_k\rangle$ and the $k$-th step of $P'$ be to $\langle k,y_k'\rangle$. The first $n-h$ steps of $P'$ mimic the last $2n-h$ steps of $P$: for $k=1,\ldots,2n-h$, $y_k'=y_{h+k}$. Pictorially speaking, we’ve taken the graph of $P$ to the right of $x=h$ and moved it $h$ units to the left and $m$ units up, so that it starts at the origin. Clearly this segment of $P'$ ends at $\langle 2n-h,m\rangle$. Complete $P'$ by reflecting the part of $P$ to the left of $x=h$ in the line $y=-m$, so that it starts at $\langle 0,-2m\rangle$ and ends at $\langle h,-m\rangle$, raising it $3m$ units to start at $\langle 0,m\rangle$ and end at $\langle h,2m\rangle$, and shifting it $2n-h$ units to the right to start at $\langle 2n-h,m\rangle$ and end at $\langle 2n,2m\rangle$. In other words, for $k=1,\ldots,h$, $y_{2n-h+k}'=m-y_k$. If $y_k'>0$ for $k=1,\ldots,2n$, let $\widehat P=P'$; $\widehat P$ lies entirely above the $x$-axis after it leaves the origin.
Otherwise, let $j$ be minimal such that $y_j'=0$; clearly $y_{j-1}'=1$, since the $j$-th step must have been a down-step. Change that to an up-step and leave the remaining sequence of up- and down-steps as is; this simply replaces $y_k'$ by $y_k'+2$ for $k=j,\ldots,2n$ and results in a path $P''$ from $\langle 0,0\rangle$ to $\langle 2n,2m+2\rangle$ that lies strictly above the $x$-axis after leaving the origin. Finally, let $\widehat P$ be the reflection of this path in the $x$-axis; $\widehat P$ lies strictly below the $x$-axis after leaving the origin and ends at $\langle 2n,-2m-2\rangle$.
You shouldn’t have too much trouble verifying that the mapping $P\mapsto\widehat P$ is injective, but you may have to work a bit to show that every path that never hits the $x$-axis after leaving the origin is $\widehat P$ for some $P$ that ends at $\langle 2n,n\rangle$.