|
| |
|
|
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)
|
|
7
|
|
|
|
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
|
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) ;
|
|
|
MATHEMATICA
|
terms = 31;
cycC[n_, a_] := Sum[EulerPhi[d] a[[d]]^(n/d), {d, Divisors[n]}]/n;
cyD[n_, a_] := Module[{cc}, cc = (1/2)cycC[n, a]; If[OddQ[n], (1/2)a[[1]]* a[[2]]^((n-1)/2)+cc, (1/4)(a[[1]]^2 a[[2]]^((n-2)/2) + a[[2]]^(n/2)) + cc]];
B[_] = 0; Do[B[x_] = Normal[(1/6) x (2 B[x^3] + 3 B[x^2] B[x] + B[x]^3) + O[x]^terms+1], terms];
A[x_] = (1/2) x (B[x^2] + B[x]^2) + O[x]^(terms+2);
a000642 = Rest[CoefficientList[A[x], x]];
g = {Sum[x^i a000642[[i]], {i, 1, terms+1}]};
For[i = 2, i <= Length[a000642], i++, g = Flatten[Append[g, g[[1]] /. x -> x^i]]];
For[G = 0; c = 2, c < terms+1, c++, f = cyD[c, g]; G = Series[f, {x, 0, terms+1}] + G];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
