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

Offset: 0

Author

Paul K. Stockmeyer, Feb 20 2022

Keywords

• nonn

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

Examples

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

Links

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

Crossrefs

Cf. A000571.

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