A000571 -id:A000571 - cp's OEIS frontend

A274098 Number of ways the most probable score sequence happens in an n-person round-robin tournament.

1, 2, 6, 24, 280, 8640, 233520, 23157120, 5329376640, 1314169920000, 1016970317932800, 1772428331094220800, 3441650619022551936000, 22088285526822118789785600, 291368298787833283829100288000

Offset: 1

N. J. A. Sloane, Jun 11 2016

nonn

There are n players, each player plays all the others, so there are n(n-1)/2 games and 2^(n(n-1)/2) possible outcomes (there are no ties). At the end of the tournament we record the score sequence, which is the partition of n(n-1)/2 into n parts specified by the numbers of victories of the players. Then a(n) is the number of ways the most probable score sequence can occur. The number of different score sequences is given by A000571(n).

			With 4 players there 6 = 4*3/2 games played with 2^(4*3/2) = 64 possible outcomes.
The possible score sequences and the number of ways each can happen are as follows:
3210 24 (meaning one player won 3 times, one player won twice, one player won once, and one player had no wins, and this can happen in 24 ways)
3111 8
2220 8
2211 24
The most probable score sequence is either 3210 or 2211, and either can happen in 24 ways, so a(4)=24. (Usually there is a unique most probable score sequence.)
The score sequences with 4 players are partitions of 6 into 4 parts.
For 6 players the most probable score sequence is 4,3,3,2,2,1. It is unique, and happens in 8640 of the 2^15 possible outcomes, so a(6) = 8640.

P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Pure Appl. Math., 49 (1920), 1-36. Gives a(1) to a(9).

Shalosh B. Ekhad, On the Most Commonly-Occurring Score Vectors for American Tournaments of n-players, and their Corresponding Records, published in the personal journal of Shalosh B. Ekhad and Doron Zeilberger, Jun 13 2016; Local copy, pdf file only, no active links
P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Pure Appl. Math., 49 (1920), 1-36. Gives a(1) to a(9). [Annotated scanned copy, scanned at 300 dpi. Do not replace with a smaller file as the print is very tiny and hard to read.]

Cf. A000571.

a(1)-a(9) confirmed by N. J. A. Sloane, Jun 11 2016

a(10)-a(15) from Shalosh B. Ekhad, Jun 13 2016

A345470 Number of self-complementary score sequences that are possible in an n-team round-robin tournament.

Original entry on oeis.org

1, 1, 1, 2, 2, 5, 6, 15, 19, 48, 64, 161, 223, 557, 796, 1971, 2887, 7090, 10596, 25826, 39256, 95016, 146533, 352411, 550328, 1315827, 2077418, 4940587, 7876036, 18639221, 29971423, 70608885, 114422037, 268436473, 438068242

Offset: 0

Howard Givner, Jun 20 2021

nonn

See A000571 for the definition of a score sequence.

A self-complementary score sequence W is a score sequence of win counts such that W = {s(1), s(2), ..., s(n)} and its complement, L={n-1-s(n), n-1-s(n-1), ..., n-1-s(1)}, a score sequence of loss counts, are identical.

			For n = 4 there are 4 score sequences of which only 2, those marked with an asterisk, are self-complementary.  These are the sequences for n=4.
    {0,1,2,3} *
    {0,2,2,2}
    {1,1,1,3}
    {1,1,2,2} *
For n = 5, there are 9 score sequences of which only 5, those marked with an asterisk, are self-complementary.  These are the sequences for n=5.
    {0,1,2,3,4} *
    {0,1,3,3,3}
    {0,2,2,2,4} *
    {0,2,2,3,3}
    {1,1,2,3,3} *
    {1,1,1,3,4}
    {1,1,2,2,4}
    {1,2,2,2,3} *
    {2,2,2,2,2} *

Paul K. Stockmeyer, Table of n, a(n) for n = 0..500
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, J. Integer Seq. 26 (2023), Article 23.5.2.

Cf. A000571.

a(30) corrected by Howard Givner, Jun 28 2021

a(0)=1 prepended and a(1) changed from 0 to 1 by Howard Givner, Feb 22 2022

