A292878 Number of ascending ballistic random walks of length n in 3-dimensions.

1, 5, 21, 81, 313, 1213, 4701, 18217, 70593, 273557, 1060069, 4107905, 15918665, 61686893, 239044717, 926329305, 3589646289, 13910345285, 53904393461, 208886521137, 809462381657, 3136771792413, 12155397830269, 47103744291977, 182533122922465, 707339543058421, 2741032537895173, 10621856854367201

Offset: 0

Author

Jeremy Dover, Sep 25 2017

Keywords

• nonn

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.

Examples

			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
                      ^ ^                  ^^
		

Links

• Jeremy Dover, Generalization of an up, left, right path problem
• Index entries for linear recurrences with constant coefficients, signature (4,-1,2).

Crossrefs

Cf. A001333.

Programs

Mathematica

LinearRecurrence[{4, -1, 2}, {1, 5, 21}, 40] (* Jean-François Alcover, Sep 29 2019 *)

PARI

Vec((1 + x + 2*x^2)/(1 - 4*x + x^2 - 2*x^3) + O(x^40)) \\ Andrew Howroyd, Feb 17 2018

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)