|
|
A134964
|
|
Number of unlabeled n-node simple graphs with at most one cycle in each connected component.
|
|
33
|
|
|
1, 1, 2, 4, 9, 19, 46, 108, 273, 696, 1836, 4896, 13323, 36541, 101323, 282693, 793697, 2237982, 6335978, 17992622, 51235887, 146228734, 418181860, 1197972026, 3437159492, 9875198568, 28407202891, 81807809714, 235831978115, 680478488927, 1965160731704
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
a(0) = 1, for n >= 1, a(n) = Sum_{1*j_1 + 2*j_2 + ··· = n} ( Product_{i = 1..n} binomial(A005703(i+1) + j_i -1, j_i) ) [(4.27) of [F. Ruskey] with n replaced by n+1, and a_i replaced by A005703(i+1)].
|
|
MATHEMATICA
|
Needs["Combinatorica`"];
nn=30; s[n_, k_]:=s[n, k]=a[n+1-k]+If[n<2k, 0, s[n-k, k]]; a[1]=1; a[n_]:=a[n]=Sum[a[i]s[n-1, i]i, {i, 1, n-1}]/(n-1); rt=Table[a[i], {i, 1, nn}]; cu=Drop[Apply[Plus, Table[Take[CoefficientList[CycleIndex[DihedralGroup[n], s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], nn], {n, 3, nn}]], 1]; t[n_, k_]:=t[n, k]=b[n+1-k]+If[n<2k, 0, t[n-k, k]]; b[1]=1; b[n_]:=b[n]=Sum[b[i]t[n-1, i]i, {i, 1, n-1}]/(n-1); ft=Table[b[i]-Sum[b[j]b[i-j], {j, 1, i/2}]+If[OddQ[i], 0, b[i/2](b[i/2]+1)/2], {i, 1, nn}];
|
|
CROSSREFS
|
Cf. A005703 (number of pseudotrees), A137917 (number of maximal pseudoforests).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|