OFFSET
0,2
COMMENTS
From Pab Ter (pabrlos2(AT)yahoo.com), Jan 24 2006: (Start)
The number of equivalence classes of sequences of period p, taking values in a set with b elements, is given by:
N(p) = (1/(p*phi(p)))*Sum_{t=0..p-1} Sum_{k=1..p-1 & gcd(p,k)=1} b^C(k,t) where C(k,t), the number of disjoint cycles of the permutations considered, is C(k,t) = Sum_{u=0..p-1} 1/M(k,p/gcd(p,u(k-1)+t)).
If gcd(k,L)=1, M(k,L) denotes the least positive integer M such that 1+k+...+k^(M-1) == 0 (mod L). Also if gcd(k,L)=1 and Ek(L) denotes the exponent of k mod L: M(k,L)=L*Ek(L)/gcd(L,1+k+...+k^(Ek(L)-1)).
(End)
Number of two-colored necklaces of length n, where similar necklaces are counted only once. Two necklaces of length n, given by color functions c and d from {0, ..., n-1} to N (set of natural numbers) are considered similar iff there is a factor f, 0 < f < n, satisfying gcd(f,n) = 1, such that, for all k from {0, ..., n-1}, d(f * k mod n) = c(k). I.e., the bead at position k is moved to f * k mod n. In other words: the sequence counts the orbits of the action of the multiplicative group {f | 0 < f < n, gcd(f,n) = 1} on the set of two-colored necklaces where f maps c to d with the formula above. - Matthias Engelhardt
REFERENCES
D. Z. Dokovic, I. Kotsireas, D. Recoskie, J. Sawada, Charm bracelets and their application to the construction of periodic Golay pairs, Discrete Applied Mathematics, Volume 188, 19 June 2015, Pages 32-40.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..50
CombOS - Combinatorial Object Server, Generate necklaces, Lyndon words, chord diagrams, and relatives.
D. Z. Dokovic, I. Kotsireas et al., Charm bracelets and their application to the construction of periodic Golay pairs, arXiv:1405.7328 [math.CO], 2014.
M. Engelhardt, The N queens problem.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
FORMULA
Reference gives formula.
MAPLE
with(numtheory): M:=proc(k, L) local e, s: s:=1: for e from 1 do if(s mod L = 0) then RETURN(e) else s:=s+k^e fi od: end; C:=proc(k, t, p) local u: RETURN(add(M(k, p/igcd(p, u*(k-1)+t))^(-1), u=0..p-1)) :end; N:=proc(p) options remember: local s, t, k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 do for k from 1 to p-1 do if igcd(p, k)=1 then s:=s+2^C(k, t, p) fi od od: RETURN(s/(p*phi(p))):end; seq(N(p), p=1..51); # first M expression
with(numtheory): E:=proc(k, L) if(L=1) then RETURN(1) else RETURN(order(k, L)) fi end; M:=proc(k, L) local s, EkL: EkL:=E(k, L): if(k>1) then s:=(k^EkL-1)/(k-1): RETURN(L*EkL/igcd(L, s)) else RETURN(L*EkL/igcd(L, EkL)) fi end; C:=proc(k, t, p) local u: RETURN(add(M(k, p/igcd(p, u*(k-1)+t))^(-1), u=0..p-1)) :end; N:=proc(p) options remember: local s, t, k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 do for k from 1 to p-1 do if igcd(p, k)=1 then s:=s+2^C(k, t, p) fi od od: RETURN(s/(p*phi(p))):end; seq(N(p), p=1..51); # second M expression (Pab Ter)
MATHEMATICA
max = 38; m[k_, n_] := (s = 1; Do[ If[ Mod[s, n] == 0, Return[e], s = s + k^e ] , {e, 1, max}]); c[k_, t_, n_] := Sum[ m[k, n/GCD[n, u*(k-1) + t]]^(-1), {u, 0, n-1}]; a[n_] := (s = 0; Do[ If[ GCD[n, k] == 1 , s = s + 2^c[k, t, n]] , {k, 1, n-1}, {t, 0, n-1}]; s/(n*EulerPhi[n])); a[0] = 1; a[1] = 2; Table[a[n], {n, 0, max}] (* Jean-François Alcover, Dec 06 2011, after Maple *)
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
Entry revised by N. J. A. Sloane at the suggestion of Max Alekseyev, Jun 20 2007
STATUS
approved