# How to count the number of paths from (0,0) to (n,n) where N, E, and k NE diagonals are allowed?

I know how to count paths from (0,0) to (i,j) where only North and East movements are allowed.

What confuses me about adding in the diagonals is that the number of possible paths seems also dependent on the location of the diagonal.

For example (0,0) to (2,2), k = 1:

Diagonal from (0,0) to (1,1): 2 possible paths

  _ (2,2)
|_|
/
(0,0)


Diagonal from (0,1) to (1,2): only 1 possible path

  __ (2,2)
/
|
(0,0)


How to count the number of paths from (0,0) to (n,n) where N, E, and k NE diagonals are allowed?

• You have $NDE$ as you drew, but also $EDN$ using those three moves ... So not only one possible path. – String Mar 3 '15 at 21:39
• @String String, there is only one possible path when you place the diagonal from (0,1) to (1,2). There are two possible paths when you place the diagonal from (0,0) to (1,1). There are also other locations to place the diagonal - I gave those examples to help explain what confuses me. – גלעד ברקן Mar 3 '15 at 21:43
• Sorry, I fully understood that. See my answer where I elaborate a bit further what I mean. – String Mar 3 '15 at 21:50

Let $E,N$ and $D$ denote the number of moves in East, North and diagonal direction respectively. Then a solution must satisfy \begin{align} i&=E+D\\ j&=N+D \end{align}

Note that for specific $(i,j)$, $D$ determines the system entirely. So given $D$ we can calculate $E,N$.

Now, for a given tuple $(E,N,D)$ satisfying the above for a given endpoint $(i,j)$, it becomes a combinatorial question how many different orders we can form using these letters. In the case of $(i,j)=(2,2)$ and $(E,N,D)=(1,1,1)$ we have the possibilities

    DNE (path 1)
DEN (path 2)
NDE (path 3)
NED
END
EDN


so of course that makes $3!=6$ paths. Here path 1 and 2 correspond to your first diagram and path 3 to your third. Indeed path 3 is the only path with the diagonal connecting $(0,1)$ and $(1,2)$, but just regarding this as permutations of letters we do not need to be that concerned with specific locations of specific parts of the paths.

I think the formula $$paths_{(i,j)}(D)=\frac{[(i-D)+(j-D)+D]!}{(i-D)!(j-D)!D!}$$ could be relevant here. Note that $(i-D)=E$ and $(j-D)=N$ which is why those figures appear. So for a given $D$ this should calculate the number of paths that can be formed.

• Thanks! That helps me think about it better. – גלעד ברקן Mar 3 '15 at 21:52
• @גלעדברקן: I am happy to hear that! – String Mar 3 '15 at 21:55