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

Author

Thomas Scheuerle, Sep 14 2023

Keywords

• nonn
• easy
• tabl

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.

Examples

			Triangle begins:
     1
     1,     1
     2,     4,     2
     8,    24,    24,     6
    64,   256,   384,   192,    24
  1024,  5120, 10240,  7680,  1920,  120
		

Links

• Paul Erdős, On a problem in graph theory, The Mathematical Gazette, 47: 220-223 (1963).

Crossrefs

Cf. A002866, A006125, A052670, A095340, A103904, A008279, A117260, A379614 (row sums).

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

Programs

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

PARI

T(n, k) = binomial(n, k)*k!*2^(binomial(n, 2) - binomial(k, 2))

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

T(n, k) = A008279(n, k) * A117260(n, k). - Peter Luschny, Dec 31 2024