2022/09/08 by Claesson, Anders, Dukes, Mark, Franklín, Atli Fannar +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2209.03925
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.