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

%I #22 Sep 29 2019 02:52:02

%S 1,5,21,81,313,1213,4701,18217,70593,273557,1060069,4107905,15918665,

%T 61686893,239044717,926329305,3589646289,13910345285,53904393461,

%U 208886521137,809462381657,3136771792413,12155397830269,47103744291977,182533122922465,707339543058421,2741032537895173,10621856854367201

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

%C 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.

%C 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.

%H Jeremy Dover, <a href="https://mathoverflow.net/q/281865">Generalization of an up, left, right path problem</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-1,2).

%F a(n) = a(n-1) + 4(2^n-1) + 4 Sum_{k=2..n} (2^(k-1)-1)*a(n-k) for n > 0.

%F From _Jay Pantone_, Sep 24 2017: (Start)

%F a(n) = 4a(n-1) - a(n-2) + 2a(n-3).

%F G.f.: (1 + x + 2x^2) / (1 - 4x + x^2 - 2x^3).

%F (End)

%e 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.

%e Sample of a good walk: LBLL U LFFFF U U BBBRBR U FR

%e Sample of a bad walk: LBR U FFFRF U LBLL U FB

%e ^ ^ ^^

%t LinearRecurrence[{4, -1, 2}, {1, 5, 21}, 40] (* _Jean-François Alcover_, Sep 29 2019 *)

%o (PARI) Vec((1 + x + 2*x^2)/(1 - 4*x + x^2 - 2*x^3) + O(x^40)) \\ _Andrew Howroyd_, Feb 17 2018

%Y Cf. A001333.

%K nonn

%O 0,2

%A _Jeremy Dover_, Sep 25 2017