A350609 -id:A350609 - cp's OEIS frontend

A350608 Number of weakly connected subgraphs of the transitive tournament on {1,...,n}.

1, 1, 4, 31, 474, 14357, 865024, 103931595, 24935913222, 11956100981537, 11460773522931212, 21967828926423843319, 84207961512578582993810, 645554571594493917538073933, 9897742810470352880099047702936, 303505765229448690912596327628571427

Offset: 1

Don Knuth, Jan 16 2022

nonn

The transitive tournament on n labeled nodes 1, ..., n has n*(n-1)/2 arcs, namely i->j for 1 <= i < j <= n.

			a(4)=31: the 31 weakly connected subgraphs when n=4 are the 1+6+15 digraphs that have only 0 or 1 or 2 arcs, plus the four digraphs with three arcs that leave one vertex untouched, plus the five digraphs with three arcs that make an N:
  1->3,1->4,2->3;
  1->3,1->4,2->4;
  1->3,2->3,2->4;
  1->4,2->3,2->4;
  1->2,1->4,3->4.

Jean Francois Pacault, "Computing the weak components of a
directed graph," SIAM Journal on Computing 3 (1974), 56-61.

R. L. Graham, D. E. Knuth, and T. S. Motzkin, Complements and transitive closures, Discrete Mathematics 2 (1972), 17--29.
Don Knuth, Weak Components Revived, January 2022.
Don Knuth, Pre-Fascicle 12A of TAOCP, Volume 4, January 2022.

Cf. A350609, A350610.

A350610 Irregular triangle read by rows: T(n,k) (n >= 1, 0 <= k <= (n-1)*(n-2)/2) = number of weakly connected subdigraphs of the transitive tournament on n nodes that have k arcs.

Original entry on oeis.org

1, 1, 1, 3, 1, 6, 15, 9, 1, 10, 45, 120, 162, 109, 27, 1, 15, 105, 455, 1365, 2755, 3738, 3353, 1889, 600, 81, 1, 21, 210, 1330, 5985, 20349, 52764, 104726, 159351, 185155, 162455, 105436, 48881, 15255, 2862, 243, 1, 28, 378, 3276, 20475, 98280, 376740, 1173564, 2995480, 6295857, 10925190, 15658609, 18498220, 17926289, 14138445, 8968823, 4498534, 1740117, 499834, 100225, 12501, 729

Offset: 1

Don Knuth, Jan 16 2022

The sum of row n is A350608(n).

For references and links see A350608.

			For example, when n=4, the 31 weakly connected graphs have respectively 1, 6, 15, 9 cases with 0, 1, 2, and 3 arcs (as in the example given for A350608).
Triangle T(n,k) begins:
  1;
  1;
  1,  3;
  1,  6,  15,   9;
  1, 10,  45, 120,  162,  109,   27;
  1, 15, 105, 455, 1365, 2755, 3738, 3353, 1889, 600, 81;
  ...

Don Knuth, Rows n = 1..16, flattened
Don Knuth, The first 16 rows.

Cf. A350608, A350609.

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

Thomas Scheuerle, Sep 14 2023

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.

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

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

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

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

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

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

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

cp's OEIS Frontend

A350608 Number of weakly connected subgraphs of the transitive tournament on {1,...,n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A350610 Irregular triangle read by rows: T(n,k) (n >= 1, 0 <= k <= (n-1)*(n-2)/2) = number of weakly connected subdigraphs of the transitive tournament on n nodes that have k arcs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula