A247326 Number of paths from (0,0) to (n,3), with vertices (i,k) satisfying 0 <= k <= 3, consisting of segments given by the vectors (1,1), (1,2), (1,-1).

0, 0, 2, 2, 6, 10, 20, 40, 74, 150, 282, 558, 1072, 2088, 4050, 7850, 15254, 29562, 57412, 111344, 216106, 419294, 813594, 1578750, 3063264, 5944144, 11533698, 22380210, 43426118, 84263882, 163505076, 317263672, 615616874, 1194537286, 2317872890, 4497581934

Offset

0,3

Comments

Also, a(n) = number of strings s(0)..s(n) of integers such that s(0) = 0, s(n) = 3, and for i > 0, s(i) is in {0,1,2,3} and s(i) - s(i-1) is in {-1,1,2} for 1 <= i <= n; also, a(n) = row 3 of the array at A247321.

Links

Clark Kimberling, Table of n, a(n) for n = 0..1000

Formula

Empirically, a(n) = 3*a(n-2) + 2*a(n-3) - a(n-4) and g.f. = (2*x^2 + x^3)/(1 - 3 x^2 - 2 x^3 + x^4).

Example

a(4) counts these 6 paths, each represented by a vector sum applied to (0,0):
(1,2) + (1,1) + (1,-1) + (1,1);
(1,1) + (1,2) + (1,-1) + (1,1);
(1,2) + (1,-1) + (1,1) + (1,1);
(1,1) + (1,-1) + (1,2) + (1,1);
(1,1) + (1,-1) + (1,1) + (1,2);
(1,1) + (1,1) + (1,-1) + (1,2).

Mathematica

z = 25; t[0, 0] = 1; t[0, 1] = 0; t[0, 2] = 0; t[0, 3] = 0;
t[1, 3] = 0; t[n_, 0] := t[n, 0] = t[n - 1, 1];
t[n_, 1] := t[n, 1] = t[n - 1, 0] + t[n - 1, 2];
t[n_, 2] := t[n, 2] = t[n - 1, 0] + t[n - 1, 1] + t[n - 1, 3];
t[n_, 3] := t[n, 3] = t[n - 1, 1] + t[n - 1, 2];
Table[t[n, 3], {n, 0, z}];  (* A247326 *)

Crossrefs

Cf. A247049, A247321, A247322, A247325.

Sequence in context: A044044 A123757 A167399 * A300274 A019310 A078008

Adjacent sequences: A247323 A247324 A247325 * A247327 A247328 A247329

Keyword

nonn,easy

Author

Clark Kimberling, Sep 13 2014

Status

approved