|
%I #15 Jan 30 2016 16:20:11
%S 1,19,317,5592,108839,2356175,56590729,1499304898,43532688017,
%T 1376491137807,47122376352941,1737338689842008,68657874376063231,
%U 2896049933653455241,129892644397271578571,6173717934189145195530,309998781844881257871161,16399060640250318161199785
%N Number of labeled graphs with at least one cycle in which every connected component has at most one cycle.
%H Alois P. Heinz, <a href="/A137352/b137352.txt">Table of n, a(n) for n = 3..150</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>.
%F a(n) = A133686(n) - A001858(n).
%e a(6)=5592 because we have several cases of one unicyclic graph or two. Namely,
%e -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.
%e -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.
%e -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.
%e -One unicyclic graph with 6 nodes, so 3660 graphs.
%e -Two triangles. The triangles can be relabeled in C(6,3)/2 ways. So 10 graphs.
%e The total of all cases is 5592.
%p 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
%t 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 *)
%Y Cf. A140144, A001858, A057500.
%K nonn
%O 3,2
%A _Washington Bomfim_, May 17 2008
%E Corrected and extended by _Alois P. Heinz_, Sep 15 2008
|
