A247322 Number of paths from (0,0) 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, 2, 5, 9, 18, 35, 67, 132, 253, 495, 956, 1859, 3605, 6994, 13577, 26333, 51114, 99159, 192431, 373372, 724497, 1405819, 2727804, 5293079, 10270553, 19929026, 38670013, 75035105, 145597538, 282516315, 548192811, 1063708916, 2064013525, 4004996055

Offset: 0

Author

Clark Kimberling, Sep 13 2014

Keywords

• nonn
• easy

Comments

Also, a(n) = number of strings s(0)..s(n) of integers such that s(0) = 0, 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 A247321.

Examples

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

Links

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

Crossrefs

Cf. A247049, A247321, A247323, A247325, A247326.

Programs

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];
u = Flatten[Table[t[n, k], {n, 0, z}, {k, 0, 3}]] (* A247321 *)
TableForm[Reverse[Transpose[Table[t[n, k], {n, 0, 12}, {k, 0, 3}]]]]
u1 = Table[t[n, k], {n, 0, z}, {k, 0, 3}];
v = Map[Total, u1]  (* A247322 column sums *)

Formula

A247322(n) = A247323(n) + A247323(n+1) + A247325(n) + A247326(n).

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