|
| |
|
|
A000368
|
|
Number of connected graphs with one cycle of length 4.
(Formerly M3365 N1356)
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
4,3
|
|
|
REFERENCES
|
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).
|
|
|
LINKS
|
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
|
|
|
FORMULA
|
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
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(PARI) 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
|
|
|
CROSSREFS
|
Column k=4 of A217781.
Cf. A000081, A000226, A001429, A005703.
Second diagonal of A058879.
Sequence in context: A244968 A071258 A120333 * A232765 A094255 A192234
Adjacent sequences: A000365 A000366 A000367 * A000369 A000370 A000371
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
