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.

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

Table of n, a(n) for n=0..44.

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

Crossrefs

Cf. A002866, A006125, A052670, A095340, A103904.

Cf. A122027, A224886, A259105, A350608, A350609, A350610.

Sequence in context: A229296 A232565 A058942 * A196759 A303165 A188813

Adjacent sequences: A365635 A365636 A365637 * A365639 A365640 A365641

Keyword

nonn,easy,tabl

Author

Thomas Scheuerle, Sep 14 2023

Status

approved