A351822 a(n) is the number of different score sequences that are possible for strong tournaments on n vertices.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 7, 21, 61, 184, 573, 1835, 5969, 19715, 66054, 223971, 767174, 2651771, 9240766, 32436016, 114596715, 407263306, 1455145050, 5224710466, 18843677124, 68243466611, 248090964092, 905092211818, 3312816854525, 12162610429661, 44780896121875, 165316324574671, 611819769698967

Offset: 0

Paul K. Stockmeyer, Feb 20 2022

nonn

See A000571 for the definition of a tournament and its score sequence. A tournament is strong if every two vertices are mutually reachable by directed paths. Alternatively, a tournament is strong if it contains a directed Hamiltonian cycle.

A sequence (s_1 <= s_2 <= ... <= s_n) of integers is the score sequence of a strong tournament iff Sum_{i=1..r} s_i > binomial(r,2) for 1 <= r < n and Sum_{i=1..n} s_i = binomial(n,2).

			The seven strong score sequences of length six are
  (1,1,2,3,4,4),
  (1,1,3,3,3,4),
  (1,2,2,2,4,4),
  (1,2,2,3,3,4),
  (1,2,3,3,3,3),
  (2,2,2,2,3,4),
  (2,2,2,3,3,3).

Paul K. Stockmeyer, Table of n, a(n) for n = 0..500
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, arXiv:2202.05238 [math.CO], 2022.
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, J. Integer Seq. 26 (2023), Article 23.5.2.

Cf. A000571.

For n >= 2, a(n) = Sum_{E=floor(n/2)..n-1} g_n(binomial(n, 2), E), where g_1(T, E) = [T=E]; g_n(T, E)=0 if T-E <= binomial(n-1, 2) and g_n(T, E) = Sum_{k=0..E} g_{n-1}(T-E, k) otherwise.

a(n) ~ c * 4^n / n^(5/2), where c = 0.202756471582408229... - Vaclav Kotesovec, Feb 21 2022

A047733 Number of score sequences in tournament with n players, when 6 points are awarded in each game.

Original entry on oeis.org

1, 4, 25, 213, 2131, 23729, 283681, 3574222, 46866712, 634204317, 8803501719, 124799484286, 1800669899917, 26374204955323, 391331674556361, 5872226011836383, 88993282402441857, 1360552594176453319

Offset: 1

David W. Wilson

nonn

Qihao Ye, Table of n, a(n) for n = 1..808

Cf. A000571, A007747, A047729, A047730, A047731.

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}) <= 6, p_i >= 0, i=1, ..., n.

A047734 Number of score sequences in tournament with n players, when 7 points are awarded in each game.

Original entry on oeis.org

1, 4, 32, 318, 3692, 47536, 657040, 9563961, 144847330, 2263567060, 36281911266, 593856894136, 9892591942306, 167278802007062, 2865331941321996, 49634901816988932, 868329574365547207

Offset: 1

David W. Wilson

nonn

Qihao Ye, Table of n, a(n) for n = 1..770

Cf. A000571, A007747, A047729-A047731.

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}) <= 7, p_i >= 0, i=1, ..., n.

A047735 Number of score sequences in tournament with n players, when 8 points are awarded in each game.

Original entry on oeis.org

1, 5, 41, 459, 6033, 88055, 1379405, 22763356, 390859501, 6924877318, 125837754305, 2335060741480, 44097660919285, 845336236860344, 16415016380975679, 322349248087651458, 6392828942756895663

Offset: 1

David W. Wilson

nonn

Qihao Ye, Table of n, a(n) for n = 1..739

Cf. A000571, A007747, A047729, A047730, A047731.

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}) <= 8, p_i >= 0, i=1, ..., n.

A047736 Number of score sequences in tournament with n players, when 9 points are awarded in each game.

Original entry on oeis.org

1, 5, 50, 630, 9285, 151652, 2658131, 49061128, 942055396, 18662965393, 379195887105, 7867076520341, 166102773740621, 3559787677138284, 77278541685154409, 1696519572528877274

Offset: 1

David W. Wilson

nonn

Qihao Ye, Table of n, a(n) for n = 1..714

Cf. A000571, A007747, A047729, A047730, A047731.

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}) <= 9, p_i >= 0, i=1, ..., n.

A047737 Number of score sequences in tournament with n players, when 10 points are awarded in each game.

Original entry on oeis.org

