A058879 -id:A058879 - cp's OEIS frontend

A000226 Number of n-node unlabeled connected graphs with one cycle of length 3.

1, 1, 3, 7, 18, 44, 117, 299, 793, 2095, 5607, 15047, 40708, 110499, 301541, 825784, 2270211, 6260800, 17319689, 48042494, 133606943, 372430476, 1040426154, 2912415527, 8167992598, 22947778342, 64577555147, 182009003773, 513729375064, 1452007713130

Offset: 3

N. J. A. Sloane

Number of rooted trees on n+1 nodes where root has degree 3. - Christian G. Bower
Third column of A033185. - Michael Somos, Aug 20 2018
From Washington Bomfim, Dec 22 2020: (Start)
Number of forests of 3 rooted trees with a total of n nodes.
Number of unicyclic graphs with a cycle of length 3 and a total of n nodes.
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 3..1000 (first 198 terms from Vincenzo Librandi)
Sergei Abramovich, Partitions of integers, Ferrers-Young diagrams, and representational efficacy of spreadsheet modeling, Spreadsheets in Education (eJSiE): Vol. 5: Iss. 2, Article 1, p. 5
Washington Bomfim, Illustration of initial terms
F. Ruskey, Combinatorial Generation, Eq.(4.27), 2003
Eric Weisstein's World of Mathematics, Rooted Tree
Index entries for sequences related to rooted trees

Column 3 of A033185 and A217781.
Cf. A000081, A001429.
For n >= 3 a(n) = A217781(n, 3) = A058879(n, n-2) = A033185(n, 3).

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; unapply(add(b(k)*x^k, k=1..n),x) end: a:= n-> coeff(series((B(n-2)(x)^3+ 3*B(n-2)(x)* B(n-2)(x^2)+ 2*B(n-2)(x^3))/6, x=0, n+1), x,n): seq(a(n), n=3..40); # Alois P. Heinz, Aug 21 2008

