3
$\begingroup$

Consider a grid in $\mathbb{N}_0^2$. We can draw a path in it by traveling from point to point via a horizontal line segment to the right or vertical line segment going up. Let $k,n \in \mathbb{N}$ and such that $k \leq n/2$. I try to compute the number of paths from $(0,0)$ to $(n-k,k)$ that lie (non-strictly) under the diagonal and do not cross it. (That is, they may touch a point $(i,i)$, but not $(i,i+1)$.)

I have read in an article that the solution is ${n \choose k} - {n \choose k-1}$, but I have no idea how to prove this.

$\endgroup$
  • $\begingroup$ If we forget about the restriction that we may not cross the diagonal, how many paths would then be possible? $\endgroup$ – Daniel Fischer May 6 '15 at 11:07
  • $\begingroup$ I'd say a path has length $n$ and we can choose to go up $k$ times, giving a total of ${n \choose k}$ possible paths. $\endgroup$ – Math Student 020 May 6 '15 at 11:12
  • $\begingroup$ Right. So we must now find an argument that shows that the number of paths that cross the diagonal is $\binom{n}{k-1}$. I'm not seeing a good argument yet, but I'm sure there is one. $\endgroup$ – Daniel Fischer May 6 '15 at 11:17
  • 1
    $\begingroup$ Have you looked into the Catalan numbers? They count something similar to this (walks from $(0,0)$ to $(n,n)$ that do not cross the diagonal). Can the proof be appropriately modified? $\endgroup$ – TravisJ May 6 '15 at 11:21
  • 1
    $\begingroup$ @DanielFischer Hmm, possibly one can count those based on the length of the path lying strictly above the diagonal, though I am also not seeing a nice way to do it. $\endgroup$ – Tobias Kildetoft May 6 '15 at 12:15
3
$\begingroup$

If we take a path from $(0,0)$ to $(n-k,k)$ which crosses the diagonal, it must at least touch the line $y=x+1$, so let P be the point where it first touches this line.

If we reflect the portion of the path from $(0,0)$ to P around the line $y=x+1$, we get a path from $(-1,1)$ to $(n-k,k)$.

Conversely, any path from $(-1,1)$ to $(n-k,k)$ must cross the line $y=x+1$, so if we let P be the point where the path first touches this line and reflect the portion of the path from $(-1,1)$ to P about this line, we get a path from $(0,0)$ to $(n-k,k)$ which crosses the diagonal.

Since this gives a bijection between the two types of paths, and since the number of paths from $(-1,1)$ to $(n-k,k)$ is given by $\binom{n}{k-1}$, we can conclude that the number of paths from $(0,0)$ to $(n-k,k)$ which do not cross the diagonal is given by $\binom{n}{k}-\binom{n}{k-1}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.