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

Author

Paul D. Hanna, Oct 14 2005

Keywords

• nonn
• tabl

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).

Examples

			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.
		

Crossrefs

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

Programs

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])}

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)].