A093729 -id:A093729 - cp's OEIS frontend

A113077 Column 3 of square table A093729; a(n) gives the number of n-th generation descendents of a node labeled (3) in the tree of tournament sequences, for n>=0.

1, 3, 15, 123, 1656, 36987, 1391106, 89574978, 10036638270, 1986129275673, 703168200003336, 450303519404234922, 526421174510139860241, 1132076561237754405471033, 4507472672071759672232970720

Offset: 0

Paul D. Hanna, Oct 14 2005

nonn

Also equals column 0 of the matrix cube of triangle A097710, which satisfies the matrix recurrence: A097710(n,k) = [A097710^2](n-1,k-1) + [A097710^2](n-1,k) for n>k>=0.

			The tree of tournament sequences of descendents of a node labeled (3) begins:
[3]; generation 1: 3->[4,5,6]; generation 2: 4->[5,6,7,8],
5->[6,7,8,9,10], 6->[7,8,9,10,11,12]; ...
Then a(n) gives the number of nodes in generation n.
Also, a(n+1) = sum of labels of nodes in generation n.

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

Cf. A113078, A113079.

{a(n,q=2)=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^3)[n+1,1])}

A093730 Antidiagonal sums of triangle A093729, which enumerates the number of nodes in the tree of tournament sequences.

Original entry on oeis.org

1, 1, 2, 5, 18, 102, 949, 14731, 386060, 17323052, 1351157580, 185867701560, 45682244004244, 20283964291276804, 16423005586691362832, 24434416299840231799694, 67236458264587977465709983

Offset: 0

Paul D. Hanna, Apr 14 2004

nonn

Related to A008934 (the number of tournament sequences).

G. C. Greubel, Table of n, a(n) for n = 0..86
M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.

Cf. A008934, A093729.

T[n_, k_] := T[n, k] = If[n<0, 0, If[n==0, 1, If[k==0, 0, If[k<=n, T[n, k-1] - T[n-1, k] + T[n-1, 2*k-1] + T[n-1, 2*k], Sum[(-1)^(j-1) * Binomial[n+1, j]*T[n, k-j], {j, 1, n+1}]]]]]; a[n_] := Sum[T[n-k, k], {k, 0, n}]; Table[a[n], {n, 0, 16}] (* Jean-François Alcover, Oct 06 2016, translated from PARI *)

{T(n,k)=if(n<0,0,if(n==0,1,if(k==0,0, if(k<=n,T(n,k-1)-T(n-1,k)+T(n-1,2*k-1)+T(n-1,2*k), sum(j=1,n+1, (-1)^(j-1)*binomial(n+1,j)*T(n,k-j))))))}
a(n)=sum(k=0,n,T(n-k,k))

@CachedFunction
def T(n, k): # T = A093729
    if n<0: return 0
    elif n==0: return 1
    elif k==0: return 0
    elif kA093730(n): return sum(T(n-k,k) for k in range(n+1))
[A093730(n) for n in range(31)] # G. C. Greubel, Feb 22 2024

a(n) = Sum_{k=0..n} A093729(n-k, k).

A008934 Number of tournament sequences: sequences (a_1, a_2, ..., a_n) with a_1 = 1 such that a_i < a_{i+1} <= 2*a_i for all i.

Original entry on oeis.org

1, 1, 2, 7, 41, 397, 6377, 171886, 7892642, 627340987, 87635138366, 21808110976027, 9780286524758582, 7981750158298108606, 11950197013167283686587, 33046443615914736611839942, 169758733825407174485685959261, 1627880269212042994531083889564192

Offset: 0

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it), Jeffrey Shallit

Also number of Meeussen sequences of length n (see the Cook-Kleber reference).
Column 1 of triangle A093729. Also generated by the iteration procedure that constructs triangle A093654. - Paul D. Hanna, Apr 14 2004
a(n) is the number of sequences (u_1,u_2,...,u_n) of positive integers such that u_1=1 and u_i <= 1+ u_1+...+u_{i-1} for 2<=i<=n. For example, omitting parentheses and commas, a(3)=7 counts 111, 112, 113, 121, 122, 123, 124. The difference-between-successive-terms operator is a bijection from the title sequences to these sequences. For example, the tournament sequence (1, 2, 4, 5, 9, 16) bijects to (1,2,1,4,7). (To count tournament sequences by length, the offset should be 1.) - David Callan, Oct 31 2020

			The 7 tournament sequences of length 4 are 1234, 1235, 1236, 1245, 1246, 1247, 1248.

Alois P. Heinz, Table of n, a(n) for n = 0..85 (first 31 terms from T. D. Noe)
M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.
E. Neuwirth, Computing tournament sequence numbers efficiently..., Séminaire Lotharingien de Combinatoire, B47h (2002), 12 pp.
Mauro Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 40:2 (2006), pp. 107-121.
Index entries for sequences related to tournaments

Cf. A058222, A058223, A093729, A093655.

Forms column 0 of triangle A097710.

