A350608
Number of weakly connected subgraphs of the transitive tournament on {1,...,n}.
Original entry on oeis.org
1, 1, 4, 31, 474, 14357, 865024, 103931595, 24935913222, 11956100981537, 11460773522931212, 21967828926423843319, 84207961512578582993810, 645554571594493917538073933, 9897742810470352880099047702936, 303505765229448690912596327628571427
Offset: 1
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.
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.
Original entry on oeis.org
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
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;
...
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
Triangle begins:
1
1, 1
2, 4, 2
8, 24, 24, 6
64, 256, 384, 192, 24
1024, 5120, 10240, 7680, 1920, 120
-
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))
Showing 1-3 of 3 results.
Comments