cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

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