Counting tournament score sequences

Claesson, Anders; Dukes, Mark; Franklín, Atli; Stefánsson, Sigurður

doi:10.1090/proc/16425

Counting tournament score sequences
HTML articles powered by AMS MathViewer

by Anders Claesson, Mark Dukes, Atli Fannar Franklín and Sigurður Örn Stefánsson;

Proc. Amer. Math. Soc. 151 (2023), 3691-3704

DOI: https://doi.org/10.1090/proc/16425

Published electronically: May 5, 2023

HTML | PDF | Request permission

Abstract:

The score sequence of a tournament is the sequence of the out-degrees of its vertices arranged in nondecreasing order. The problem of counting score sequences of a tournament with $n$ vertices is more than 100 years old [Quart. J. Math. 49 (1920), pp. 1–36]. In 2013 Hanna conjectured a surprising and elegant recursion for these numbers. We settle this conjecture in the affirmative by showing that it is a corollary to our main theorem, which is a factorization of the generating function for score sequences with a distinguished index. We also derive a closed formula and a quadratic time algorithm for counting score sequences.

References

Max Alekseyev, https://oeis.org/A145855/a145855.txt, 2008.
Arthur Cayley, A theorem on trees, volume 13 of Cambridge Library Collection - Mathematics, Cambridge University Press, 2009, 26–28.
Shane Chern, An extension of a formula of Jovovic, Integers 19 (2019), Paper No. A47, 7. MR 4017188
P. Erdös, A. Ginzburg, and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel Sect. F 10F (1961), no. 1, 41–43. MR 3618568
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
Frank Harary and Leo Moser, The theory of round robin tournaments, Amer. Math. Monthly 73 (1966), 231–246. MR 197347, DOI 10.2307/2315334
OEIS Foundation Inc, The Online Encyclopedia of Integer Sequences, https://oeis.org, 2021.
Daniel J. Kleitman and Kenneth J. Winston, Forests and score vectors, Combinatorica 1 (1981), no. 1, 49–54. MR 602415, DOI 10.1007/BF02579176
H. G. Landau, On dominance relations and the structure of animal societies. III. The condition for a score structure, Bull. Math. Biophys. 15 (1953), 143–148. MR 54933, DOI 10.1007/bf02476378
P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Math. 49 (1920), 1–36, Reprinted in Percy Alexander MacMahon Collected Papers, Volume I, George E. Andrews, ed., MIT Press, 1978.
T. V. Narayana and D. H. Bent, Computation of the number of score sequences in round-robin tournaments, Canad. Math. Bull. 7 (1964), no. 1, 133–136.
John Riordan, The number of score sequences in tournaments, J. Combinatorial Theory 5 (1968), 87–89. MR 228385, DOI 10.1016/S0021-9800(68)80032-8
John Riordan, Erratum: “The number of score sequences in tournaments”, J. Combinatorial Theory 6 (1969), 226. MR 234845, DOI 10.1016/0020-7225(68)90031-1
Richard P. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math. 6 (1980), 333–342. MR 593545, DOI 10.1016/S0167-5060(08)70717-9
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
Paul K. Stockmeyer, Counting various classes of tournament score sequences, arXiv:2202.05238v1, 2022.