Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} – {2n\choose n+1}$ than Wikipedia
I do not understand the how they get ${2n\choose n+1}$ and I do not see how this is the number of monotonic paths that cross the diagonal. Please be explicit about the $n+1$ term. I think this is the hardest part for me to understand.
I understand the bijections between proper parenthesizations and so forth…
Thanks!
Best Answer
There are $\binom{2n}{n+1}$ monotonic paths from $\langle 0,0\rangle$ to $\langle n-1,n+1\rangle$: such a path must contain exactly $(n-1)+(n+1)=2n$ steps, any $n+1$ of those steps can be vertical, and the path is completely determined once you know which $n+1$ of the $2n$ steps are vertical. Every monotonic path from $\langle 0,0\rangle$ to $\langle n-1,n+1$ necessarily rises above the diagonal, since it starts on the diagonal and finishes above it. At some point, therefore, it must go from a point $\langle m,m\rangle$ on the diagonal to the point $\langle m,m+1\rangle$ just above the diagonal. After the point $\langle m,m+1\rangle$ the path must still take $(n+1)-(m+1)=n-m$ vertical steps and $(n-1)-m=n-m-1$ horizontal steps.
If you flip that part of the path across the axis $y=x+1$, each vertical step turns into a horizontal step and vice versa, so you’re now taking $n-m$ horizontal and $n-m-1$ vertical steps. You’re starting at $\langle m,m+1\rangle$, so you end up at $\langle m+(n-m),(m+1)+(n-m-1)\rangle=\langle n,n\rangle$. Thus, each monotonic path from $\langle 0,0\rangle$ to $\langle n-1,n+1\rangle$ can be converted by this flipping procedure into a monotonic path from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that has vertical step from some $\langle m,m\rangle$ on the diagonal to the point $\langle m,m+1\rangle$ immediately above it.
Conversely, every monotonic path from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that rises above the diagonal must have such a vertical step in it, and reversing the flip produces a monotonic path from $\langle 0,0\rangle$ to $\langle n-1,n+1\rangle$. Thus, this flipping procedure yields a bijection between all monotonic paths from $\langle 0,0\rangle$ to $\langle n-1,n+1\rangle$, on the one hand, and all monotonic paths from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that rise above the diagonal, on the other. As we saw in the first paragraph, there are $\binom{2n}{n+1}$ of the former, so there are also $\binom{2n}{n+1}$ of the latter. The total number of monotonic paths from $\langle 0,0\rangle$ to $\langle n,n\rangle$, on the other hand, is $\binom{2n}n$: each path has $2n$ steps, any $n$ of them can be vertical, and the path is completely determined once we know which $n$ are vertical.
The difference $\binom{2n}n-\binom{2n}{n+1}$ is therefore simply the total number of monotonic paths from $\langle 0,0\rangle$ to $\langle n,n\rangle$ minus the number that rise above the diagonal, i.e., the number that do not rise above the diagonal — which is precisely what we wanted.