A096744 Triangle T, read by rows, such that the matrix cube shifts T one place diagonally left and upward, with T(n, 0) = T(n, n) = 1 for n>=0.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 6, 3, 1, 1, 1, 16, 12, 3, 1, 1, 1, 40, 37, 12, 3, 1, 1, 1, 133, 138, 55, 12, 3, 1, 1, 1, 429, 498, 219, 55, 12, 3, 1, 1, 1, 1696, 2103, 969, 273, 55, 12, 3, 1, 1, 1, 6583, 8734, 4215, 1266, 273, 55, 12, 3, 1, 1, 1, 29167, 40291, 19989, 6213, 1428

Offset

0,8

Comments

Column with index 1 forms A096745 shift right. Row sums form A096746. The convergent of the rows in reverse order is the sequence enumerating ternary trees (A001764).

Links

Table of n, a(n) for n=0..71.

Formula

T(n, k) = Sum_{i=0..n-1} Sum_{j=0..n-2} T(n-2, j)*T(j, i)*T(i, k-1) for n>1 and k>0; T(n, 0)=T(n, n)=1.

Example

Rows begin:
{1},
{1,1},
{1,1,1},
{1,3,1,1},
{1,6,3,1,1},
{1,16,12,3,1,1},
{1,40,37,12,3,1,1},
{1,133,138,55,12,3,1,1},
{1,429,498,219,55,12,3,1,1},
{1,1696,2103,969,273,55,12,3,1,1},
{1,6583,8734,4215,1266,273,55,12,3,1,1},
{1,29167,40291,19989,6213,1428,273,55,12,3,1,1},
{1,128401,185364,94755,30249,7266,1428,273,55,12,3,1,1},...
T^3 begins:
{1},
{3,1},
{6,3,1},
{16,12,3,1},
{40,37,12,3,1},
{133,138,55,12,3,1},
{429,498,219,55,12,3,1},...
which equals T shift one place diagonally left and upward.

Mathematica

T[n_, 0] := 1; T[n_, n_] := 1; T[n_, k_] := Sum[ Sum[ T[n - 2, j]*T[j, i]*T[i, k - 1], {j, 0, n - 2}], {i, 0, n - 1}] ; Table[T[n, k], {n, 0, 10}, {k, 0, n}] (* G. C. Greubel, Nov 28 2016 *)

Prog

(PARI) {T(n, k) = if(n<k||k<0, 0 , if(n==k||k==0, 1, sum(i=0, n-1, sum(j=0, n-2, T(n-2, j)*T(j, i))*T(i, k-1) )))}

Crossrefs

Cf. A096745, A096746, A096591, A001764.

Sequence in context: A135494 A367618 A016566 * A180051 A160752 A186024

Adjacent sequences: A096741 A096742 A096743 * A096745 A096746 A096747

Keyword

nonn,tabl

Author

Paul D. Hanna, Jul 06 2004

Status

approved