

A350608


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


3



1, 1, 4, 31, 474, 14357, 865024, 103931595, 24935913222, 11956100981537, 11460773522931212, 21967828926423843319, 84207961512578582993810, 645554571594493917538073933, 9897742810470352880099047702936, 303505765229448690912596327628571427
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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


REFERENCES

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


LINKS

Table of n, a(n) for n=1..16.
R. L. Graham, D. E. Knuth, and T. S. Motzkin, Complements and transitive closures, Discrete Mathematics 2 (1972), 1729.
Don Knuth, Weak Components Revived, January 2022.
Don Knuth, PreFascicle 12A of TAOCP, Volume 4, January 2022.


EXAMPLE

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.


CROSSREFS

Cf. A350609, A350610.
Sequence in context: A195195 A141827 A262529 * A143077 A203011 A228467
Adjacent sequences: A350605 A350606 A350607 * A350609 A350610 A350611


KEYWORD

nonn


AUTHOR

Don Knuth, Jan 16 2022


STATUS

approved



