2

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?.

Albus Dumbledore
  • 11,860
  • You say shortest distance to go from one corner to the opposite corner. But there is only one way with the shortest distance which is going along the diagonal. – Math Lover Aug 25 '20 at 14:00
  • I assume you're allowed to travel only up and right? And you are moving say from the bottom left corner to upper right corner. You should mention that. – peter.petrov Aug 25 '20 at 14:00
  • @peter.petrov yes that is what i mean – Albus Dumbledore Aug 25 '20 at 14:00
  • This is equivalent to a sequence of $-1, 1$ where the sum cannot be less than zero. I swear there was a famous Youtube math channel doing a video on this, giving a bijection between the cases with different total sums. Thought was 3blue1brown but actually wasn't. Couldn't remember where I watched it. – cr001 Aug 25 '20 at 14:05
  • @cr001 For this problem I think you mean the sum must be exactly equal to zero (and of length 2n-2) – N A McMahon Aug 25 '20 at 14:06
  • The final sum has to be zero. What I meant was any subsequence cannot become less than zero (cross the diagonal). – cr001 Aug 25 '20 at 14:07
  • Can't remember the full argument, but it had something to do with the first time it hits zero in the middle, and swapping the left side sub-sequence and the right side sub-sequence with some special operation. – cr001 Aug 25 '20 at 14:09
  • Found the video. Not phrased exactly the same but essentially the same problem. https://www.youtube.com/watch?v=PBt1gB9Ou9E – cr001 Aug 25 '20 at 14:16
  • https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem#Variant:_ties_allowed – peter.petrov Aug 25 '20 at 14:16
  • 1
    The wikipedia article on Catalan Numbers contains several proofs and should more than suffice to answer your question. Read that first. Get back to us after reading the proofs in the article. Only after you have finished, if you still need more help in understanding, ask for more clarification about specific points in the article that you still do not understand. – JMoravitz Aug 25 '20 at 14:17
  • As for deciding on which, if any, of the dozens or hundreds of times people have asked for proof of the formula for Catalan numbers this post should be closed as a duplicate of, this one seems close to the phrasing you used. See also here. – JMoravitz Aug 25 '20 at 14:28
  • 1
    Find all ways that take you to the point (n-1,n+1) as they all cross the diagonal and subtract from all ways to get to point (n, n). That should give you the number of ways to get to point (n, n) without crossing the diagonal. – Math Lover Aug 25 '20 at 14:37
  • @MathLover never thought about that ! thanks ,i now have 2 approaches to this problem. – Albus Dumbledore Aug 25 '20 at 15:09

1 Answers1

1

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.

enter image description here enter image description here

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}$

cr001
  • 12,598