Number of paths on square lattice without immediate backtracking I'm looking for the number of paths of a given length $N$ on an $r$-dimensional square lattice ($\mathbb{Z}^r$,$r\geq2$) with steps $(\pm 1, 0, 0 \dots)$,$(0,\pm 1, 0, 0 \dots)$... that go from $0$ to a given point $p$ on the lattice. In my problem backtracking isn't allowed, i.e you cannot go "left" directly after going "right", or "up" directly after going "down" etc.
https://arxiv.org/abs/1503.05930  gives the number for $r=2$ when backtracking is allowed, but sadly I couldn't find anything for my case.
 A: Let me give it a try for $r=2$, which should generalize pretty straighforwardly. Consider a generating function $f(n,e,w,s)$ in 4 variables, $n,e,w,s$, each variable denoting the weight of a unit step in the corresponding direction (N, E, W, S). A weight of a path $p$ is then the product of weights of its steps. We can partition a non-backtracking path uniquely into a (possibly empty) alternating sequence of maximal vertical and horizontal runs. Since no backtracking is allowed, a horizontal run consists of all E's or all W's, and a vertical run consists of all N's or all S's.
The generating functions of a nonempty horizontal and vertical run are:
$$
\begin{split}
h=h(e,w)&=\frac{e}{1-e}+\frac{w}{1-w}=\frac{e+w-2ew}{(1-e)(1-w)},\\
v=v(n,s)&=\frac{n}{1-n}+\frac{s}{1-s}=\frac{n+s-2ns}{(1-n)(1-s)}.
\end{split}
$$
The possibilities for a sequence of horizontal and vertical runs are $(hv)^*, (hv)^*h, v(hv)^*, v(hv)^*h$. Thus, the generating function
$$
f=\frac{1+h+v+hv}{1-hv}=\frac{(1+h)(1+v)}{1-hv}.
$$
Note also that
$$
\begin{split}
1+h=\frac{1-ew}{(1-e)(1-w)},\\
1+v=\frac{1-ns}{(1-n)(1-s)}.
\end{split}
$$
Thus,
$$
\begin{split}
f&=\frac{(1-ew)(1-ns)}{(1-e)(1-w)(1-n)(1-s)-(e+w-2ew)(n+s-2ns)}\\
&=\frac{1-(ew+ns)+news}{1-(n+e+w+s)+(ew+ns)+(new+sew+nes+nws)-3news}.
\end{split}
$$
For your purposes, we need to keep track of the total number of steps and the coordinates, so we need to make the substitution $e=xt$, $w=xt^{-1}$, $n=xu$, $s=xu^{-1}$. This yields
$$
\begin{split}
f&=\frac{(1-x^2)^2}{(1-x^2)(1+3x^2)-x(1-x^2)(t+t^{-1}+u+u^{-1})}\\
&=\frac{1-x^2}{1+3x^2-x(t+t^{-1}+u+u^{-1})}\\
&=\frac{1-x^2}{1+3x^2-x\dfrac{(u+t)(1+ut)}{ut}}.
\end{split}
$$
In particular, letting $t=u=1$, we get $f(x,x,x,x)=\dfrac{1+x}{1-3x}$ as expected.
Another relatively straightforward calculation (see Theorem 6.3.3 in Stanley's Enumerative Combinatorics, Volume 2) is to let $u=1$ and find the number of paths with no immediate backtracking from the origin to anywhere on the $x$-axis according to the total number of steps. This yields the generating function
$$
\frac{1-x^2}{\sqrt{(1-2x+3x^2)^2-4x^2}}=\frac{1-x^2}{\sqrt{(1-x)(1-3x)(1+3x^2)}}.
$$
