|
| |
|
|
A137352
|
|
Number of labeled graphs with at least one cycle in which every connected component has at most one cycle.
|
|
3
|
|
|
|
1, 19, 317, 5592, 108839, 2356175, 56590729, 1499304898, 43532688017, 1376491137807, 47122376352941, 1737338689842008, 68657874376063231, 2896049933653455241, 129892644397271578571, 6173717934189145195530, 309998781844881257871161, 16399060640250318161199785
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
3,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
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.
|
|
|
MAPLE
|
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); # Alois P. Heinz, Sep 15 2008
|
|
|
MATHEMATICA
|
nn=20; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]!CoefficientList[Series[ Exp[Log[1/(1-t)]/2+t/2-3t^2/4]-Exp[t-t^2/2], {x, 0, nn}], x], 3] (* Geoffrey Critzer, Mar 23 2013 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