1, 6, 61, 846, 13771, 248623, 4816659, 98277943, 2086173336, 45688601782, 1026218795502, 23536101285148, 549336702455778, 13014352354398322, 312313455482385108, 7579157833713922471

Offset: 1

David W. Wilson

nonn

Qihao Ye, Table of n, a(n) for n = 1..692

Cf. A000571, A007747, A047729, A047730, A047731.

Nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0 = p_{n+1} = 0, 2*p_i - (p_{i+1} + p_{i-1}) <= 10, p_i >= 0, i = 1..n.

A348532 a(n) is the number of multisets of integers that are possible to reach by starting with n occurrences of 0 and by splitting and reverse splitting.

Original entry on oeis.org

1, 1, 2, 2, 7, 9, 43, 59, 338, 490, 3097, 4639, 31283, 48107, 338553, 531469, 3857036, 6157068, 45713546, 73996100

Offset: 0

Tejo Vrush, Oct 21 2021

Splitting is taking 2 occurrences of the same integer and incrementing one of them by 1 and decrementing the other occurrence by 1.

Reverse splitting is taking two elements with a difference of 2 and incrementing the smaller one by 1 and decrementing the larger one by 1. It is the opposite of splitting.

			For n = 5, the multisets are as follows:
  {{0,0,0,0,0}}   {{-1,0,0,0,1}}   {{-1,-1,0,1,1}}
  {{-1,-1,0,0,2}} {{-1,-1,-1,1,2}} {{-2,0,0,1,1}}
  {{-2,0,0,0,2}}  {{-2,-1,1,1,1}}  {{-2,-1,0,1,2}}.
  Therefore, a(5) = 9.
For n = 6, the multisets are as follows:
  {{0,0,0,0,0,0}}     {{-1,0,0,0,0,1}}     {{-1,-1,0,0,1,1}}
  {{-1,-1,0,0,0,2}}   {{-1,-1,-1,1,1,1}}   {{-1,-1,-1,0,1,2}}
  {{-1,-1,-1,0,0,3}}* {{-1,-1,-1,-1,2,2}}* {{-1,-1,-1,-1,1,3}}*
  {{-2,0,0,0,1,1}}    {{-2,0,0,0,0,2}}     {{-2,-1,0,1,1,1}}
  {{-2,-1,0,0,1,2}}   {{-2,-1,0,0,0,3}}*   {{-2,-1,-1,1,1,2}}
  {{-2,-1,-1,0,2,2}}  {{-2,-1,-1,0,1,3}}   {{-2,-1,-1,-1,2,3}}*
  {{-2,-2,1,1,1,1}}*  {{-2,-2,0,1,1,2}}    {{-2,-2,0,0,2,2}}
  {{-2,-2,0,0,1,3}}   {{-2,-2,-1,1,2,2}}   {{-2,-2,-1,1,1,3}}
  {{-2,-2,-1,0,2,3}}  {{-2,-2,-2,2,2,2}}*  {{-2,-2,-2,1,2,3}}*
  {{-3,0,0,0,0,3}}*   {{-3,0,0,0,1,2}}*    {{-3,0,0,1,1,1}}*
  {{-3,-1,1,1,1,1}}*  {{-3,-1,0,1,1,2}}    {{-3,-1,0,0,2,2}}
  {{-3,-1,0,0,1,3}}   {{-3,-1,-1,1,2,2}}   {{-3,-1,-1,1,1,3}}
  {{-3,-1,-1,0,2,3}}  {{-3,-2,1,1,1,2}}*   {{-3,-2,0,1,2,2}}
  {{-3,-2,0,1,1,3}}   {{-3,-2,0,0,2,3}}    {{-3,-2,-1,2,2,2}}*
  {{-3,-2,-1,1,2,3}}.
  Therefore, a(6) = 43.
The ones marked with an asterisk are the ones that need reverse splitting
to be reached. They are not produced using the rules of A347913.

Cf. A000571, A347913.

def nextq(q):
    used, used2 = set(), set()
    for i in range(len(q)-1):
        for j in range(i+1, len(q)):
            if q[i] == q[j]:
                if q[i] in used: continue
                used.add(q[i])
                qc = list(q); qc[i] -= 1; qc[j] += 1
                yield tuple(sorted(qc))
            elif q[j] - q[i] == 2:  # assumes q is sorted
                if q[i] in used2: continue
                used2.add(q[i])
                qc = list(q); qc[i] += 1; qc[j] -= 1
                yield tuple(sorted(qc))
