3
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ But what is $A$? $\endgroup$ Oct 22, 2015 at 12:18
  • $\begingroup$ @Fedor Petrov, sequence, i fix it $\endgroup$
    – G H
    Oct 22, 2015 at 12:22

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.