A008934 - OEIS

%I #57 Feb 22 2024 02:42:01

%S 1,1,2,7,41,397,6377,171886,7892642,627340987,87635138366,

%T 21808110976027,9780286524758582,7981750158298108606,

%U 11950197013167283686587,33046443615914736611839942,169758733825407174485685959261,1627880269212042994531083889564192

%N 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.

%C Also number of Meeussen sequences of length n (see the Cook-Kleber reference).

%C Column 1 of triangle A093729. Also generated by the iteration procedure that constructs triangle A093654. - _Paul D. Hanna_, Apr 14 2004

%C 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

%H Alois P. Heinz, <a href="/A008934/b008934.txt">Table of n, a(n) for n = 0..85</a> (first 31 terms from T. D. Noe)

%H M. Cook and M. Kleber, <a href="https://doi.org/10.37236/1522">Tournament sequences and Meeussen sequences</a>, Electronic J. Comb. 7 (2000), #R44.

%H E. Neuwirth, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s47neuwirth.html">Computing tournament sequence numbers efficiently...</a>, Séminaire Lotharingien de Combinatoire, B47h (2002), 12 pp.

%H Mauro Torelli, <a href="http://www.numdam.org/item?id=ITA_2006__40_2_107_0">Increasing integer sequences and Goldbach's conjecture</a>, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 40:2 (2006), pp. 107-121.

%H <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>

%F From _Paul D. Hanna_, Apr 14 2004: (Start)

%F a(n) = A093729(n, 1).

%F a(n) = A093655(2^n). (End)

%F a(n) = A097710(n, 0). - _Paul D. Hanna_, Aug 24 2004

%F From _Benedict W. J. Irwin_, Nov 26 2016: (Start)

%F Conjecture: a(n) is given by a series of nested sums as follows:

%F   a(2) = Sum_{i=1..2} 1,

%F   a(3) = Sum_{i=1..2} Sum_{j=1..i+2} 1,

%F   a(4) = Sum_{i=1..2} Sum_{j=1..i+2} Sum_{k=1..i+j+2} 1,

%F   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.

%F (End)

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

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

%o (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)

%o (SageMath)

%o @CachedFunction

%o def T(n, k):

%o     if n<0: return 0

%o     elif n==0: return 1

%o     elif k==0: return 0

%o     elif k<n+1: return T(n,k-1) - T(n-1,k) + T(n-1,2*k-1) + T(n-1,2*k)

%o     else: return sum((-1)^(j-1)*binomial(n+1,j)*T(n, k-j) for j in range(1,n+2))

%o def A008934(n): return T(n,1)

%o [A008934(n) for n in range(31)] # _G. C. Greubel_, Feb 22 2024

%Y Cf. A058222, A058223, A093729, A093655.

%Y Forms column 0 of triangle A097710.

%K nonn,nice,easy

%O 0,3

%A Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it), _Jeffrey Shallit_