A285522 Array read by antidiagonals: T(m,n) = number of circulant digraphs up to Cayley isomorphism on n vertices with edges colored according to step value using a maximum of m-1 colors.
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 6, 4, 1, 1, 6, 18, 10, 5, 1, 1, 20, 24, 40, 15, 6, 1, 1, 14, 135, 70, 75, 21, 7, 1, 1, 48, 130, 544, 165, 126, 28, 8, 1, 1, 52, 648, 700, 1625, 336, 196, 36, 9, 1, 1, 140, 1137, 4480, 2635, 3996, 616, 288, 45, 10, 1
Offset: 1
Examples
Table starts: \n 1 2 3 4 5 6 7 8 9 10 m\ --------------------------------------------------- 1 | 1 1 1 1 1 1 1 1 1 1 ... 2 | 1 2 3 6 6 20 14 48 52 140 ... 3 | 1 3 6 18 24 135 130 648 1137 4995 ... 4 | 1 4 10 40 70 544 700 4480 11056 65824 ... 5 | 1 5 15 75 165 1625 2635 20625 65425 489125 ... 6 | 1 6 21 126 336 3996 7826 72576 280596 2521476 ... ... Case n=10: Only 1, 3, 7, 9 are prime to 10. Multiplication modulo 10 is described by the following multiplication table. 1, 2, 3, 4, 5, 6, 7, 8, 9 => (1)(2)(3)(4)(5)(6)(7)(8)(9) => m^9 3, 6, 9, 2, 5, 8, 1, 4, 7 => (1397)(2684)(5) => m^3 7, 4, 1, 8, 5, 2, 9, 6, 3 => (1793)(2486)(5) => m^3 9, 8, 7, 6, 5, 4, 3, 2, 1 => (19)(28)(37)(46)(5) => m^5 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. (shown above to the right of the corresponding multiplication table row). In order to count the equivalence classes using Polya's enumeration theorem only the number of cycles in each permutation is needed. This gives the cycle index polynomial (1/4)*(m^9 + m^5 + 2*m^3). Putting m = 1..4 gives 1, 140, 4995, 65824.
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275
- V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
- R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
- Eric Weisstein's World of Mathematics, Circulant Graph.
- Wikipedia, Polya enumeration theorem.
Crossrefs
Programs
-
Mathematica
A132191[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #] &], 0], {k, 1, n}]; T[m_, n_] := A132191[m, n]/m; Table[T[m - n + 1, n], {m, 1, 11}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)
-
PARI
a(n,x)=sum(k=1, n, if(gcd(k, n)==1, x^(sumdiv(n, d, eulerphi(d)/znorder(Mod(k, d)))-1), 0))/eulerphi(n); for(m=1, 6, for(n=1, 10, print1( a(n,m), ", ") ); print(); );
Formula
T(m, n) = A132191(m, n) / m.
Comments