|
|
A350608
|
|
Number of weakly connected subgraphs of the transitive tournament on {1,...,n}.
|
|
4
|
|
|
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*(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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|