login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000226 Number of n-node unlabeled connected graphs with one cycle of length 3.
(Formerly M2668 N1066)
9
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,3

COMMENTS

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)

REFERENCES

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).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 3..1000 (first 198 terms from Vincenzo Librandi)

Sergei Abramovich, 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

FORMULA

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

MAPLE

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

MATHEMATICA

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 *)

PROG

(PARI) 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

CROSSREFS

Column 3 of A033185 and A217781.

Cf. A000081, A001429.

For n >= 3 a(n) = A217781(n, 3) = A058879(n, n-2) = A033185(n, 3).

Sequence in context: A027967 A181306 A178035 * A291734 A291229 A036883

Adjacent sequences:  A000223 A000224 A000225 * A000227 A000228 A000229

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Apr 19 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 26 08:43 EST 2021. Contains 341631 sequences. (Running on oeis4.)