Voozh

A351822

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

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

LINKS

Paul K. Stockmeyer, Table of n, a(n) for n = 0..500

Sophie Rehberg, Extensions of Ehrhart theory and applications to combinatorial structures, Ph D. dissertation, Freien Univ. (Berlin, Germany 2025). See p. 145.

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.

FORMULA

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

EXAMPLE

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

CROSSREFS

Cf. A000571.