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

1, 3, 5, 11, 20, 40, 77, 149, 291, 561, 1094, 2116, 4113, 7975, 15477, 30035, 58268, 113084, 219397, 425753, 826091, 1602969, 3110382, 6035336, 11710993, 22723803, 44093269, 85558059, 166016420, 322136912, 625072109, 1212885517, 2353473731, 4566663857

Offset

0,2

Comments

Also, a(n) = number of strings s(0)..s(n) of integers such that s(0) = 1, 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) = n-th column sum of the array at A247352.

Links

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

Formula

A247353(n) = A247354(n) + A247354(n+1) + A247355(n) + A247321(n).

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

Example

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

Mathematica

z = 50; t[0, 0] = 0; t[0, 1] = 1; t[0, 2] = 0; t[0, 3] = 0;
t[1, 3] = 1; 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]
u = Flatten[Table[t[n, k], {n, 0, z}, {k, 0, 3}]] (* A247352 *)
u1 = Table[t[n, k], {n, 0, z}, {k, 0, 3}];
v = Map[Total, u1]  (* A247353 *)

Crossrefs

Cf. A247322, A247352, A247354, A247355.

Sequence in context: A094588 A299027 A339006 * A293948 A281318 A082713

Adjacent sequences: A247350 A247351 A247352 * A247354 A247355 A247356

Keyword

nonn,easy

Author

Clark Kimberling, Sep 15 2014

Status

approved