A283189 - OEIS

%I #26 Jan 10 2020 05:31:16

%S 1,1,2,2,3,5,6,10,17,21,26,70,63,125,290,314,411,1121,1098,2558,5005,

%T 5909,8054,23210,26589,44301,88826,134554,170823,598805,478318,908194,

%U 2155345,2690421,5382190,10809394,10761723,21523445,48449998,72956830,87169619

%N Number of oriented circulant graphs of order n up to Cayley isomorphism.

%C This sequence may be incorrect, but for the moment I don't think so. (Even if wrong it could represent something else.) In particular, this sequence should agree with A060966 for all squarefree n. For nonsquarefree n this sequence is allowed to be greater.

%C An oriented graph is a directed graph in which there is at most one edge between any two vertices. (A directed graph can have one in each direction.)

%C Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other.

%C Ideally this sequence should be to A060966 as A056391 is to A049297.

%H Andrew Howroyd, <a href="/A283189/b283189.txt">Table of n, a(n) for n = 1..500</a>

%e Case n=8:

%e Only 1, 3, 5, 7 are prime to 8.

%e Multiplication module 8 is described by the following multiplication table.

%e 1 2 3 4 5 6 7 => (1)(2)(3)[4](5)(6)(7) => 6 => 3^3 => 27

%e 3 6 1 4 7 2 5 => (1 3)[2 6][4](5 7)    => 2 => 3^1 =>  3

%e 5 2 7 4 1 6 3 => (1 5)(2)(3 7)[4](6)   => 4 => 3^2 =>  9

%e 7 6 5 4 3 2 1 => [1 7][2 6][3 5][4]    => 0 => 3^0 =>  1

%e Each row of the multiplication table can be viewed as a permutation and together these form a commutative group on 4 elements. In this case the group is isomorphic to the cyclic group C_4. Each permutation can be represented in cycle notation. However, only those cycles that do not include both a value and its negative can be used to form symmetrical solutions. In the above calculation, square brackets have been used to denote excluded cycles. Each remaining pair introduces a factor of 3 corresponding to no edge, or an edge in one of two directions. Putting everything together with Burnsides's lemma gives a(8) = (27 + 3 + 9 + 1)/4 = 10.

%e The corresponding step sets (one from each equivalence class) are:

%e {}, {1}, {2}, {1,2}, {1,-2}, {1,3}, {1,-3}, {1,2,3}, {1,2,-3}, {1,-2,-3}.

%t IsLeastPoint[s_, r_, f_] := Module[{t}, t = f[s]; While[t > s && t != r, t = f[t]]; t == s && t != r];

%t c[n_, k_] := Sum[Boole@ IsLeastPoint[u, n-u, Mod[# k, n]&], {u, 1, n-1}]/2;

%t a[n_] := Sum[If[GCD[n, k] == 1, 3^c[n, k], 0], {k, 1, n}]/EulerPhi[n];

%t a /@ Range[1, 41] (* _Jean-François Alcover_, Sep 21 2019, from PARI *)

%o (PARI)

%o IsLeastPoint(s,r,f)={my(t=f(s)); while(t>s&&t<>r,t=f(t));t==s&&t<>r}

%o C(n,k)=sum(u=1,n-1,IsLeastPoint(u,n-u,v->v*k%n))/2;

%o a(n)=sum(k=1, n, if (gcd(n,k)==1, 3^C(n,k),0))/eulerphi(n);

%Y Cf. A060966, A056391, A049297.

%K nonn

%O 1,3

%A _Andrew Howroyd_, Apr 30 2017