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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002094 Number of unlabeled connected loop-less graphs on n nodes containing exactly one cycle (of length at least 2) and with all nodes of degree <= 4.
(Formerly M1383 N0541)
5
0, 1, 2, 5, 10, 25, 56, 139, 338, 852, 2145, 5513, 14196, 36962, 96641, 254279, 671640, 1781840, 4742295, 12662282, 33898923, 90981264, 244720490, 659591378, 1781048728, 4817420360, 13050525328, 35405239155, 96180222540, 261603173201, 712364210543 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

A pair of parallel edges is permitted and is regarded as a cycle of length 2.

The original definition in A Handbook of Integer Sequences (1973) based on Schiff (1875) was simply "Alcohols". - N. J. A. Sloane, Mar 22 2018

Schiff used an now outdated terminology and did not use the term "alcohols", but in German "zweiwerthige Kohlenwasserstoffe C_{n}H_{2n} ..." and later ".. deren je zwei verfuegbare Affinitaeten ... durch Alkoholradikale befriedigt sind.", translated "bivalent hydrocarbons  ... whose free valences ... are covered by alcohol radicals". At that time the meaning of "alcohol radical" was different from modern terminology, now meaning an -OH group, but in Schiff's terminology another C_{x}H{y} hydrocarbon group was meant. The organic compounds that are described by the graphs of this sequence in modern chemical terminology are the acyclic alkenes, with exactly one double carbon-to-carbon bond, and the monocyclic cycloalkanes  (see Wikipedia links). - Hugo Pfoertner, Mar 29 2018

REFERENCES

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

Vaclav Kotesovec, Table of n, a(n) for n = 1..400

R. J. Mathar, Illustration for graphs up to 6 carbons, 2018

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

Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875.

Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]

Wikipedia, Alkene. Those with exactly one double carbon-to-carbon bond are covered by this sequence, the simplest being ethylene C_{2}H_{4}.

Wikipedia, Cycloalkane. The simplest alicyclic compounds, which are the monocyclic saturated hydrocarbons with formula C_{n}H_{2n}, are covered by this sequence, the first example being cyclopropane C_{3}H_{6}.

FORMULA

Let A(x) denote the generating function for A000598 (Number of rooted ternary trees with n nodes), i.e., A(x) = 1+(1/6)*x*(A(x)^3+3*A(x)*A(x^2)+2*A(x^3)), and set B(x)=(A(x)^2+A(x^2))/2. With D_k(x) being the cycle polynomial of the regular k-gon for k>=2, the final generating function is then given by Sum_{k>=2} x^k*D_k(B(x)), which can be evaluated very quickly. - Sascha Kurz, Mar 18 2018

MAPLE

# cycle index of cyclic group C_n

cycC_n := proc(n::integer, a)

    local d ;

    add(numtheory[phi](d)*a[d]^(n/d), d=numtheory[divisors](n)) ;

    %/n ;

end proc:

# cycle index of dihedral group

cyD_n := proc(n::integer, a)

    cycC_n(n, a)/2 ;

    if type(n, 'odd') then

        %+ a[1]*a[2]^((n-1)/2)/2 ;

    else

        %+ ( a[1]^2*a[2]^((n-2)/2) +a[2]^(n/2) )/4 ;

    end if;

end proc:

a000642 := [

    1, 1, 2, 3, 7, 14, 32, 72, 171, 405, 989, 2426, 6045, 15167, 38422, 97925,

    251275, 648061, 1679869, 4372872, 11428365, 29972078, 78859809, 208094977,

    550603722, 1460457242, 3882682803, 10344102122, 27612603765, 73844151259,

    197818389539,  530775701520, 1426284383289] ;

g := [add(a000642[i]*x^i, i=1..nops(a000642)) ];

for i from 2 to nops(a000642) do

    g := [op(g), subs(x=x^i, g[1]) ] ;

end do:

Nmax := nops(a000642) :

G := 0 ;

for c from 2 to Nmax do

    f := cyD_n(c, g) ;

    G := G+ taylor(f, x=0, Nmax) ;

end do:

taylor(G, x=0, Nmax) ;

gfun[seriestolist](%) ; # R. J. Mathar, Mar 17 2018

CROSSREFS

Cf. A000294, A000598, A000602, A000625, A000642, A001429 (unbound degrees), A068051.

Sequence in context: A026383 A162963 A297860 * A212709 A264867 A115725

Adjacent sequences:  A002091 A002092 A002093 * A002095 A002096 A002097

KEYWORD

nonn

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Better definition from R. J. Mathar; terms beyond 852 from R. J. Mathar and Sean A. Irvine, Mar 17 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 August 19 18:51 EDT 2019. Contains 326133 sequences. (Running on oeis4.)