|
%I #13 Sep 16 2014 02:35:17
%S 1,0,0,0,0,1,1,0,1,1,1,2,1,2,4,2,2,5,5,6,5,7,13,10,7,18,22,20,18,29,
%T 45,40,29,63,87,74,63,116,166,150,116,229,329,282,229,445,627,558,445,
%U 856,1232,1072,856,1677,2373,2088,1677,3229,4621,4050,3229
%N Rectangular array read upwards by columns: T = T(n,k) = number of paths from (0,0) to (n,k), where 0 <= k <= 3, consisting of segments given by the vectors (1,1), (1,2), (1,-1).
%C Also, T(n,k) = number of strings s(0)..s(n) of integers such that s(0) = 0, s(n) = k, 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.
%H Clark Kimberling, <a href="/A247321/b247321.txt">Table of n, a(n) for n = 0..1000</a>
%F The four rows and the column sums all empirically satisfy the linear recurrence r(n) = 3*r(n-2) + 2*r(n-3) - r(n-4), with g.f. of the form p(x)/q(x), where q(x) = 1 - 3 x^2 - 2 x^3 + x^4. Initial terms and p(x) follow:
%F (row 0, the bottom row): 1,0,1,1; 1 - 2*x^2 - x^3
%F (row 1): 0,1,1,2; x + x^2 - x^3
%F (row 2): 0,1,1,4; x + x^2 + x^3
%F (row 3): 0,0,1,1; 2x^2 + 2x^3
%F (n-th column sum) = 1,2,5,9; 1 + 2*x + 2*x^2 + x^3.
%e First 10 columns:
%e 0 .. 0 .. 2 .. 2 .. 6 .. 10 .. 20 .. 40 .. 74 .. 150
%e 0 .. 1 .. 1 .. 4 .. 5 .. 13 .. 22 .. 45 .. 87 .. 166
%e 0 .. 1 .. 1 .. 2 .. 5 .. 7 ... 18 .. 29 .. 63 .. 116
%e 1 .. 0 .. 1 .. 1 .. 2 .. 5 ... 7 ... 18 .. 29 .. 63
%e T(3,2) counts these 4 paths, given as vector sums applied to (0,0):
%e (1,2) + (1,1) + (1, -1)
%e (1,1) + (1,2) + (1,-1)
%e (1,2) + (1,-1) + (1,1)
%e (1,1) + (1,-1) + (1,2)
%e Partial sums of second components in each vector sum give the 3 integer strings described in Comments: (0,2,3,2), (0,1,3,2), (0,2,1,2), (0,1,0,2).
%t z = 25; t[0, 0] = 1; t[0, 1] = 0; t[0, 2] = 0; t[0, 3] = 0;
%t t[1, 3] = 0; t[n_, 0] := t[n, 0] = t[n - 1, 1];
%t t[n_, 1] := t[n, 1] = t[n - 1, 0] + t[n - 1, 2];
%t t[n_, 2] := t[n, 2] = t[n - 1, 0] + t[n - 1, 1] + t[n - 1, 3];
%t t[n_, 3] := t[n, 3] = t[n - 1, 1] + t[n - 1, 2];
%t u = Flatten[Table[t[n, k], {n, 0, z}, {k, 0, 3}]] (* A247321 *)
%t TableForm[Reverse[Transpose[Table[t[n, k], {n, 0, 12}, {k, 0, 3}]]]]
%t u1 = Table[t[n, k], {n, 0, z}, {k, 0, 3}];
%t v = Map[Total, u1] (* A247322 column sums *)
%t Table[t[n, 0], {n, 0, z}] (* A247323, row 0 *)
%t Table[t[n, 1], {n, 0, z}] (* A247323 shifted, row 1 *)
%t Table[t[n, 2], {n, 0, z}] (* A247325, row 2 *)
%t Table[t[n, 3], {n, 0, z}] (* A247326, row 3 *)
%Y Cf. A247049, A247322, A247323, A247325, A247326.
%K nonn,tabf,easy
%O 0,12
%A _Clark Kimberling_, Sep 13 2014
|
