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

%I #20 Jul 09 2018 04:30:15

%S 1,2,4,12,40,184,1296,17072,424992,20314096,1836858752,310029536960,

%T 97286240288512,56843800957620672,62057188173197829888,

%U 127071179605916892107264,489838590133142165412740096,3566828190793813383233169950592,49211415580467941255510544567667200

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

%H Andrew Howroyd, <a href="/A218144/b218144.txt">Table of n, a(n) for n = 1..50</a>

%e 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.

%t CoefficientList[Table[PairGroupIndex[AlternatingGroup[n],s]/.Table[s[i]->2,{i,1,Binomial[n,2]}],{n,1,7}],x]

%t (* Second program: *)

%t 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];

%t edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];

%t g[n_, r_] := (s = 0; Do[s += permcount[p]*(2^(r*Length[p] + edges[p])), {p, IntegerPartitions[n]}]; s/n!); a[1] = 1;

%t a[n_] := (s = 0; Do[If[EvenQ[Total[p - 1]], s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; 2*s/n!);

%t Array[a, 20] (* _Jean-François Alcover_, Jul 09 2018, after _Andrew Howroyd_ *)

%o (PARI)

%o 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}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}

%o 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

%Y Cf. A000088, A192332, A191563, A199574.

%K nonn

%O 1,2

%A _Geoffrey Critzer_, Oct 21 2012

%E Terms a(11) and beyond from _Andrew Howroyd_, May 22 2018