t[n_?Negative, ] = 0; t[0, ] = 1; t[, 0] = 0; t[n, k_] /; k <= n :=  t[n, k] = t[n, k-1] - t[n-1, k] + t[n-1, 2k-1] + t[n-1, 2 k]; t[n_, k_] /; k > n :=  t[n, k] =Sum[(-1)^(j-1) Binomial[n+1, j]*t[n, k-j] , {j, 1, n+1}]; Table[t[n, 1], {n, 0, 15} ] (* Jean-François Alcover, May 17 2011, after PARI prog. *)

{T(n,k)=if(n<0,0,if(n==0,1,if(k==0,0, if(k<=n,T(n,k-1)-T(n-1,k)+T(n-1,2*k-1)+T(n-1,2*k), sum(j=1,n+1,(-1)^(j-1)*binomial(n+1,j)*T(n,k-j))))))} /*(Cook-Kleber)*/ a(n)=T(n,1)

@CachedFunction
def T(n, k):
    if n<0: return 0
    elif n==0: return 1
    elif k==0: return 0
    elif kA008934(n): return T(n,1)
[A008934(n) for n in range(31)] # G. C. Greubel, Feb 22 2024

From Paul D. Hanna, Apr 14 2004: (Start)
a(n) = A093729(n, 1).
a(n) = A093655(2^n). (End)
a(n) = A097710(n, 0). - Paul D. Hanna, Aug 24 2004
From Benedict W. J. Irwin, Nov 26 2016: (Start)
Conjecture: a(n) is given by a series of nested sums as follows:
  a(2) = Sum_{i=1..2} 1,
  a(3) = Sum_{i=1..2} Sum_{j=1..i+2} 1,
  a(4) = Sum_{i=1..2} Sum_{j=1..i+2} Sum_{k=1..i+j+2} 1,
  a(5) = Sum_{i=1..2} Sum_{j=1..i+2} Sum_{k=1..i+j+2} Sum_{l=1..i+j+k+2} 1.
(End)

A113078 Number of tournament sequences: a(n) gives the number of n-th generation descendents of a node labeled (4) in the tree of tournament sequences.

Original entry on oeis.org

1, 4, 26, 274, 4721, 134899, 6501536, 537766009, 77598500096, 19821981700354, 9077118324755246, 7531446638893873684, 11423775838657143826346, 31914367054676982206368909, 165251261153335414813452988541

Offset: 0

Paul D. Hanna, Oct 14 2005

nonn

Equals column 4 of square table A093729. Also equals column 0 of the matrix 4th power of triangle A097710, which satisfies the matrix recurrence: A097710(n,k) = [A097710^2](n-1,k-1) + [A097710^2](n-1,k) for n>k>=0.

			The tree of tournament sequences of descendents of a node labeled (4) begins:
[4]; generation 1: 4->[5,6,7,8]; generation 2: 5->[6,7,8,9,10],
6->[7,8,9,10,11,12], 7->[8,9,10,11,12,13,14],
8->[9,10,11,12,13,14,15,16]; ...
Then a(n) gives the number of nodes in generation n.
Also, a(n+1) = sum of labels of nodes in generation n.

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

Cf. A113077, A113079, A008934, A113089, A113096, A113098, A113100, A113107, A113109, A113111, A113113.

{a(n,q=2)=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^4)[n+1,1])}

A113079 Number of tournament sequences: a(n) gives the number of n-th generation descendents of a node labeled (5) in the tree of tournament sequences.

Original entry on oeis.org

1, 5, 40, 515, 10810, 376175, 22099885, 2231417165, 393643922005, 123097221805100, 69087264010363930, 70321483026073531730, 130954011392485408662370, 449450774746306949114288795

Offset: 0

Paul D. Hanna, Oct 14 2005

nonn

Equals column 5 of square table A093729. Also equals column 0 of the matrix 5th power of triangle A097710, which satisfies the matrix recurrence: A097710(n,k) = [A097710^2](n-1,k-1) + [A097710^2](n-1,k) for n>k>=0.

			The tree of tournament sequences of descendents of a node labeled (5) begins:
[5]; generation 1: 5->[6,7,8,9,10]; generation 2:
6->[7,8,9,10,11,12], 7->[8,9,10,11,12,13,14],
8->[9,10,11,12,13,14,15,16], 9->[10,11,12,13,14,15,16,17,18],
10->[11,12,13,14,15,16,17,18,19,20]; ...
Then a(n) gives the number of nodes in generation n.
Also, a(n+1) = sum of labels of nodes in generation n.

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

Cf. A113077, A113078, A008934, A113089, A113096, A113098, A113100, A113107, A113109, A113111, A113113.

{a(n,q=2)=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^5)[n+1,1])}

A113081 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 3-tournament sequences, for n>=1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 21, 10, 3, 1, 0, 331, 114, 21, 4, 1, 0, 11973, 2970, 331, 36, 5, 1, 0, 1030091, 182402, 11973, 724, 55, 6, 1, 0, 218626341, 27392682, 1030091, 33476, 1345, 78, 7, 1, 0, 118038692523, 10390564242, 218626341, 3697844, 75695, 2246

Offset: 0

