|
| |
|
|
A351822
|
|
a(n) is the number of different score sequences that are possible for strong tournaments on n vertices.
|
|
2
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
