A058222 -id:A058222 - 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.

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)

A002083 Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 22, 42, 84, 165, 330, 654, 1308, 2605, 5210, 10398, 20796, 41550, 83100, 166116, 332232, 664299, 1328598, 2656866, 5313732, 10626810, 21253620, 42505932, 85011864, 170021123, 340042246, 680079282, 1360158564

Offset: 1

N. J. A. Sloane

Number of compositions p(1) + p(2) + ... + p(k) = n of n into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j), see example - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 29 2001 (clarified by Joerg Arndt, Feb 01 2013)
a(n) is the number of sequences (b(1),b(2),...) of unspecified length satisfying b(1) = 1, 1 <= b(i) <= 1 + Sum[b(j),{j,i-1}] for i>=2, Sum[b(i)] = n-1. For example, a(5) = 3 counts (1, 1, 1, 1), (1, 2, 1), (1, 1, 2). These sequences are generated by the Mathematica code below. - David Callan, Nov 02 2005
a(n+1) is the number of padded compositions (d_1,d_2,...,d_n) of n satisfying d_i <= i for all i. A padded composition of n is obtained from an ordinary composition (c_1,c_2,...,c_r) of n (r >= 1, each c_i >= 1, Sum_{i=1..r} c_i = n) by inserting c_i - 1 zeros immediately after each c_i. Thus (3,1,2) -> (3,0,0,1,2,0) is a padded composition of 6 and a padded composition of n has length n. For example, with n=4, a(5) counts (1,1,1,1), (1,1,2,0), (1,2,0,1). - David Callan, Feb 04 2006
From David Callan, Sep 25 2006: (Start)
a(n) is the number of ordered trees on n edges in which (i) every node (= non-root non-leaf vertex) has at least 2 children and (ii) each leaf is either the leftmost or rightmost child of its parent.
For example, a(4)=2 counts
    ./\.../\
    /\...../\,
  and a(5)=3 counts
    .|.......|....../|\
    / \...../ \...../ \
    ../\.../\.
(End)
Starting with offset 2 = eigensequence of triangle A101688 and row sums of triangle A167948. - Gary W. Adamson, Nov 15 2009
If we remove the condition that a(2) = 1, then the resulting sequence is A045690 minus the first term. - Chai Wah Wu, Nov 08 2022

			From _Joerg Arndt_, Feb 01 2013: (Start)
