OFFSET
0,3
REFERENCES
R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, Oct 1989.
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 = 0..50
R. C. Read, The Enumeration of Mating-Type Graphs, Dept. Combinatorics and Optimization, Univ. Waterloo, Oct 1989. (Annotated scanned copy)
FORMULA
G.f. Sum_{n>=1} x^n * (Sum_{(j)} h((j)) * 2^Y((j)) * Product_{i=1..n} (1-x^i)^{j_i}) where the inner sum runs over all partitions (j) = j_1j_2...j_m of n = 1 * j_1 + 2 * j_2 + ... _ m * j_m, h((j)) = 1 / Product_{i=1..m} (j_i! * i^{j_i}), and Y((j)) = Sum_{i=1..m} (i-1) * j_i + Sum_{i=1..m} i * j_i * (j_i - 1) + 2 * Sum_{1 <= i < k <= m} j_i * j_k * gcd(i, k). - Sean A. Irvine, Mar 06 2018
MATHEMATICA
permcount[v_] := Module[{m = 1, s = 0, t, i, k = 0}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Sum[v[[i]] - 1, {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, If[n == 0, Return[1]]; Sum[Do[ s += permcount[p]* 2^edges[p] * Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {p, IntegerPartitions[k]}], {k, 1, n}]; s];
a /@ Range[0, 20] (* Jean-François Alcover, Sep 22 2019, after Andrew Howroyd *)
PROG
(PARI) \\ compare A000273.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}
a(n) = {if(n<1, n==0, my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s)} \\ Andrew Howroyd, Sep 09 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(0)=1 prepended by Andrew Howroyd, Sep 09 2018
STATUS
approved