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

1, 1, 2, 2, 3, 5, 6, 10, 17, 21, 26, 70, 63, 125, 290, 314, 411, 1121, 1098, 2558, 5005, 5909, 8054, 23210, 26589, 44301, 88826, 134554, 170823, 598805, 478318, 908194, 2155345, 2690421, 5382190, 10809394, 10761723, 21523445, 48449998, 72956830, 87169619

Offset: 1

Author

Andrew Howroyd, Apr 30 2017

Keywords

• nonn

Comments

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.

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

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.

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

Examples

			Case n=8:
Only 1, 3, 5, 7 are prime to 8.
Multiplication module 8 is described by the following multiplication table.
1 2 3 4 5 6 7 => (1)(2)(3)[4](5)(6)(7) => 6 => 3^3 => 27
3 6 1 4 7 2 5 => (1 3)[2 6][4](5 7)    => 2 => 3^1 =>  3
5 2 7 4 1 6 3 => (1 5)(2)(3 7)[4](6)   => 4 => 3^2 =>  9
7 6 5 4 3 2 1 => [1 7][2 6][3 5][4]    => 0 => 3^0 =>  1
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.
The corresponding step sets (one from each equivalence class) are:
{}, {1}, {2}, {1,2}, {1,-2}, {1,3}, {1,-3}, {1,2,3}, {1,2,-3}, {1,-2,-3}.
		

Links

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

Crossrefs

Cf. A060966, A056391, A049297.

Programs

Mathematica

IsLeastPoint[s_, r_, f_] := Module[{t}, t = f[s]; While[t > s && t != r, t = f[t]]; t == s && t != r];
c[n_, k_] := Sum[Boole@ IsLeastPoint[u, n-u, Mod[# k, n]&], {u, 1, n-1}]/2;
a[n_] := Sum[If[GCD[n, k] == 1, 3^c[n, k], 0], {k, 1, n}]/EulerPhi[n];
a /@ Range[1, 41] (* Jean-François Alcover, Sep 21 2019, from PARI *)

PARI

IsLeastPoint(s,r,f)={my(t=f(s)); while(t>s&&t<>r,t=f(t));t==s&&t<>r}
C(n,k)=sum(u=1,n-1,IsLeastPoint(u,n-u,v->v*k%n))/2;
a(n)=sum(k=1, n, if (gcd(n,k)==1, 3^C(n,k),0))/eulerphi(n);