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

0, 1, 2, 3, 8, 12, 28, 49, 100, 191, 370, 724, 1392, 2721, 5254, 10223, 19812, 38456, 74628, 144769, 280984, 545107, 1057862, 2052520, 3982816, 7728177, 14995626, 29097643, 56460416, 109556004, 212580908, 412491201, 800394316, 1553079415, 3013584442

Offset: 0

Author

Clark Kimberling, Sep 15 2014

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A247352, A247353, A247354.

Programs

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];
Table[t[n, 2], {n, 0, z}]   (* A247355 *)

Formula

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