A218144 Number of inequivalent graphs on n nodes where two graphs are equivalent if adjacency is preserved under the action of the alternating group.

1, 2, 4, 12, 40, 184, 1296, 17072, 424992, 20314096, 1836858752, 310029536960, 97286240288512, 56843800957620672, 62057188173197829888, 127071179605916892107264, 489838590133142165412740096, 3566828190793813383233169950592, 49211415580467941255510544567667200

Offset

1,2

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Example

a(4) = 12 because we have the 11 classes of graphs (A000088) under the action of the symmetric group but the class represented by (say) 1-2-3-4 is separate from the class of graphs that could be represented by 2-1-3-4.

Mathematica

CoefficientList[Table[PairGroupIndex[AlternatingGroup[n], s]/.Table[s[i]->2, {i, 1, Binomial[n, 2]}], {n, 1, 7}], x]
(* Second program: *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, 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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
g[n_, r_] := (s = 0; Do[s += permcount[p]*(2^(r*Length[p] + edges[p])), {p, IntegerPartitions[n]}]; s/n!); a[1] = 1;
a[n_] := (s = 0; Do[If[EvenQ[Total[p - 1]], s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; 2*s/n!);
Array[a, 20] (* Jean-François Alcover, Jul 09 2018, after Andrew Howroyd *)

Prog

(PARI)
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, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, if(sum(i=1, #p, p[i]-1)%2==0, s+=permcount(p)*2^edges(p))); if(n==1, 1, 2*s/n!)} \\ Andrew Howroyd, May 22 2018

Crossrefs

Cf. A000088, A192332, A191563, A199574.

Sequence in context: A134983 A330679 A342225 * A222919 A264760 A090959

Adjacent sequences: A218141 A218142 A218143 * A218145 A218146 A218147

Keyword

nonn

Author

Geoffrey Critzer, Oct 21 2012

Extensions

Terms a(11) and beyond from Andrew Howroyd, May 22 2018

Status

approved