A113092 Square table T, read by antidiagonals, where T(n,k) gives the number of n-th generation descendents of a node labeled (k) in the tree of 4-tournament sequences.

1, 0, 1, 0, 1, 1, 0, 4, 2, 1, 0, 46, 13, 3, 1, 0, 1504, 242, 27, 4, 1, 0, 146821, 13228, 693, 46, 5, 1, 0, 45236404, 2241527, 52812, 1504, 70, 6, 1, 0, 46002427696, 1237069018, 12628008, 146821, 2780, 99, 7, 1, 0, 159443238441379, 2305369985312, 9924266772

Offset: 0

Author

Paul D. Hanna, Oct 14 2005

Keywords

• nonn
• tabl

Comments

A 4-tournament sequence is an increasing sequence of positive integers (t_1,t_2,...) such that t_1 = p, t_i = p (mod 3) and t_{i+1} <= 4*t_i, where p>=1. This is the table of 4-tournament sequences when the starting node has label p = k for column k>=1.

Examples

			Table begins:
1,1,1,1,1,1,1,1,1,1,1,1,1,...
0,1,2,3,4,5,6,7,8,9,10,11,...
0,4,13,27,46,70,99,133,172,216,265,...
0,46,242,693,1504,2780,4626,7147,10448,14634,...
0,1504,13228,52812,146821,330745,648999,1154923,1910782,...
0,146821,2241527,12628008,45236404,124626530,289031301,...
0,45236404,1237069018,9924266772,46002427696,155367674020,...
0,46002427696,2305369985312,26507035453923,159443238441379,...
0,159443238441379,14874520949557933,246323730279500082,...
		

Links

• M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.

Crossrefs

Cf. A113095, A113096 (column 1), A113098 (column 2), A113100 (column 2); Tables: A093729 (2-tournaments), A113081 (3-tournaments), A113103 (5-tournaments); diagonals: A113093, A113094.

Programs

PARI

/* Generalized Cook-Kleber Recurrence */
{T(n,k,q=4)=if(n==0,1,if(n<0||k<=0,0,if(n==1,k, if(n>=k,sum(j=1,k,T(n-1,k+(q-1)*j)), sum(j=1,n+1,(-1)^(j-1)*binomial(n+1,j)*T(n,k-j))))))}
for(n=0,10,for(k=0,10,print1(T(n,k),", "));print(""))

PARI

/* Matrix Power Recurrence (Paul D. Hanna) */
{T(n,k,q=4)=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^q)[r-1,c-1])+(M^q)[r-1,c]))); return((M^k)[n+1,1])}
for(n=0,10,for(k=0,10,print1(T(n,k),", "));print(""))

Formula

For n>=k>0: T(n, k) = Sum_{j=1..k} T(n-1, k+3*j); else for k>n>0: T(n, k) = Sum_{j=1..n+1}(-1)^(j-1)*C(n+1, j)*T(n, k-j); with T(0, k)=1 for k>=0. Also, column k of T equals column 0 of the matrix k-th power of triangle A113095, which satisfies the matrix recurrence: A113095(n, k) = [A113095^4](n-1, k-1) + [A113095^4](n-1, k) for n>k>=0.