cp's OEIS Frontend

A141782 Number of connected graphs with one cycle of length m = n-4 and n nodes.

%I A141782 #10 Feb 18 2013 11:30:41
%S A141782 18,28,32,45,52,69,79,100,114,140,158,189,212,249,277,320,354,404,444,
%T A141782 501,548,613,667,740,802,884,954,1045,1124,1225,1313,1424,1522,1644,
%U A141782 1752,1885,2004,2149,2279,2436,2578,2748,2902,3085,3252
%N A141782 Number of connected graphs with one cycle of length m = n-4 and n nodes.
%C A141782 We have unicyclic graphs of order n = m+4 with a cycle of length m. Only 4 nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1,2,3,4, or 5. The set of graphs can be divided in five subsets S_1, S_2, S_3, S_4 and S_5, such that
%C A141782 S_1 has trees of orders [5,1,1,...,1],
%C A141782 S_2 has trees of orders [4,2,1,...,1],
%C A141782 S_3 has trees of orders [3,3,1,...,1],
%C A141782 S_4 has trees of orders [3,2,2,1,...,1] and
%C A141782 S_5 has trees of orders [2,2,2,2,1,...,1].
%C A141782 |S_1| = 9 since there are 9 rooted trees with 5 points.
%C A141782 |S_2| = 4floor(m/2).
%C A141782 |S_3| = 3floor(m/2). We consider the 3 2-combinations (with repetition) of the 2 distinct rooted trees of order 3.
%C A141782 |S_4| = 2floor((m-1)^2/4) since floor((m-1)^2/4) is the number of bracelets with m beads, 2 of which are red, 1 of which is blue.
%C A141782 With x=m-4, |S_5| = <(x^3 +9x^2 +(32-9(x mod 2))x)/48 +0.6>. The value of |S_5| is equal to the number of m-bead bracelets with 4 red beads.
%C A141782 This sequence is the fifth column of table T of A058879.
%H A141782 Washington Bomfim, <a href="/A141782/b141782.txt">Table of n, a(n) for n = 7..100</a>
%H A141782 Washington Bomfim, <a href="http://commons.wikimedia.org/wiki/Image:FiguraA141782.PNG">The 32 unicyclic graphs of order 9 with a pentagon.</a>.
%F A141782 With m = n-4 and x = m-4, a(n) = <(x^3 +9x^2 +(32-9(x mod 2))x)/48 +0.6> + 2floor((m-1)^2/4) + 7floor(m/2) + 9. Empirically for n odd a(n) = (n^3 +9n^2 -n +87)/48 Empirically for n even a(n) = (n^3 +9n^2 +8n +192-n%4*6)/48.
%F A141782 Empirical g.f.: -x^7*(16*x^7-23*x^6-9*x^5+18*x^4-17*x^3+24*x^2+8*x-18) / ((x-1)^4*(x+1)^2*(x^2+1)). [_Colin Barker_, Feb 18 2013]
%e A141782 E.g. a(9)=32. Click the link to see an illustration of the 32 unicyclic graphs of order 9 with a pentagon.
%o A141782 (PARI) m=n-4 x=m-4 a(n) = round((x^3+9*x^2+(32-9*(x%2))*x)/48+0.6)+2*floor((m-1)^2/4)+7*floor(m/2)+9
%Y A141782 Cf. A058879, A005232, A000081, A002620.
%K A141782 nonn
%O A141782 7,1
%A A141782 _Washington Bomfim_, Jul 31 2008