Counting tournament score sequences

DOI10.1090/PROC/16425zbMATH Open1517.05078arXiv2209.03925OpenAlexW4318828914MaRDI QIDQ6106038FDOQ6106038

Authors: Anders Claesson, Mark Dukes, Atli Fannar Franklín, Sigurdur Örn Stefánsson 

Publication date: 27 June 2023

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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 (MacMahon 1920). 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.

Full work available at URL: https://arxiv.org/abs/2209.03925

Recommendations

• scientific article; zbMATH DE number 7732125
• Score sets in multitournaments. I. Mathematical results
• scientific article; zbMATH DE number 568801
• Asymptotic enumeration of tournaments with a given score sequence
• An algorithm to generate tournament score sequences

zbMATH Keywords

quadratic time algorithm for counting score sequences

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Decompositions of Rational Convex Polytopes
• Title not available (Why is that?)
• The Theory of Round Robin Tournaments
• Title not available (Why is that?)
• The On-Line Encyclopedia of Integer Sequences
• Forests and score vectors
• Computation of the Number of Score Sequences in Round-Robin Tournaments
• An extension of a formula of Jovovic
• The number of score sequences in tournaments
• Erratum

Cited In (17)

• Title not available (Why is that?)
• Computing tournament sequence numbers efficiently with matrix techniques
• Asymptotic enumeration of tournaments with a given score sequence
• Tournament scoring problem
• Title not available (Why is that?)
• Counting the number of round-robin tournament schedules
• On scores in tournaments
• The stochastic sandpile model on complete graphs
• Tournament Coding of Integer Sequences
• Construction of tournaments with a given score sequence
• Title not available (Why is that?)
• Permutations with few inversions
• A note on the lacking polynomial of the complete bipartite graph
• Counting tournament brackets
• An algorithm to generate tournament score sequences
• Tournament sequences and Meeussen sequences
• Calculating the frequency of tournament score sequences

This page was built for publication: Counting tournament score sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6106038)