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!

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .