A138237 Number of unlabeled graphs with at least one cycle in which every connected component has at most one cycle.

1, 3, 9, 26, 71, 197, 543, 1507, 4186, 11722, 32883, 92724, 262179, 743792, 2115019, 6028779, 17217093, 49258009, 141142096, 404997704, 1163569094, 3346830818, 9636723582, 27774427243, 80121104084, 231317022483, 668346261557

Offset

3,2

Links

Table of n, a(n) for n=3..29.

Wikipedia, Pseudoforest.

Formula

a(n) = A134964(n) - A005195(n).

Example

a(9)=543 since we have several cases, with one unicyclic graph, or two, or three. Namely,
-One triangle and a forest of order 6, or 20 graphs.
-One unicyclic graph with 4 nodes and a forest of order 5, or 20 graphs.
-One unicyclic graph with 5 nodes and a forest of order 4, or 30 graphs.
-One unicyclic graph with 6 nodes and a forest of order 3, or 39 graphs.
-One unicyclic graph of 7 nodes and a forest of order 2, or 66 graphs.
-One unicyclic graph of 8 nodes and an isolated vertex, or 89 graphs.
-One unicyclic graph of 9 nodes, or 240 graphs.
-Two triangles and a forest of order 3, or 3 graphs.
-One triangle plus one unicyclic graph of 4 nodes plus a forest of order 2, or 4 graphs.
-One triangle plus one unicyclic graph of 5 nodes plus an isolated vertex, or 5 graphs.
-One triangle plus one unicyclic graph of 6 nodes, or 13 graphs.
-Two unicyclic graphs of 4 nodes and an isolated vertex, or C(2+2-1,2)=3 graphs.
-One unicyclic graph of 5 nodes and another of 4 nodes, or 10 graphs.
-Three triangles, or 1 graph.
Total = 543.

Crossrefs

Cf. A001429, A005195, A140145.

Sequence in context: A221946 A291410 A048470 * A121286 A072863 A054963

Adjacent sequences: A138234 A138235 A138236 * A138238 A138239 A138240

Keyword

nonn

Author

Washington Bomfim, May 17 2008

Status

approved