login
A365638
Triangular array read by rows: T(n, k) is the number of ways that a k-element transitive tournament can occur as a subtournament of a larger tournament on n labeled vertices.
0
1, 1, 1, 2, 4, 2, 8, 24, 24, 6, 64, 256, 384, 192, 24, 1024, 5120, 10240, 7680, 1920, 120, 32768, 196608, 491520, 491520, 184320, 23040, 720, 2097152, 14680064, 44040192, 55050240, 27525120, 5160960, 322560, 5040, 268435456, 2147483648, 7516192768, 11274289152, 7046430720, 1761607680, 165150720, 5160960, 40320
OFFSET
0,4
COMMENTS
A tournament is a directed digraph obtained by assigning a direction for each edge in an undirected complete graph. In a transitive tournament all nodes can be strictly ordered by their reachability.
LINKS
Paul Erdős, On a problem in graph theory, The Mathematical Gazette, 47: 220-223 (1963).
FORMULA
T(n, k) = binomial(n, k)*k!*2^(binomial(n, 2) - binomial(k, 2)).
T(n, 0) = A006125(n).
T(n, 1) = A095340(n).
T(n, 2) = A103904(n).
T(n, n) = n!.
T(n, n-1) = A002866(n-1).
T(n, n-2) = A052670(n).
EXAMPLE
Triangle begins:
1
1, 1
2, 4, 2
8, 24, 24, 6
64, 256, 384, 192, 24
1024, 5120, 10240, 7680, 1920, 120
MAPLE
T := (n, k) -> 2^(((n-1)*n - (k-1)*k)/2) * n! / (n-k)!:
seq(seq(T(n, k), k = 0..n), n = 0..8); # Peter Luschny, Nov 02 2023
PROG
(PARI) T(n, k) = binomial(n, k)*k!*2^(binomial(n, 2) - binomial(k, 2))
KEYWORD
nonn,easy,tabl
AUTHOR
Thomas Scheuerle, Sep 14 2023
STATUS
approved