cp's OEIS Frontend

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

%I A283189 #26 Jan 10 2020 05:31:16
%S A283189 1,1,2,2,3,5,6,10,17,21,26,70,63,125,290,314,411,1121,1098,2558,5005,
%T A283189 5909,8054,23210,26589,44301,88826,134554,170823,598805,478318,908194,
%U A283189 2155345,2690421,5382190,10809394,10761723,21523445,48449998,72956830,87169619
%N A283189 Number of oriented circulant graphs of order n up to Cayley isomorphism.
%C A283189 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 A283189 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 A283189 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 A283189 Ideally this sequence should be to A060966 as A056391 is to A049297.
%H A283189 Andrew Howroyd, <a href="/A283189/b283189.txt">Table of n, a(n) for n = 1..500</a>
%e A283189 Case n=8:
%e A283189 Only 1, 3, 5, 7 are prime to 8.
%e A283189 Multiplication module 8 is described by the following multiplication table.
%e A283189 1 2 3 4 5 6 7 => (1)(2)(3)[4](5)(6)(7) => 6 => 3^3 => 27
%e A283189 3 6 1 4 7 2 5 => (1 3)[2 6][4](5 7)    => 2 => 3^1 =>  3
%e A283189 5 2 7 4 1 6 3 => (1 5)(2)(3 7)[4](6)   => 4 => 3^2 =>  9
%e A283189 7 6 5 4 3 2 1 => [1 7][2 6][3 5][4]    => 0 => 3^0 =>  1
%e A283189 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 A283189 The corresponding step sets (one from each equivalence class) are:
%e A283189 {}, {1}, {2}, {1,2}, {1,-2}, {1,3}, {1,-3}, {1,2,3}, {1,2,-3}, {1,-2,-3}.
%t A283189 IsLeastPoint[s_, r_, f_] := Module[{t}, t = f[s]; While[t > s && t != r, t = f[t]]; t == s && t != r];
%t A283189 c[n_, k_] := Sum[Boole@ IsLeastPoint[u, n-u, Mod[# k, n]&], {u, 1, n-1}]/2;
%t A283189 a[n_] := Sum[If[GCD[n, k] == 1, 3^c[n, k], 0], {k, 1, n}]/EulerPhi[n];
%t A283189 a /@ Range[1, 41] (* _Jean-François Alcover_, Sep 21 2019, from PARI *)
%o A283189 (PARI)
%o A283189 IsLeastPoint(s,r,f)={my(t=f(s)); while(t>s&&t<>r,t=f(t));t==s&&t<>r}
%o A283189 C(n,k)=sum(u=1,n-1,IsLeastPoint(u,n-u,v->v*k%n))/2;
%o A283189 a(n)=sum(k=1, n, if (gcd(n,k)==1, 3^C(n,k),0))/eulerphi(n);
%Y A283189 Cf. A060966, A056391, A049297.
%K A283189 nonn
%O A283189 1,3
%A A283189 _Andrew Howroyd_, Apr 30 2017