A049287
Number of nonisomorphic circulant graphs, i.e., undirected Cayley graphs for the cyclic group of order n.
Original entry on oeis.org
1, 2, 2, 4, 3, 8, 4, 12, 8, 20, 8, 48, 14, 48, 44, 84, 36, 192, 60, 336, 200, 416, 188, 1312, 423, 1400, 928, 3104, 1182, 8768, 2192, 8364, 6768, 16460, 11144, 46784, 14602, 58288, 44424, 136128, 52488, 355200, 99880, 432576, 351424, 762608, 364724, 2122944, 798952, 3356408
Offset: 1
- Andrew Howroyd, Table of n, a(n) for n = 1..70
- V. Gatt, On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3, arXiv:1703.06038 [math.CO], 2017.
- V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001; J. Alg. Comb. 18 (2003) 189.
- V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
- Brendan McKay, Nauty home page.
- R. Poeschel, Publications.
- Eric Weisstein's World of Mathematics, Circulant Graph.
- Eric Weisstein's World of Mathematics, Circulant Matrix.
-
CountDistinct /@ Table[CanonicalGraph[CirculantGraph[n, #]] & /@ Subsets[Range[Floor[n/2]]], {n, 25}] (* Eric W. Weisstein, May 13 2017 *)
A049288
Number of nonisomorphic circulant tournaments, i.e., Cayley tournaments for cyclic group of order 2n-1.
Original entry on oeis.org
1, 1, 1, 2, 3, 4, 6, 16, 16, 30, 88, 94, 205, 457, 586, 1096, 3280, 5472, 7286, 21856, 26216, 49940, 174848, 182362, 399472, 1048576, 1290556, 3355456, 7456600, 9256396, 17895736, 59654816, 89478656, 130150588, 390451576, 490853416, 954437292
Offset: 1
- B. Alspach, On point-symmetric tournaments, Canad. Math. Bull., 13 (1970), 317-323. [Annotated copy] See r(n).
- B. Alspach, On point-symmetric tournaments, Canad. Math. Bull., 13 (1970), 317-323. See r(n).
- V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001.
- V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders
- R. Poeschel, Publications
- Index entries for sequences related to tournaments
A283189
Number of oriented circulant graphs of order n up to Cayley isomorphism.
Original entry on oeis.org
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
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}.
-
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 *)
-
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);
Showing 1-3 of 3 results.
Comments