A049297 - OEIS

%I #26 Aug 06 2024 06:30:29

%S 1,2,3,6,6,20,14,46,51,140,108,624,352,1400,2172,4262,4116,22040,

%T 14602,68016,88376,209936,190746,1062592,839094,2797000,3728891,

%U 11276704,9587580,67195520,35792568

%N Number of nonisomorphic circulant digraphs (i.e., Cayley digraphs for the cyclic group) of order n.

%C Terms may be computed by filtering potentially isomorphic graphs of A056391 through nauty. Terms computed in this way for a(25), a(27) agree with theoretical calculations by others. - _Andrew Howroyd_, Apr 23 2017

%H V. A. Liskovets, <a href="https://arxiv.org/abs/math/0104131">Some identities for enumerators of circulant graphs</a>, arXiv:math/0104131 [math.CO], 2001.

%H V. A. Liskovets and R. Poeschel, <a href="https://citeseerx.ist.psu.edu/pdf/b76573e0c2df2ff117cef015809e232a3747f585">On the enumeration of circulant graphs of prime-power and squarefree orders</a>.

%H R. Poeschel, <a href="http://www.math.tu-dresden.de/~poeschel/Publikationen.html">Publications</a>.

%H V. Gatt, <a href="https://arxiv.org/abs/1703.06038">On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3</a>, arXiv:1703.06038 [math.CO], 2017.

%H Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, <a href="https://doi.org/10.1007/978-3-030-32808-5_2">From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices</a>, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.

%H Brendan McKay, <a href="http://users.cecs.anu.edu.au/~bdm/nauty/">Nauty home page</a>.

%F There is an easy formula for prime orders. Formulae are also known for squarefree and prime-squared orders.

%F From _Andrew Howroyd_, Apr 23 2017: (Start)

%F a(n) <= A056391(n).

%F a(n) = A056391(n) for squarefree n.

%F a(A000040(n)^2) = A038777(n).

%F (End)

%o (GAP)

%o LoadPackage("grape");

%o CirculantDigraphCount:= function(n) local g; # slow for n >= 10

%o g:=Graph( Group(()), [1..n], OnPoints, function(x,y) return (y-x) mod n = 1; end,false);

%o return Length(GraphIsomorphismClassRepresentatives(List(Combinations([1..n]), s->DistanceGraph(g,s))));

%o end; # _Andrew Howroyd_, Apr 23 2017

%Y Cf. A049287-A049289, A056391, A038777.

%K nonn,nice

%O 1,2

%A _Valery A. Liskovets_

%E Further values for (twice) squarefree and (twice) prime-squared orders can be found in the Liskovets reference.

%E a(14) corrected by _Andrew Howroyd_, Apr 23 2017

%E a(16)-a(31) from _Andrew Howroyd_, Apr 23 2017