|
| |
|
|
A283189
|
|
Number of oriented circulant graphs of order n up to Cayley isomorphism.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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}.
|
|
|
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];
|
|
|
PROG
|
(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);
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
