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.

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

Offset: 0

Author

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

Keywords

• nonn
• nice
• easy

Comments

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

Examples

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

Links

• 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

Crossrefs

Cf. A058222, A058223, A093729, A093655.

Forms column 0 of triangle A097710.

Programs

Mathematica

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

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))))))} /*(Cook-Kleber)*/ a(n)=T(n,1)

SageMath

@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

Formula

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)