The Gateway to Computer Science Excellence
+4 votes
Show that, in a grid, the number of paths from $(0,0)$ to $(n,n)$ which does not cross  ( it could touch ) the line $x = y$ is

\frac{1}{1+n}\binom{2\cdot n}{n} = \binom{2\cdot n}{n} - \binom{2\cdot n}{n-1}

After that, show the number of balanced paranthesis strings of length $2n$ is same as the above result.
in Set Theory & Algebra by | 293 views

similar concept explain in this video -  (lecture by Akashdeep nain sir codechef, its very high content, if u have time then worth of watching it)

(if u understand this is good, rest ignore this)

4 Answers

+5 votes
Best answer

Part 1 - 

Every path from (0,0) to (n,n) consists of n Right steps and n Up steps. 

Total number of steps = $2n$
$n$ Right steps out of $2n$ steps can be chosen in $\binom{2n}{n}$  ways. Remaining steps will be upward steps only.
Total number of possible paths - $\Large\binom{2n}{n}$

Now we have to subtract those paths which cross the line x =y of the grid. Say, those paths are bad paths. 
Line x=y is the main diagonal of the gird only. 
Now every path that crosses the diagonal must have crossed it for the very first time.
Find that step that crosses the diagonal for the 1st time.
Observe that before the path crosses the diagonal it must have taken k right steps and k up steps before it touches the diagonal after that (k+1) th up step crosses the diagonal.
Means we need Up steps to be less than or equal to Right step at any point to remain on or below the diagonal.
 There remain n−k steps to the right and n − k-1 steps up.

Now flip the steps in the path after that (k+1)th step along a line parallel the diagonal i.e every time the original path goes to the right, go up instead, and when the original path goes up, go to the right.

Now see, k steps before the path cross the diagonal and k+1th step that crosses the diagonal remains same after the flip.
so there remain n−k steps to the right and n − k-1 steps up. But since we swap right and up steps , the modified path with have a total of (k) + (n − k − 1) = n − 1 steps to the right and (k + 1) + (n − k) = n + 1 steps up. Thus every modified path ends at the same point, n − 1 steps to the right and n + 1 steps up. 

Now our grid changes from nxn to (n-1) x (n+1).
Thus the number of bad paths is the total number of routes in an (n − 1) x (n + 1) grid.
Total number of bad paths =  $\Large\binom{2n}{n-1}$
Choose $n-1$ right steps out of $2n$ steps remaining will be up steps only. 

Total number of paths from (0,0) to (n,n) which does not cross the line x=y is
 $\Large\binom{2n}{n} -  \binom{2n}{n-1}$ 

= $\Large\binom{2n}{n} -  \frac{n}{n+1}\binom{2n}{n}$

= $\Large\frac{1}{n+1}\binom{2n}{n} $ = Cn = Nth Catalan number

Part 2 - 
Now consider Right steps as open parenthesis and Up steps as close parenthesis. 
Now we have the same requirements - There are n open parenthesis and n close parenthesis and for any prefix number of close parenthesis to be less than or equal to the number of Open Parenthesis.
So In terms of balanced parenthesis string, we are starting with a sequence of n ( and n ) which is not balanced, and exchanging all ( with ) after the first that violates the condition.

So  the number of balanced parenthesis strings of length 2n is given by  $\Large\frac{1}{n+1}\binom{2n}{n} $

selected by
+3 votes

    I am proving the 2nd part of the question  that is 

The number of paths from (0,0) to (n,n) without crossing the line x=y is equal to the number of balanced paranthesis strings.

Now, at each step we are moving either horizontal or in the upward direction.

To, reach the point (n,n) from (0,0) we have to cover n horizontal lines (lines parallel to x axis) and n upward lines (lines parallel to y-axis).

Now, take one path for example where we are covering n lines in the horizontal direction to the point (n,0) and then n lines in the upward direction to the point (n,n).

That path would be represented by HHH.........H(ntimes)UUU...........U(ntimes)  (writing H for horizontal and U for upward ).

So, we can write any path from (0,0) to (n,n) with a string of n H's and n U's just write H when we take horizontal direction and U when we take the upward direction.

So, when there is no restriction the number of paths from (0,0) to (n,n) is equal to the number of strings with nH's and nU's = 2nC