def a(n):
    s = tuple(0 for i in range(n)); reach = {s}; expand = list(reach)
    while len(expand) > 0:
        q = expand.pop()
        for qq in nextq(q):
            if qq not in reach:
                reach.add(qq)
                expand.append(qq)
    return len(reach)
print([a(n) for n in range(13)]) # Michael S. Branicky, Oct 21 2021

It appears that a(n) = A000571(n) for odd n.

a(6)-a(19) from Michael S. Branicky, Oct 21 2021

A351869 a(n) is the number of self-complementary score sequences that are possible for strong tournaments on n vertices.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 3, 9, 11, 30, 39, 103, 141, 363, 514, 1301, 1894, 4727, 7036, 17358, 26311, 64282, 98936, 239712, 373806, 899115, 1418130, 3389078, 5399133, 12828749, 20619565, 48739465, 78963217, 185769110, 303128971, 710067027, 1166206802, 2720959217, 4495461790

Offset: 0

Paul K. Stockmeyer, Feb 22 2022

nonn

See A000571 for the definition of a tournament and its score sequence. A tournament is strong if every two vertices are mutually reachable by directed paths. Alternatively, a tournament is strong if it contains a directed Hamiltonian cycle.

A sequence (s_1 <= s_2 <= ... <= s_n) of integers is the score sequence of a strong tournament iff Sum_{i=1..r} s_i > binomial(r,2) for 1 <= r < n and Sum_{i=1..n} s_i = binomial(n,2). It is self-complementary iff s_{n+1-i} = n-1-s_i for 1 <= i <= n/2.

			The 9 self-complementary strong score sequences of length seven are
  (1,1,2,3,4,5,5),
  (1,1,3,3,3,5,5),
  (1,2,2,3,4,4,5),
  (1,2,3,3,3,4,5),
  (1,3,3,3,3,3,5),
  (2,2,2,3,4,4,4),
  (2,2,3,3,3,4,4),
  (2,3,3,3,3,3,4),
  (3,3,3,3,3,3,3).

Paul K. Stockmeyer, Table of n, a(n) for n = 0..501
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, arXiv:2202.05238 [math.CO], 2022.
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, J. Integer Seq. 26 (2023), Article 23.5.2.

Cf. A000571, A351822, A345470.

For n >= 1, a(2*n) = Sum_{T=binomial(n,2)+1..n*(n-1)} Sum_{E=floor(n/2)..n-1} g_n(T,E) and a(2*n+1) = Sum_{T=binomial(n,2)+1..n^2} Sum_{E=floor(n/2)..n} g_n(T,E), where g_1(T, E)=[T=E], and for n>=2, g_n(T, E)=0 if T-E <= binomial(n-1, 2) and g_n(T, E) = Sum_{k=0..E} g_{n-1}(T-E, k) otherwise.

cp's OEIS Frontend

A274098 Number of ways the most probable score sequence happens in an n-person round-robin tournament.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A345470 Number of self-complementary score sequences that are possible in an n-team round-robin tournament.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A351822 a(n) is the number of different score sequences that are possible for strong tournaments on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A047733 Number of score sequences in tournament with n players, when 6 points are awarded in each game.

Views

Author

Keywords

Links

Crossrefs

Formula

A047734 Number of score sequences in tournament with n players, when 7 points are awarded in each game.

Views

Author

Keywords

Links

Crossrefs

Formula

A047735 Number of score sequences in tournament with n players, when 8 points are awarded in each game.

Views

Author

Keywords

Links

Crossrefs

Formula

A047736 Number of score sequences in tournament with n players, when 9 points are awarded in each game.

Views

Author

Keywords

Links

Crossrefs

Formula

A047737 Number of score sequences in tournament with n players, when 10 points are awarded in each game.

Views

Author

Keywords

Links

Crossrefs

Formula

A348532 a(n) is the number of multisets of integers that are possible to reach by starting with n occurrences of 0 and by splitting and reverse splitting.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

Extensions

A351869 a(n) is the number of self-complementary score sequences that are possible for strong tournaments on n vertices.

Views

Author

Keywords

Comments