cp's OEIS Frontend

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

%I A351822 #42 Dec 25 2024 04:05:49
%S A351822 1,1,0,1,1,3,7,21,61,184,573,1835,5969,19715,66054,223971,767174,
%T A351822 2651771,9240766,32436016,114596715,407263306,1455145050,5224710466,
%U A351822 18843677124,68243466611,248090964092,905092211818,3312816854525,12162610429661,44780896121875,165316324574671,611819769698967
%N A351822 a(n) is the number of different score sequences that are possible for strong tournaments on n vertices.
%C A351822 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.
%C A351822 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).
%H A351822 Paul K. Stockmeyer, <a href="/A351822/b351822.txt">Table of n, a(n) for n = 0..500</a>
%H A351822 Paul K. Stockmeyer, <a href="http://arxiv.org/abs/2202.05238">Counting Various Classes of Tournament Score Sequences</a>, arXiv:2202.05238 [math.CO], 2022.
%H A351822 Paul K. Stockmeyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Stockmeyer/stock14.html">Counting Various Classes of Tournament Score Sequences</a>, J. Integer Seq. 26 (2023), Article 23.5.2.
%F A351822 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.
%F A351822 a(n) ~ c * 4^n / n^(5/2), where c = 0.202756471582408229... - _Vaclav Kotesovec_, Feb 21 2022
%e A351822 The seven strong score sequences of length six are
%e A351822   (1,1,2,3,4,4),
%e A351822   (1,1,3,3,3,4),
%e A351822   (1,2,2,2,4,4),
%e A351822   (1,2,2,3,3,4),
%e A351822   (1,2,3,3,3,3),
%e A351822   (2,2,2,2,3,4),
%e A351822   (2,2,2,3,3,3).
%Y A351822 Cf. A000571.
%K A351822 nonn
%O A351822 0,6
%A A351822 _Paul K. Stockmeyer_, Feb 20 2022