A350608 -id:A350608 - cp's OEIS frontend

A350609 Triangle read by rows: T(n,k) (n >= 1, 1 <= k <= n) = number of subdigraphs of the transitive tournament on n nodes that have k weak components.

1, 1, 1, 4, 2, 2, 31, 15, 10, 8, 474, 228, 162, 96, 64, 14357, 7057, 5242, 3296, 1792, 1024, 865024, 438662, 342394, 222720, 130048, 65536, 32768, 103931595, 54542867, 44669602, 30110848, 18337792, 10027008, 4718592, 2097152, 24935913222, 13548525896, 11608243634, 8093078016, 5130403840, 2945449984, 1518338048, 671088640, 268435456

Offset: 1

Don Knuth, Jan 16 2022

The sum of row n is 2^(n*(n-1)/2) = A006125(n).

For references and links see A350608.

			For example, the entries for n=3 are {4,2,2}, because the empty subgraph and the subgraphs with a single arc have 1 weak component {123}; 1->2,1->3 and 1->3,2->3 have 2 weak components (namely {1,23} and {12,3}); finally 1->2,2->3 and 1->2,1->3,2->3 have 3 weak components (namely {1,2,3}).
Triangle T(n,k) begins:
       1;
       1,      1;
       4,      2,      2;
      31,     15,     10,      8;
     474,    228,    162,     96,     64;
   14357,   7057,   5242,   3296,   1792,  1024;
  865024, 438662, 342394, 222720, 130048, 65536, 32768;
  ...

Don Knuth, Rows n = 1..16, flattened

Column k=1 gives A350608.
Main diagonal gives A006125(n-1).
Cf. 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

A350609 Triangle read by rows: T(n,k) (n >= 1, 1 <= k <= n) = number of subdigraphs of the transitive tournament on n nodes that have k weak components.

Views

Author

Keywords

Comments

Examples

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