Now, our restriction is we can't cross the x=y line that means if any path reaches to a point (x,y) where y>x then that path is rejected and should not be in our solution.

A path can reach a point (x,y) where y>x only when we find that a prefix of the path (string containing nH's and nU's) contains more U's than H's (THINK)

Take an example for clarity suppose n=3 then the path HUUHHU is rejected because the prefix HUU contains more U's than H's

So, our answer will be those strings where no prefix contains more U's than H's this thing happens for balanced paranthesis just replace H by '{' and U by '}'

So, the number of paths from (0,0) to (n,n) is equal to the number of strings of balanced paranthesis.(part 2 of the problem proved)


+1 vote

I am proving the part 1 of the problem only.

Without any restriction the number of paths from (0,0) to (n,n) is 2nCn.

Now,our problem has a restriction that we cannot cross the x=y line.

So, out of 2nCn paths we have to substract those paths which crosses the x=y line.

Now, I am going to prove that the no. of paths which crosses the x=y line is equal to number of paths we can take to go from (0,0) to (n-1,n+1).

                                                                                                     Look at the above image I have taken n=3 for simplicity. Assume there is one black ant and one red ant at the point (0,0). Now, the red ant wants to reach the point (2,4) and the black ant wants to reach the point (3,3).

The red ant can move only in the red region (shaded with red pen) and the black ant moves only in the black region (shaded with black pen) and suppose the black ant has sworn that it will take at least one point above the x=y line during his journey.

Note that red ant has to take at least one point above x=y line because the point (2,4) is above x=y line.

Now, to prove the number of paths can be taken by the red ant to reach the point (2,4) = number of path can be taken by the black  ant to reach (3,3)

When the ants are moving  through their common region ( the square (0,0) (2,0) (2,3) (0,3) ) they are moving together problem occurs when one ant leaves the common region.

Take a path traced by the black ant HHUUUH

Now, since the red ant is moving together with the black ant  when they are in the common region so, the path traced by the red ant upto the point (2,3) (note that the black ant reaches the point (2,3) in the above given path) is HHUUU

Now, the problem occurs when black ant goes horizontal to the point (3,3) then the red ant would take an upward direction to (2,4)

Whenever the black ant leaves the common region the red ant takes a path towards upward direction and after that follows the same direction as black ant.

Take another path for black ant HUUHHU the corresponding path for red ant will be HUUHUU.

In this way we will get an unique path for red ant corresponding to the path taken by the black ant.

Similarly we will also get an unquie path for black ant corresponding to a path taken by a red ant.(Think)

Thus set of paths taken by the red ant forms a bijective mapping with the set of paths taken by the black ant where at least one point is above the x=y line.

So, the number of paths taken by the black ant by taking at least one point above the x=y line = the no. of paths taken by the red ant to reach the point (2,4) = 6C2

In general it will be 2nCn-1

So, our required result is 2nCn - 2nCn-1  ( part 1 of the problem proved ).

+1 vote

I have found the recursive solution for solving this problem-

Let ways(n,n) be the number of ways of reaching a point (n,n) from (0,0) such that any path doesn't cross the diagonal at any time.

Now we can reach a point (x,y) by 2 ways- Through a point (x-1,y)  -  right move or point (x,y-1)   - up move.

But wait! is this always correct for any point?? because if the point is (x,x) number of ways to reach (x,x) by our solution,would be ways(x-1,x)+ways(x,x-1).

But observe!! If we are calculating the number of ways of reaching (x,x) through (x-1,x), we are counting the paths in which we have crossed the diagonal which is not what we are looking for. So, for reaching a point (x,x) we should just find the number of ways passing only through (x,x-1) and NOT (x-1,x).


So, now our recursive equation looks like this:

ways(x,y)= ways(x-1,y) + ways (x,y-1) ; if x!=y

                =ways(x,y-1); if(x==y).


I have written a small piece of code for this problem.You might understand this reucrsive equation better through this code:-

#include <stdio.h>
int ways(int x,int y)
    if(x==0 || y==0)return 1;
    else if(x==y)return ways(x,y-1);
    else return ways(x-1,y)+ ways(x,y-1);
int main()
    int n,ans;
  ans= ways(n,n);
    return 0;




Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,586 answers
95,409 users