4
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Please add the sequence to the OEIS. $\endgroup$ – Max Alekseyev Sep 24 '17 at 13:38
  • $\begingroup$ This is absolutely not an answer to your question, but I have a suggested name: iterated ballistic random walk. A possible generalization (maybe this is what you had in mind?): once you move backwards or forwards in the $i$th direction, the reverse move in the $i$th direction is forbidden until after the walk has moved in the $(i-1)$st direction. This condition is also sufficient to ensure that there are no self-intersections. Again, there will be a simple recurrence relation to compute the number of walks because the process is driven by a Markov chain. $\endgroup$ – Anthony Quas Sep 24 '17 at 18:51
  • $\begingroup$ PS: The reason it's ballistic is that unlike regular random walk, this one moves away from the origin (in the $e_1$ direction at a linear rate); the reason it's iterated is that between steps of the $e_i$ direction, it performs a $(d-i)$-dimensional random walk in the remaining directions. $\endgroup$ – Anthony Quas Sep 24 '17 at 18:52
  • $\begingroup$ @Jeremy Dover Could you indicate the Math.StackExchange question you are refering to ? $\endgroup$ – Jean Marie Becker Sep 24 '17 at 22:16
  • 1
    $\begingroup$ @JeanMarieBecker: sure...here is the link math.stackexchange.com/questions/2441318/… $\endgroup$ – Jeremy Dover Sep 24 '17 at 22:22
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.