login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000571 Number of different scores that are possible in an n-team round-robin tournament.
(Formerly M1189 N0459)
17
1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, 158808, 531469, 1799659, 6157068, 21258104, 73996100, 259451116, 915695102, 3251073303, 11605141649, 41631194766, 150021775417, 542875459724, 1972050156181, 7189259574618, 26295934251565, 96478910768821, 354998461378719, 1309755903513481 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

A tournament is a complete graph with one arrow on each edge; the score of a node is its out-degree; a(n) is number of different score sequences when there are n nodes.

Also number of nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0=p_{n+1}=0, 2p_i -(p_{i+1}+p_{i-1}) <= 1, p_i >= 0, i=1, ..., n.

Also number of score sequences of length n: weakly increasing sequences a[0,1,...,n-1] where sum(j=0..k, a[j]) >= k*(k+1)/2 and sum(j=0..n-1, a[j]) = (n-1)*n/2; same as weak compositions of n*(n-1) with partial sums up to position k at least k*(k+1)/2; see example. - Joerg Arndt, Mar 29 2014

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 21.

J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 68 (but table contains errors).

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

LINKS

Sean A. Irvine, Table of n, a(n) for n = 0..100

C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the x-rays of permutations

Sebrina Ruth Cropper, Ranking Score Vectors of Tournaments (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies. - From N. J. A. Sloane, Jun 10 2012

John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968), see page 88.

T. V. Narayana and D. H. Best, Computation of the number of score sequences in round-robin tournaments, Canad. Math. Bull., 7 (1964), 133-136 (but table contains errors).

D. Recoskie and J. Sawada, The Taming of Two Alley CATs, 2012.

J. Riordan, The number of score sequences in tournaments, J. Combin. Theory, 5 (1968), 87-89. [The main result of this paper seems to be wrong - see A210726.]

Eric Weisstein's World of Mathematics, Score Sequence.

Index entries for sequences related to tournaments

FORMULA

Let f_1(T, E)=1 if T=E>=0, =0 else; f_n(T, E)=0 if T-E<C(n-1, 2), =Sum_{k=0..E} f_{n-1}(T-E, k) else; then a(n)=Sum_{E=[n/2]..n-1} f_n(C(n, 2), E), n >= 2.

Riordan seems to claim that a(n) = 2*a(n-1)-a(n-2) + A046919(n), but this is not true. - N. J. A. Sloane, May 06 2012.

Logarithmic derivative yields A145855, the number of n-member subsets of 1..2n-1 whose elements sum to a multiple of n. - Paul D. Hanna, Jul 17 2013

a(n) = (1/n) * Sum_{k=1..n} A145855(k) * a(n-k) for n>0 with a(0)=1. - Paul D. Hanna, Jul 17 2013

EXAMPLE

a(3)=2, since either one node dominates [ 2,1,0 ] or each node defeats the next [ 1,1,1 ].

G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 22*x^6 + 59*x^7 + 167*x^8 +...

where the logarithm begins:

log(A(x)) = x + x^2/2 + 4*x^3/3 + 9*x^4/4 + 26*x^5/5 + 76*x^6/6 +...+ A145855(n)*x^n/n +...

From Joerg Arndt, Mar 29 2014: (Start)

The a(6) = 22 score sequences of length 6 are:

01:  [ 0 1 2 3 4 5 ]

02:  [ 0 1 2 4 4 4 ]

03:  [ 0 1 3 3 3 5 ]

04:  [ 0 1 3 3 4 4 ]

05:  [ 0 2 2 2 4 5 ]

06:  [ 0 2 2 3 3 5 ]

07:  [ 0 2 2 3 4 4 ]

08:  [ 0 2 3 3 3 4 ]

09:  [ 0 3 3 3 3 3 ]

10:  [ 1 1 1 3 4 5 ]

11:  [ 1 1 1 4 4 4 ]

12:  [ 1 1 2 2 4 5 ]

13:  [ 1 1 2 3 3 5 ]

14:  [ 1 1 2 3 4 4 ]

15:  [ 1 1 3 3 3 4 ]

16:  [ 1 2 2 2 3 5 ]

17:  [ 1 2 2 2 4 4 ]

18:  [ 1 2 2 3 3 4 ]

19:  [ 1 2 3 3 3 3 ]

20:  [ 2 2 2 2 2 5 ]

21:  [ 2 2 2 2 3 4 ]

22:  [ 2 2 2 3 3 3 ]

(End)

PROG

(PARI) {A145855(n)=sumdiv(n, d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/(2*n))}

{a(n)=polcoeff(exp(sum(m=1, n, A145855(m)*x^m/m)+x*O(x^n)), n)} \\ Paul D. Hanna, Jul 17 2013

CROSSREFS

Cf. A007747, A210726, A145855.

Sequence in context: A092920 A177377 A035053 * A077003 A210726 A046917

Adjacent sequences:  A000568 A000569 A000570 * A000572 A000573 A000574

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(11) corrected by Kenneth Winston, Aug 05 1978

More terms from David W. Wilson

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 23 11:33 EDT 2014. Contains 245994 sequences.