cp's OEIS Frontend

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.

%I A008934 #57 Feb 22 2024 02:42:01
%S A008934 1,1,2,7,41,397,6377,171886,7892642,627340987,87635138366,
%T A008934 21808110976027,9780286524758582,7981750158298108606,
%U A008934 11950197013167283686587,33046443615914736611839942,169758733825407174485685959261,1627880269212042994531083889564192
%N 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.
%C A008934 Also number of Meeussen sequences of length n (see the Cook-Kleber reference).
%C A008934 Column 1 of triangle A093729. Also generated by the iteration procedure that constructs triangle A093654. - _Paul D. Hanna_, Apr 14 2004
%C A008934 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 A008934 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 A008934 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 A008934 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 A008934 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 A008934 <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%F A008934 From _Paul D. Hanna_, Apr 14 2004: (Start)
%F A008934 a(n) = A093729(n, 1).
%F A008934 a(n) = A093655(2^n). (End)
%F A008934 a(n) = A097710(n, 0). - _Paul D. Hanna_, Aug 24 2004
%F A008934 From _Benedict W. J. Irwin_, Nov 26 2016: (Start)
%F A008934 Conjecture: a(n) is given by a series of nested sums as follows:
%F A008934   a(2) = Sum_{i=1..2} 1,
%F A008934   a(3) = Sum_{i=1..2} Sum_{j=1..i+2} 1,
%F A008934   a(4) = Sum_{i=1..2} Sum_{j=1..i+2} Sum_{k=1..i+j+2} 1,
%F A008934   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 A008934 (End)
%e A008934 The 7 tournament sequences of length 4 are 1234, 1235, 1236, 1245, 1246, 1247, 1248.
%t A008934 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 A008934 (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 A008934 (SageMath)
%o A008934 @CachedFunction
%o A008934 def T(n, k):
%o A008934     if n<0: return 0
%o A008934     elif n==0: return 1
%o A008934     elif k==0: return 0
%o A008934     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 A008934     else: return sum((-1)^(j-1)*binomial(n+1,j)*T(n, k-j) for j in range(1,n+2))
%o A008934 def A008934(n): return T(n,1)
%o A008934 [A008934(n) for n in range(31)] # _G. C. Greubel_, Feb 22 2024
%Y A008934 Cf. A058222, A058223, A093729, A093655.
%Y A008934 Forms column 0 of triangle A097710.
%K A008934 nonn,nice,easy
%O A008934 0,3
%A A008934 Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it), _Jeffrey Shallit_