OFFSET
1,3
COMMENTS
The transitive tournament on n labeled nodes 1, ..., n has n*(n-1)/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), 56-61.
LINKS
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.
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
KEYWORD
nonn
AUTHOR
Don Knuth, Jan 16 2022
STATUS
approved