Paul D. Hanna, Oct 14 2005

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

			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,3,10,21,36,55,78,105,136,171,210,...
0,21,114,331,724,1345,2246,3479,5096,7149,...
0,331,2970,11973,33476,75695,148926,265545,440008,...
0,11973,182402,1030091,3697844,10204145,23694838,...
0,1030091,27392682,218626341,1011973796,3416461455,...
0,218626341,10390564242,118038692523,706848765844,...
0,118038692523,10210795262650,166013096151621,...

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

Cf. A113084, A113085 (column 1), A113089 (column 2); tables: A093729 (2-tournaments), A113092 (4-tournaments), A113103 (5-tournaments).

/* Generalized Cook-Kleber Recurrence */ T(n,k,q=3)=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))))))

/* Matrix Power Recurrence (Paul D. Hanna) */ T(n,k,q=3)=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>=k>0: T(n, k) = Sum_{j=1..k} T(n-1, k+2*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. Column k of T equals column 0 of the matrix k-th power of triangle A113084, which satisfies the matrix recurrence: A113084(n, k) = [A113084^3](n-1, k-1) + [A113084^3](n-1, k) for n>k>=0.

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.

Original entry on oeis.org

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

Paul D. Hanna, Oct 14 2005

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.

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

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

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

/* 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(""))

/* 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(""))

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.

A113103 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 5-tournament sequences.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 5, 2, 1, 0, 85, 16, 3, 1, 0, 4985, 440, 33, 4, 1, 0, 1082905, 43600, 1251, 56, 5, 1, 0, 930005021, 16698560, 173505, 2704, 85, 6, 1, 0, 3306859233805, 26098464448, 94216515, 481376, 4985, 120, 7, 1, 0, 50220281721033905

Offset: 0

Paul D. Hanna, Oct 14 2005

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

			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,5,16,33,56,85,120,161,208,261,320,...
0,85,440,1251,2704,4985,8280,12775,18656,26109,...
0,4985,43600,173505,481376,1082905,2122800,3774785,6241600,...
0,1082905,16698560,94216515,337587520,930005021,2156566656,...
0,930005021,26098464448,210576669921,978162377600,...
0,3306859233805,172513149018752,2002383115518243,...
0,50220281721033905,4938593053649344000,82856383278525698433,...

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

Cf. A113106, A113107 (column 1), A113109 (column 2), A113111 (column 3), A113113 (column 4); Tables: A093729 (2-tournaments), A113081 (3-tournaments), A113092 (4-tournaments).

/* Generalized Cook-Kleber Recurrence */
{T(n,k,q=5)=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(""))

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

For n>=k>0: T(n, k) = Sum_{j=1..k} T(n-1, k+4*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. Column k of T equals column 0 of the matrix k-th power of triangle A113106, which satisfies the matrix recurrence: A113106(n, k) = [A113106^5](n-1, k-1) + [A113106^5](n-1, k) for n>k>=0.

A113080 Square table, read by antidiagonals, where T(n,k) equals the number of k-tournament sequences of length n for k>=1, with T(0,k) = 1 for k>=1 and T(n,1) = 0 for n>0.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 7, 10, 3, 1, 0, 41, 114, 27, 4, 1, 0, 397, 2970, 693, 56, 5, 1, 0, 6377, 182402, 52812, 2704, 100, 6, 1, 0, 171886, 27392682, 12628008, 481376, 8125, 162, 7, 1, 0, 7892642, 10390564242, 9924266772, 337587520, 2918750, 20502, 245, 8

Offset: 1

Paul D. Hanna, Oct 14 2005

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

			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,2,10,27,56,100,162,245,352,486,650,...
0,7,114,693,2704,8125,20502,45619,92288,173259,...
0,41,2970,52812,481376,2918750,13399506,50216915,...
0,397,182402,12628008,337587520,4976321250,48633051942,...
0,6377,27392682,9924266772,978162377600,42197834315625,...
0,171886,10390564242,26507035453923,12088945462984960,...
0,7892642,10210795262650,246323730279500082,...

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

Columns: A008934 (k=2), A113089 (k=3), A113100 (k=4), A113113 (k=5); related tables: A093729 (k=2), A113081 (k=3), A113092 (k=4), A113103 (k=5).

{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^k)[r-1,c-1])+(M^k)[r-1,c]))); return((M^(k-1))[n+1,1])}

cp's OEIS Frontend

A113077 Column 3 of square table A093729; a(n) gives the number of n-th generation descendents of a node labeled (3) in the tree of tournament sequences, for n>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A093730 Antidiagonal sums of triangle A093729, which enumerates the number of nodes in the tree of tournament sequences.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A008934 Number of tournament sequences: sequences (a_1, a_2, ..., a_n) with a_1 = 1 such that a_i < a_{i+1} <= 2*a_i for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A113078 Number of tournament sequences: a(n) gives the number of n-th generation descendents of a node labeled (4) in the tree of tournament sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A113079 Number of tournament sequences: a(n) gives the number of n-th generation descendents of a node labeled (5) in the tree of tournament sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A113081 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 3-tournament sequences, for n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula