cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament.

Original entry on oeis.org

0, 1, 2, 4, 8, 14, 28
Offset: 0

Views

Author

Warren D. Smith, Sep 11 2006

Keywords

Comments

A Ramsey-like number but defined for tournaments (i.e., directed graphs in which each node-pair is joined by exactly one arc) rather than undirected graphs.
It is not hard to show that a(n) always exists and a(n) is nondecreasing.
The lower bounds a(4)>=8 and a(5)>=14 and a(6)>=28 arise from the cyclic tournaments with offsets 1,2,4 mod 7; the same is true of offsets 1,3,9,2,6,5 mod 13 and the "QRgraph" in GF(3^3) with 27 vertices.
The following lower bounds a(n)>=P+1 arise from QRgraph(P) where P is prime and P=3 (mod 4): a(8)>=48, a(9)>=84, a(10)>=108, a(12)>=200, a(13)>=272.
This is almost certainly different from the other sequences currently in the OEIS which begin 1,2,4,8,14,28.

References

  • K. B. Reid, Tournaments, in Handbook of Graph Theory; see p. 167.

Links

Crossrefs

Cf. A122027, A003141.

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.

Original entry on oeis.org

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

Views

Author

Thomas Scheuerle, Sep 14 2023

Keywords

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

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
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.