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

Author

Geoffrey Critzer, Oct 21 2012

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A000088, A192332, A191563, A199574.

Programs

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 *)

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

Extensions

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