OFFSET
0,2
COMMENTS
A walk begins at the origin, and each step can be in one of five directions: Up (0,0,1), Left (-1,0,0), Right (1,0,0), Forward (0,-1,0) or Backward (0,1,0), satisfying the condition that within each plane z=k, the path may only move away from the first step into that plane. This concept generalizes the "Number of n step one-sided prudent walks with east, west and north steps" of A001333.
Number of length n strings of the symbols U, L, R, F and B such that between any L and R (resp. F and B) there appears at least one U.
LINKS
Jeremy Dover, Generalization of an up, left, right path problem
Index entries for linear recurrences with constant coefficients, signature (4,-1,2).
FORMULA
a(n) = a(n-1) + 4(2^n-1) + 4 Sum_{k=2..n} (2^(k-1)-1)*a(n-k) for n > 0.
From Jay Pantone, Sep 24 2017: (Start)
a(n) = 4a(n-1) - a(n-2) + 2a(n-3).
G.f.: (1 + x + 2x^2) / (1 - 4x + x^2 - 2x^3).
(End)
EXAMPLE
One can think of the Us as separators. Each substring between the Us (plus those before the first U and after the last U) can only contain one of L or R, and one of F or B.
Sample of a good walk: LBLL U LFFFF U U BBBRBR U FR
Sample of a bad walk: LBR U FFFRF U LBLL U FB
^ ^ ^^
MATHEMATICA
LinearRecurrence[{4, -1, 2}, {1, 5, 21}, 40] (* Jean-François Alcover, Sep 29 2019 *)
PROG
(PARI) Vec((1 + x + 2*x^2)/(1 - 4*x + x^2 - 2*x^3) + O(x^40)) \\ Andrew Howroyd, Feb 17 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeremy Dover, Sep 25 2017
STATUS
approved