Skip to main content
1 of 2
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

How many double paths in a grid?

I have a combinatorics problem motivated, of all things, by category theory.

Consider a two-dimensional grid of vertices and edges. Fix two points, $P$ and $Q$, such that $Q$ is $a$ steps right and $b$ steps down from $a$. I'm interested in counting pairs of shortest paths from $P$ to $Q$. That is two paths from $P$ to $Q$ that only go down and right, never up and left. They are also never allowed to touch, either on an edge or a vertex, so one is always down-left and the other up-right.

If $a=1$ or $b=1$ there is just one pair of paths that work, forming a rectangle. If $a=2$ and $b=2$ I count 3 pairs - one forming a square and two forming Ls. How many pairs are there in general?

(This calculation helps count the number of indecomposable objects in a certain abelian category.)

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563