|
|
A247325
|
|
Number of paths from (0,0) to (n,2), with vertices (i,k) satisfying 0 <= k <= 3, consisting of segments given by the vectors (1,1), (1,2), (1,-1).
|
|
6
|
|
|
0, 1, 1, 4, 5, 13, 22, 45, 87, 166, 329, 627, 1232, 2373, 4621, 8956, 17377, 33737, 65422, 127009, 246363, 478134, 927685, 1800119, 3492960, 6777593, 13151433, 25518580, 49516525, 96081013, 186435302, 361757509, 701951407, 1362062118, 2642933937, 5128331659
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Also, a(n) = number of strings s(0)..s(n) of integers such that s(0) = 0, 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 A247321.
|
|
LINKS
|
|
|
FORMULA
|
Empirically, a(n) = 3*a(n-2) + 2*a(n-3) - a(n-4) and g.f. = (x + x^2 + x^3)/(1 - 3 x^2 - 2 x^3 + x^4).
|
|
EXAMPLE
|
a(4) counts these 4 paths, each represented by a vector sum applied to (0,0):
(1,2) + (1,1) + (1,-1);
(1,1) + (1,2) + (1,-1);
(1,2) + (1,-1) + (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, 2], {n, 0, z}]; (* A247325 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|