login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001429 Number of n-node connected unicyclic graphs.
(Formerly M1438 N0568)
23
1, 2, 5, 13, 33, 89, 240, 657, 1806, 5026, 13999, 39260, 110381, 311465, 880840, 2497405, 7093751, 20187313, 57537552, 164235501, 469406091, 1343268050, 3848223585, 11035981711, 31679671920, 91021354454, 261741776369, 753265624291, 2169441973139, 6252511838796 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

REFERENCES

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

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

Andrew Howroyd, Table of n, a(n) for n = 3..500

Washington G. Bomfim, A picture of the twenty one unicycles with 3,4,5 and 6 vertices

Audace A. V. Dossou-Olory, Graphs and unicyclic graphs with extremal connected subgraphs, arXiv:1812.02422 [math.CO], 2018.

R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.

R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]

S. Karim, J. Sawada, Z. Alamgirz and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.

Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.

Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Derivation of algorithm and Maple implementation using PET.)

Marko Riedel, Maple implementation using PET.

M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points, Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967. doi: 10.2172/4180737.

Eric Weisstein's World of Mathematics, Unicyclic Graph

FORMULA

a(n) = A068051(n) - A027852(n) - A000081(n).

MATHEMATICA

Needs["Combinatorica`"];

nn=30; s[n_, k_]:=s[n, k]=a[n+1-k]+If[n<2k, 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}]; Apply[Plus, Table[Take[CoefficientList[CycleIndex[DihedralGroup[n], s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], nn], {n, 3, nn}]]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)

(* Second program: *)

TreeGf[nn_] := Module[{A}, A = Table[1, {nn}]; For[n = 1, n <= nn 1, n++, A[[n + 1]] = 1/n * Sum[Sum[ d*A[[d]], {d, Divisors[k]}]*A[[n - k + 1]], {k, 1, n}]]; x A.x^Range[0, nn-1]];

seq[n_] := Module[{t, g}, If[n < 3, {}, t = TreeGf[n - 2]; g[e_] := Normal[t + O[x]^(Quotient[n, e]+1)] /. x -> x^e  + O[x]^(n+1); Sum[Sum[ EulerPhi[d]*g[d]^(k/d), {d, Divisors[k]}]/k + If[OddQ[k], g[1]* g[2]^Quotient[k, 2], (g[1]^2 + g[2])*g[2]^(k/2-1)/2], {k, 3, n}]]/2 // Drop[CoefficientList[#, x], 3]&];

seq[32] (* Jean-François Alcover, Oct 05 2019, after Andrew Howroyd's PARI code *)

PROG

(PARI) \\ TreeGf gives gf of A000081

TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}

seq(n)={if(n<3, [], my(t=TreeGf(n-2)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2))} \\ Andrew Howroyd, May 05 2018

CROSSREFS

Next-to-main diagonal of A054924. Cf. A000055.

Cf. A236570 (number of not necessarily connected n-node unicyclic graphs).

Sequence in context: A007020 A080888 A052988 * A148288 A320813 A278134

Adjacent sequences:  A001426 A001427 A001428 * A001430 A001431 A001432

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from R. C. Read (rcread(AT)math.uwaterloo.ca)

a(27) corrected, more terms, formula from Christian G. Bower, Feb 12 2002

Edited by Charles R Greathouse IV, Oct 05 2009

Terms a(30) and beyond from Andrew Howroyd, May 05 2018

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 November 17 00:08 EST 2019. Contains 329209 sequences. (Running on oeis4.)