cp's OEIS Frontend

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

%I A350608 #26 Jan 17 2022 22:17:46
%S A350608 1,1,4,31,474,14357,865024,103931595,24935913222,11956100981537,
%T A350608 11460773522931212,21967828926423843319,84207961512578582993810,
%U A350608 645554571594493917538073933,9897742810470352880099047702936,303505765229448690912596327628571427
%N A350608 Number of weakly connected subgraphs of the transitive tournament on {1,...,n}.
%C A350608 The transitive tournament on n labeled nodes 1, ..., n has n*(n-1)/2 arcs, namely i->j for 1 <= i < j <= n.
%D A350608 Jean Francois Pacault, "Computing the weak components of a
%D A350608 directed graph," SIAM Journal on Computing 3 (1974), 56-61.
%H A350608 R. L. Graham, D. E. Knuth, and T. S. Motzkin, <a href="https://mathweb.ucsd.edu/~fan/ron/papers/72_08_complements.pdf">Complements and transitive closures</a>, Discrete Mathematics 2 (1972), 17--29.
%H A350608 Don Knuth, <a href="/A350608/a350608.txt">Weak Components Revived</a>, January 2022.
%H A350608 Don Knuth, <a href="https://cs.stanford.edu/~knuth/fasc12a+.pdf">Pre-Fascicle 12A of TAOCP, Volume 4</a>, January 2022.
%e A350608 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:
%e A350608   1->3,1->4,2->3;
%e A350608   1->3,1->4,2->4;
%e A350608   1->3,2->3,2->4;
%e A350608   1->4,2->3,2->4;
%e A350608   1->2,1->4,3->4.
%Y A350608 Cf. A350609, A350610.
%K A350608 nonn
%O A350608 1,3
%A A350608 _Don Knuth_, Jan 16 2022