3,2

Wkipedia, Pseudoforest.

a(n) = A133686(n) - A001858(n).

a(6)=5592 because we have several cases of one unicyclic graph or two. Namely,

-One triangle and a forest of order 3. The unique triangle can be relabeled in C(6,3)=20 ways, we have 20*7= 140 graphs.

-One unicyclic graph with 4 nodes and a forest of order 2. The 15 distinct unicyclic graphs of 4 nodes can be relabeled in C(6,4) ways, so we have 2*15C(6,2), or 450 graphs.

-One unicyclic graph with 5 nodes and an isolated vertex. There are 222 different graphs that can be relabeled in C(6,5) ways, so 6 * 222 = 1332 graphs.

-One unicyclic graph with 6 nodes, so 3660 graphs.

-Two triangles. The triangles can be relabeled in C(6,3)/2 ways. So 10 graphs.

The total of all cases is 5592.

cy:= proc(n) option remember; local t; binomial(n-1, 2) *add ((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n, k) option remember; local j; if k=0 then 1 elif k<0 or n<k then 0 else add (binomial (n-1, j) *((j+1)^(j-1) *T(n-j-1, k-j) +cy(j+1) *T(n-j-1, k-j-1)), j=0..k) fi end: a1:= n-> add (T(n, k), k=0..n): a2:= proc(n) option remember; if n=0 then 1 else add (binomial (n-1, j) *(j+1)^(j-1) *a2(n-1-j), j=0..n-1) fi end: a:= n-> a1(n)-a2(n): seq (a(n), n=3..25); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 15 2008]

Cf. A140144, A001858, A057500.

Sequence in context: A138943 A111420 A166965 this_sequence A027541 A143699 A015676

Adjacent sequences: A137349 A137350 A137351 this_sequence A137353 A137354 A137355

nonn

Washington Bomfim (webonfim(AT)bol.com.br), May 17 2008

Corrected and extended by Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 15 2008