Generalization of an up, left, right path problem

Question

I recently answered a question on the Math Stack Exchange regarding an example in van Lint and Wilson's A Course in Combinatorics, counting the number of paths with $n$ steps consisting of up, left, and right steps, where no left step can be adjacent to a right step. Letting $a_n$ be the number of such paths, the example makes an elegant argument that $a_n = 2a_{n-1}+a_{n-2}$, which can be solved using standard methods.

The requirements on the path ensure that it will not intersect itself, which made me wonder if anyone has addressed higher dimensional analogs of this problem. A natural generalization in three space might be finding the number $b_n$ of paths of length $n$ such that each step is up, left, right, forward or backward, with the properties:

• if a left (resp. right) step occurs, a right (resp. left) step cannot occur until after the next up step
• if a forward (resp. backward) step occurs, a backward (resp. forward) step cannot occur until after the next up step

Is anyone aware of work on any such generalizations? I have a recurrence relation for the $b_n$'s:

$$b_n = b_{n-1} + 4(2^n-1) + 4\displaystyle \sum_{i=2}^n (2^{i-1}-1)b_{n-i}$$

with $b_0=1$ and $b_1=5$. Running this up creates a sequence which does not appear in the OEIS. Any references would be much appreciated!

Answer 1

Your sequence has generating function $$ \frac{1+x+2x^2}{1-4x+x^2-2x^3} $$ and satisfies the constant-coefficient linear recurrence $$ b_{n+3} = 4b_{n+2}-b_{n+1}+2b_n. $$

I'll give two quick proofs, but first I'll prove the 2D version with the same techniques. Both prove that the analogous problem in any number of dimensions always has a rational generating function and a constant-coefficient linear recurrence.

---

Consider the 2D case. Let $A(x)$ be the generating function for all valid walks, let $B(x)$ be the generating function for all valid walks that either end in $U$ or are length $0$, and let $C(x)$ be the generating function for all valid walks that end in $L$ or $R$. Then, these three formal power series satisfy the system of equations $$ \left\{ \begin{array}{l} A(x) = B(x) + C(x)\\ B(x) = 1 + xA(x)\\ C(x) = 2xB(x) + xC(x) \end{array} \right.. $$ The reasoning is as follows: every walk is either empty or ends in something, hence the first equation; every walk that ends in $U$ can be formed by taking any walk and appending a $U$, hence the second equation; every walk that ends in $L$ or $R$ can be formed by taking a walk that ends in $U$ or is empty and appending either $L$ or $R$ or by taking a walk that ends in $L$ or $R$ and appending the same symbol as the current last symbol. Solving this system gives $$ A(x) = \frac{1 + x}{1-2x-x^2} $$ which gives the constant-coefficient recurrence you mention.

Another solution can be formed with a two-state finite state machine. State 1 represents paths in which the next symbol can be anything, State 2 represents paths in which the next symbol is restricted because the previous symbol was $L$ or $R$. The start state is State 1 and both states are accepting. The transition matrix is $$ \left[\begin{array}{cc}x&2x\\x&x\end{array}\right] $$ and the transfer matrix method gives the same rational generating function.

---

For the 3D problem, you only need to one additional equation. Let $P(z)$ be the generating function for all valid walks, let $Q(z)$ be the generating function for all walks that end in $U$ or have length $0$, let $R(z)$ be the generating function for all walks that have a single direction locked in (i.e., since the last $U$, exactly one of $L,R,F,B$ has been seen), and let $S(z)$ be the generating function for all walks that have both directions locked in (i.e., since the last $U$, exactly one of $L$ or $R$ and exactly one of $F$ or $B$ have been seen). The system becomes $$ \left\{\begin{array}{l} P(x) = Q(x) + R(x) + S(x)\\ Q(x) = 1 + xP(x)\\ R(x) = 4xQ(x) + xR(x)\\ S(x) = 2xR(x) + 2xS(x) \end{array}\right.. $$ The solution is the rational generating function I mention at the top of this post.

The second solution generalizes in a similar way. Now three states are needed: one where you are free to move in any direction, one in which one type of movement is locked ($L/R$ or $F/B$), and one in which both types of movement are locked.

These can clearly be generalized to any dimension, so every such sequence has a rational generating function and hence a constant-coefficient linear recurrence.