A113095 Triangle T, read by rows, that satisfies the recurrence: T(n,k) = [T^4](n-1,k-1) + [T^4](n-1,k) for n>k>=0, with T(n,n)=1 for n>=0, where T^4 is the matrix 4th power of T.

1, 1, 1, 4, 5, 1, 46, 66, 21, 1, 1504, 2398, 978, 85, 1, 146821, 255113, 122914, 14962, 341, 1, 45236404, 84425001, 46001193, 7046354, 235122, 1365, 1, 46002427696, 91159696960, 54661544301, 9933169553, 432627794, 3738738, 5461, 1

Offset

0,4

Comments

Column 0 of the matrix power p, T^p, equals the number of 4-tournament sequences having initial term p (see A113092 for definitions).

Links

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

Formula

Let GF[T] denote the g.f. of triangular matrix T. Then GF[T] = 1 + x*(1+y)*GF[T^4] and for all integer p>=1: GF[T^p] = 1 + x*Sum_{j=1..p} GF[T^(p+3*j)] + x*y*GF[T^(4*p)].

Example

Triangle T begins:
1;
1,1;
4,5,1;
46,66,21,1;
1504,2398,978,85,1;
146821,255113,122914,14962,341,1;
45236404,84425001,46001193,7046354,235122,1365,1; ...
Matrix third power T^3 (A113099) begins:
1;
3,1;
27,15,1;
693,513,63,1;
52812,47619,8289,255,1; ...
where column 0 equals A113100.
Matrix 4th power T^4 (A113101) begins:
1;
4,1;
46,20,1;
1504,894,84,1;
146821,108292,14622,340,1;
45236404,39188597,6812596,233758,1364,1; ...
where adjacent sums in row n of T^4 forms row n+1 of T.

Prog

(PARI) {T(n, k)=local(M=matrix(n+1, n+1)); for(r=1, n+1, for(c=1, r, M[r, c]=if(r==c, 1, if(c>1, (M^4)[r-1, c-1])+(M^4)[r-1, c]))); return(M[n+1, k+1])}

Crossrefs

Cf. A097710, A113084, A113106; A113092, A113096 (column 0), A113097 (T^2), A113099 (T^3), A113101 T^4).

Sequence in context: A286796 A286718 A204579 * A157784 A274615 A258895

Adjacent sequences: A113092 A113093 A113094 * A113096 A113097 A113098

Keyword

nonn,tabl

Author

Paul D. Hanna, Oct 14 2005

Status

approved