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

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

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

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)

Example

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

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

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 k<n+1: return T(n, k-1) - T(n-1, k) + T(n-1, 2*k-1) + T(n-1, 2*k)
    else: return sum((-1)^(j-1)*binomial(n+1, j)*T(n, k-j) for j in range(1, n+2))
def A008934(n): return T(n, 1)
[A008934(n) for n in range(31)] # G. C. Greubel, Feb 22 2024

Crossrefs

Cf. A058222, A058223, A093729, A093655.

Forms column 0 of triangle A097710.

Sequence in context: A163921 A213434 A331920 * A084871 A340645 A122942

Adjacent sequences: A008931 A008932 A008933 * A008935 A008936 A008937

Keyword

nonn,nice,easy

Author

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

Status

approved