Cyclic sequence is equivalence class of cyclic shift action.


If $a = (a\_1, ... , a\_i)\_c$ is cyclic sequence then $(a\_1, a\_2, \ldots a\_{i-1}, a\_i)\_c = (a\_2, a\_3, \ldots, a\_i, a\_1)\_c = \ldots = (a\_i, a\_1, \ldots , a\_{i-2}, a\_{i-1})\_c$.


Let $i = 2^n$, $\forall a$ $a\_j \in \{0,1,2,3,4\}$, and $\forall a$ $|\{a\_j:a\_j \in a \}| < 4$.


I want to find number and asymptotic for all such cyclic sequences.


Thank you for any help!



Number and asymptotic for cyclic sequences
You are essentially counting necklaces, see e.g. <http://theory.cs.uvic.ca/inf/neck/NecklaceInfo.html>. The number of necklaces of length $l$ over a $k$-element alphabet is


$N\_k(l)=\frac{1}{l}\sum\_{d|l}\phi(\frac{l}{d})k^d$.


In your case, $l=2^n$, so the above simplifies to


$N\_k^\*(n)=2^{-n}\sum\_{j=0}^n2^{n-j-1}k^{2^j} = \sum\_{j=0}^n2^{-j-1}k^{2^j}$.


Finally, the constraints (at most $3$ different symbols from $\{0,\dots,4\}$) get you an inclusion-exclusion chain


$\binom{5}{3}N\_3^\*(n)-\binom{5}{2}N\_2^\*(n)+\binom{5}{1}N\_1^\*(n) = 5 \sum\_{j=0}^n2^{-j-1}(2\cdot3^{2^j}-2\cdot 2^{2^j}+1)$ 


for the number you are seeking.


