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