The a(7) = 11 compositions p(1) + p(2) + ... + p(k) = 7 of 7 into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j) are
[ 1]  [ 1 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 1 2 ]
[ 3]  [ 1 1 1 1 2 1 ]
[ 4]  [ 1 1 1 1 3 ]
[ 5]  [ 1 1 1 2 1 1 ]
[ 6]  [ 1 1 1 2 2 ]
[ 7]  [ 1 1 1 3 1 ]
[ 8]  [ 1 1 2 1 1 1 ]
[ 9]  [ 1 1 2 1 2 ]
[10]  [ 1 1 2 2 1 ]
[11]  [ 1 1 2 3 ]
(End)

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.28.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..3325 (first 200 terms from T. D. Noe)
Magnus Aspenberg and Rodrigo Perez, Control of cancellations that restrain the growth of a binomial recursion, arXiv:1006.1340 [math.CO], 2010. Mentions this sequence.
P. Capell and T. V. Narayana, On knock-out tournaments, Canad. Math. Bull. 13 1970 105-109.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
G. Kreweras, and P. Moszkowski, A new enumerative property of the Narayana numbers, Journal of statistical planning and inference 14.1 (1986): 63-67.
D. Levin, L. Pudwell, M. Riehl and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
J. W. Moon, R. K. Guy and N. J. A. Sloane, Correspondence, 1988
T. V. Narayana, Quelques résultats relatifs aux tournois "knock-out" et leurs applications aux comparaisons aux paires, C. R. Acad. Sci. Paris, Series A-B 267 1968 A32-A33.
T. V. Narayana and J. Zidek, Contributions to the theory of tournaments I, Cahiers du Bur. Univ. de Rech. Oper., 13 (1969), 1-18. [MR 0256734, 41 #1390]
John Riordan and N. J. A. Sloane, Correspondence, 1974
M. A. Stern, 5. Aufgaben., Journal für die reine und angewandte Mathematik (Crelle's journal), volume 18, 1838, p. 100.
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.
B. E. Wynne & N. J. A. Sloane, Correspondence, 1976-84
B. E. Wynne & T. V. Narayana, Tournament configuration, weighted voting, and partitioned catalans, Preprint.
Bayard Edmund Wynne and T. V. Narayana, Tournament configuration and weighted voting, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78.
Index entries for "core" sequences

Cf. A045690. A058222 gives sums of words.
Cf. A001045, A002487, A101688, A167948.
Cf. A242729.
Bisections: A245094, A259858.

a002083 n = a002083_list !! (n-1)
a002083_list = 1 : f [1] where
   f xs = x : f (x:xs) where x = sum $ take (div (1 + length xs) 2) xs
-- Reinhard Zumkeller, Dec 27 2011

A002083 := proc(n) option remember; if n<=3 then 1 elif n mod 2 = 0 then 2*procname(n-1) else 2*procname(n-1)-procname((n-1)/2); end if; end proc:
a := proc(n::integer) # A002083 Narayana-Zidek-Capell numbers: a(2n)=2a(2n-1), a(2n+1)=2a(2n)-a(n). local k; option remember; if n = 0 then 1 else add(K(n-k+1, k)*procname(n - k), k = 1 .. n); #else add(K((n-k)!, k!)*procname(n - k), k = 1 .. n); end if end proc; K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n then KC := 1 else KC := 0 end if; end proc; # Thomas Wieder, Jan 13 2008

a[1] = 1; a[n_] := a[n] = Sum[a[k], {k, n/2, n-1} ]; Table[ a[n], {n, 2, 70, 2} ] (* Robert G. Wilson v, Apr 22 2001 *)
bSequences[1]={ {1} }; bSequences[n_]/;n>=2 := bSequences[n] = Flatten[Table[Map[Join[ #, {i}]&, bSequences[n-i]], {i, Ceiling[n/2]}], 1] (* David Callan *)
a=ConstantArray[0,20]; a[[1]]=1; a[[2]]=1; Do[If[EvenQ[n],a[[n]]=2a[[n-1]],a[[n]]=2a[[n-1]]-a[[(n-1)/2]]];,{n,3,20}]; a (* Vaclav Kotesovec, Nov 19 2012 *)

PARI
```
a(n)=if(n<3,n>0,2*a(n-1)-(n%2)*a(n\2))
```

a(n)=local(A=1+x);for(i=1,n,A=(1-x-x^2*subst(A,x,x^2+O(x^n)))/(1-2*x));polcoeff(A,n) \\ Paul D. Hanna, Mar 17 2010

from functools import lru_cache
@lru_cache(maxsize=None)
def A002083(n): return 1 if n <=3 else (A002083(n-1)<<1)-(A002083(n>>1) if n&1 else 0) # Chai Wah Wu, Nov 07 2022

a(1)=1, else a(n) is sum of floor(n/2) previous terms.
Conjecture: lim_{n->oo} a(n)/2^(n-3) = a constant ~0.633368 (=2*A242729). - Gerald McGarvey, Jul 18 2004
First column of A155092. - Mats Granvik, Jan 20 2009
a(n+2) = A037254(n,1) = A037254(n,floor(n/2)+1). - Reinhard Zumkeller, Nov 18 2012
Limit is equal to 0.633368347305411640436713144616576659... = 2*Atkinson-Negro-Santoro constant = 2*A242729, see Finch's book, chapter 2.28 (Erdős' Sum-Distinct Set Constant), pp. 189, 552. - Vaclav Kotesovec, Nov 19 2012
a(n) is the permanent of the (n-1) X (n-1) matrix with (i, j) entry = 1 if i-1 <= j <= 2*i-1 and = 0 otherwise. - David Callan, Nov 02 2005
a(n) = Sum_{k=1..n} K(n-k+1, k)*a(n-k), where K(n,k) = 1 if 0 <= k AND k <= n and K(n,k)=0 else. (Several arguments to the K-coefficient K(n,k) can lead to the same sequence. For example, we get A002083 also from a(n) = Sum_{k=1..n} K((n-k)!,k!)*a(n-k), where K(n,k) = 1 if 0 <= k <= n and 0 else. See also the comment to a similar formula for A002487.) - Thomas Wieder, Jan 13 2008
G.f. satisfies: A(x) = (1-x - x^2*A(x^2))/(1-2x). - Paul D. Hanna, Mar 17 2010

Definition clarified by Chai Wah Wu, Nov 08 2022

A058223 Tree of Meeussen sequences read across rows.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 5, 6, 7, 8, 8, 10, 11, 12, 8, 9, 11, 12, 13, 8, 9, 10, 12, 13, 14, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 14, 9, 10, 11, 12, 13, 14, 15, 9, 10, 11, 12, 13, 14, 15, 16, 13, 16, 18, 19, 20, 13, 15, 18, 20, 21, 22, 13, 14, 16, 19, 21, 22, 23, 13, 14, 15, 17, 20, 22, 23, 24

Offset: 0

N. J. A. Sloane, Dec 02 2000

Labels on paths down the tree are Meeussen Sequences: b(1)=1 < b(2) <...< b(n) such that b(n)-1 has a unique representation as a sum of distinct b(i) (i

			Irregular triangle begins:
  1;
  2;
  3,4;
  5,6,7,5,6,7,8;
  ...

Sean A. Irvine, Table of n, a(n) for n = 0..10000
M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.

A008934 gives number of children at level n. Cf. A058222.

A058311 Number of nodes at n-th level in tree in which top node is 1; each node k has children labeled k, k+1, ..., (k+1)^2 at next level.

Original entry on oeis.org

1, 4, 48, 7918, 463339346, 7134188685100826388, 13246386641449904934758023373599438217628, 643152870463337226096320122089499144560533929707886143570111588898313745804013188842

Offset: 0

N. J. A. Sloane, Dec 09 2000

nonn

Triggered by a comment from Michael Kleber, Dec 08 2009, who said: The algorithm in my paper with Cook lets you compute the equivalent sequence where the children of a node labeled (k) are labeled with all the integers in the interval [p(k), q(k)] where p,q are any polynomials you like (in the paper, p(k)=k+1 and q(k)=2k). For a bunch of p,q the resulting sequence is well known, e.g., p(k)=1, q(k)=k+1 is the Catalan numbers.

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

Cf. A008934, A058222, A147780, A147794.

M:=4;
L[0]:=[1]; a[0]:=1;
for n from 1 to M do
L[n]:=[];
t1:=L[n-1];
tc:=nops(t1);
for i from 1 to tc do
t2:=t1[i];
for j from t2 to (t2+1)^2 do
L[n]:=[op(L[n]),j]; od:
a[n]:=nops(L[n]);
#lprint(n,L[n],a[n]);
od:
od:
[seq(a[n],n=0..M)];
# See the reference for a better way to compute this!
p := proc(n,k) option remember; local j ; if n = 1 then k^2+k+2; # (k+1)^2-(k-1) else sum( procname(n-1,j),j=k..(k+1)^2) ; fi; expand(%) ; end proc:
A058311 := proc(n) if n = 0 then 1 ; else subs(k=1, p(n,k)) ; fi; end proc:
for n from 0 do printf("%d,\n", A058311(n)) ; od: # R. J. Mathar, May 04 2009

p[n_, k_] := p[n, k] = If[n == 1, k^2+k+2, Sum[p[n-1, j], {j, k, (k+1)^2}]];
a[n_] := If[n == 0, 1, p[n, 1]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 7}] (* Jean-François Alcover, Jun 26 2023, after R. J. Mathar *)

Corrected, with Maple program, by N. J. A. Sloane, May 03 2009. Thanks to Max Alekseyev for pointing out that something was wrong.

Replaced a(4), added three more terms - R. J. Mathar, May 04 2009

Showing 1-4 of 4 results.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A002083 Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A058223 Tree of Meeussen sequences read across rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A058311 Number of nodes at n-th level in tree in which top node is 1; each node k has children labeled k, k+1, ..., (k+1)^2 at next level.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions