$\begingroup$

consider a $n$ x $n$ square. How do i find the number of ways in which a person can travel from one corner to opposite corner(shortest distance) so that he never crosses the diagonal.(note he can touch the diagonal).he can only travel up or left.

I know this is a direct consequence of the 'bertrands ballot theorem' but i have not learned about it yet. i know the total number of ways of going from one corner to the opposite without any restrictions is $\binom{2n}{n}$.i tried drawing a figure and considering cases but that doesn't help.I dont know on how to proceed further.Possibly it has something to do with symmetry.Answer given is $\frac{1}{n+1}\binom{2n}{n}$.where did that $\frac{1}{n+1}$ come from?

is there a simple way to solve this problem?.

$\endgroup$ 13

1 Answer

$\begingroup$

Note: this answer is a summary of this video and not my original idea. It explains where the $1\over n+1$ comes from.

The problem you are describing is basically a sequence of $n$ "right" steps and $n$ "up" steps where the number of "up"s cannot exceed the number of "right"s at any point.

We will draw this in a diagram, where each "right" step is represented by a "up" segment and each "down" step is represented by a "down" segment.

First we remove the restriction, the total number of ways is clearly $2n\choose n$.

We define the term "exceedance" to be the number of down steps below $0$. We notice that, for a diagram with exceedance $k>0$, if we take the segment that hit $0$ the first time from a negative point, exchange its left and right hand sides, and move the whole right part including itself up one unit, we end up with a $k-1$ exceedance diagram. We can also go from $k-1$ to $k$ by looking at the first time from positive side to $0$ reading from right to left.

Therefore there is a bijection between cases of each consecutive exceedance, and therefore all exceedance have the same number of elements.

There are $n+1$ different exceedances possible and each has the same size, so for the exceedance=$0$ case we have ${1\over n+1}{2n\choose n}$

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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