Lattice paths that don't touch the diagonal

639 Views Asked by At

Consider a coordinate system. Suppose we want to calculate the number of lattice paths from (0,0) to (P,Q); P>Q such that none of those lattice paths ever touch the line y=x, which indirectly tells us that any given point of time the numbers of advancements along east cannot be equal to the number of advancements towards the north. So its basically asking for the number of lattice paths in which at any instant, the number of x advancements is strictly greater than the y advancements.

Some visual diagrams can help in better understanding.... considering (P=8 and Q=5 in here,) :

enter image description here

So, as you can see, the path in RED is a BAD path as it touches the diagonal at (3,3), whereas the BLUE path is a GOOD path as it always stays below the diagonal and never touches it

1

There are 1 best solutions below

2
On

Existing result magically to the rescue: Bertrand's ballot theorem!