terms = 30; r[] = 0; Do[r[x] = x *Exp[Sum[r[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms+3}]; A[x_] = (r[x]^3 + 3*r[x]*r[x^2] + 2*r[x^3])/6 + O[x]^(terms+3); Drop[CoefficientList[A[x], x], 3] (* Jean-François Alcover, Nov 23 2011, updated Jan 11 2018 *)

seq(max_n) = {my(a = f = vector(max_n), s, D); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n=3,max_n,s=0;forpart(P=n,D=Set(P);if(#D==3,s+=f[P[1]]*f[P[2]]*f[P[3]];next());
if(#D==1, s+= binomial(f[P[1]]+2, 3); next());
if(P[1] == P[2], s += binomial(f[P[1]]+1, 2) * f[P[3]],
s += binomial(f[P[2]]+1, 2) * f[P[1]]),[1,n],[3,3]); a[n] = s ); a[3..max_n] }; \\ Washington Bomfim, Dec 22 2020

G.f.: (r(x)^3+3*r(x)*r(x^2)+2*r(x^3))/6 where r(x) is g.f. for rooted trees (A000081).
a(n) = Sum_{j1+2j2+···= n} (Product_{i=1..n} binomial(A000081(i) + j_i -1, j_i)) [(4.27) of [F. Ruskey] with n replaced by n+1]. - Washington Bomfim, Dec 22 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 19 2000

A000368 Number of connected graphs with one cycle of length 4.

Original entry on oeis.org

1, 1, 4, 9, 28, 71, 202, 542, 1507, 4114, 11381, 31349, 86845, 240567, 668553, 1860361, 5188767, 14495502, 40572216, 113743293, 319405695, 898288484, 2530058013, 7135848125, 20152898513, 56986883801

Offset: 4

N. J. A. Sloane

nonn

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, page 69.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 4..2000 (terms 4..43 from Sean A. Irvine, 44..200 from Washington Bomfim)
Washington Bomfim, Illustration of initial terms

Column k=4 of A217781.
Cf. A000081, A000226, A001429, A005703.
Second diagonal of A058879.

Needs["Combinatorica`"]; nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 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}]; Take[CoefficientList[CycleIndex[DihedralGroup[4], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {5, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
A000081 = Rest[Cases[ Import["https://oeis.org/A000081/b000081.txt", "Table"], {, }][[All, 2]]]; max = 30; g81 = Sum[A000081[[k]]*x^k, {k, 1, max}]; g81x2 = Sum[A000081[[k]]*x^(2 k), {k, 1, max}]; g81x4 = Sum[A000081[[k]]*x^(4 k), {k, 1, max}]; Drop[CoefficientList[ Series[(2*g81x4 + 3*g81x2^2 + 2*g81^2*g81x2 + g81^4)/8, {x, 0, max}], x], 4] (* Vaclav Kotesovec, Dec 25 2020 *)

g(Q)={my(V=Vec(Q),D=Set(V),d=#D); if(d==4,return(3*f[D[1]]*f[D[2]]*f[D[3]]*f[D[4]]));
if(d==1, return((f[D[1]]^4+2*f[D[1]]^3+3*f[D[1]]^2+2*f[D[1]])/8));
my(k=1, m = #select(x->x == D[k],V), t); while(m==1, k++; m = #select(x->x == D[k], V)); t = D[1]; D[1] = D[k]; D[k] = t;
if(d == 3, return( f[D[1]] * f[D[2]] * f[D[3]] * (3 * f[D[1]] + 1)/2 ) );
if(m==3, return(f[D[1]]^2 * f[D[2]] * (f[D[1]] + 1)/2));
((3*f[D[2]]^2 + f[D[2]])*f[D[1]]^2 + (f[D[2]]^2 + 3*f[D[2]])*f[D[1]])/4 };
seq(max_n) = { my(s, a = vector(max_n), U); f = vector(max_n); f[1] = 1;
for(j=1, max_n - 1, if(j%100==0,print(j)); f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n=4, max_n, s=0; forpart(Q = n, if( (Q[4] > Q[3]) && (Q[3]-1 > Q[2]),
      U = U / (f[Q[4] + 1] * f[Q[3] - 1]) * f[Q[4]] * f[Q[3]],  U = g(Q)); s += U,
[1,n],[4,4]); a[n] = s; if(n % 100 == 0, print(n": " s))); a[4..max_n] };
\\ Washington Bomfim, Jul 19 2012 and Dec 22 2020

From Washington Bomfim, Jul 19 2012 and Dec 22 2020: (Start)
a(n) = Sum_{P}( g(Q) ), where P is the set of the partitions Q of n with 4 parts, Q with distinct parts D[1]..D[d], D[1] the part of maximum multiplicity m in Q, f(n) = A000081(n), and g(Q) given by,
       | 3 * f(D[1]) * f(D[2]) * f(D[3]) * f(D[4]),              if d = 4,
       | (f(D[1])^4 + 2*f(D[1])^3 + 3*f(D[1])^2 + 2*f(D[1]))/8,  if d = 1,
g(Q) = | f(D[1]) * f(D[2]) * f(D[3]) * (3 * f(D[1]) + 1)/2,      if d = 3,
       | ((3*f(D[2])^2+f(D[2]))*f(D[1])^2+(f(D[2])^2+3*f(D[2]))*f(D[1]))/4,
       |                                                   if d=2, and m=2,
       | f(D[1])^2 * f(D[2]) * (f(D[1]) + 1)/2,            if d=2, and m=3.
(End)
G.f.: (2*t(x^4) + 3*t(x^2)^2 + 2*t(x)^2*t(x^2) + t(x)^4)/8 where t(x) is the g.f. of A000081. - Andrew Howroyd, Dec 03 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 20 2000
Definition improved by Franklin T. Adams-Watters, May 16 2006
More terms from Sean A. Irvine, Nov 14 2010

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

Original entry on oeis.org

18, 28, 32, 45, 52, 69, 79, 100, 114, 140, 158, 189, 212, 249, 277, 320, 354, 404, 444, 501, 548, 613, 667, 740, 802, 884, 954, 1045, 1124, 1225, 1313, 1424, 1522, 1644, 1752, 1885, 2004, 2149, 2279, 2436, 2578, 2748, 2902, 3085, 3252

Offset: 7

Washington Bomfim, Jul 31 2008

nonn

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
S_1 has trees of orders [5,1,1,...,1],
S_2 has trees of orders [4,2,1,...,1],
S_3 has trees of orders [3,3,1,...,1],
S_4 has trees of orders [3,2,2,1,...,1] and
S_5 has trees of orders [2,2,2,2,1,...,1].
|S_1| = 9 since there are 9 rooted trees with 5 points.
|S_2| = 4floor(m/2).
|S_3| = 3floor(m/2). We consider the 3 2-combinations (with repetition) of the 2 distinct rooted trees of order 3.
|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.
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.
This sequence is the fifth column of table T of A058879.

			E.g. a(9)=32. Click the link to see an illustration of the 32 unicyclic graphs of order 9 with a pentagon.

Washington Bomfim, Table of n, a(n) for n = 7..100
Washington Bomfim, The 32 unicyclic graphs of order 9 with a pentagon..

Cf. A058879, A005232, A000081, A002620.

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

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.

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]

cp's OEIS Frontend

A000226 Number of n-node unlabeled connected graphs with one cycle of length 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000368 Number of connected graphs with one cycle of length 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula