0
$\begingroup$

The answers to these questions are presumably well known (and easy?).

Question 1: Given an alphabet of n letters (1,2,...n), how many distinct words of length r exists, considered up to cyclic permutation?

Question 2: How many such cyclic words exist if we do not allow the 2-letter subword "12"?.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Q1 is done easily by means of Mobius inversion, you can find answers everywhere really as one of the first examples of Mobius inversion. For Q2, I do not know any reference, but you can use inclusion-exclusion principle and look at number of words with at least $k$ occurrences of 12? $\endgroup$
    – Vladimir Dotsenko
    Nov 23, 2013 at 15:15
  • $\begingroup$ Vladimir's right about question 1, but it might be good to give a definite reference. See Free Lie Algebras by Christophe Reutenauer, Corollary 7.3. $\endgroup$
    – Todd Trimble ♦
    Nov 23, 2013 at 17:25

1 Answer 1

Reset to default
1
$\begingroup$

Q2: Essentially you want to know what is the number of periodic sequences of (minimal) period $r$ for the subshift of finite type given by the $n\times n$ matrix $M_n$ such that $M_{12}=0$ and $M_{ij}=1$ for all $(i,j)\neq (1,2)$.

The answer is $\text{trace}(M_n^r)$ - see [Katok & Hasselblatt, Modern Theory of Dynamical Systems, Corollary 1.9.5]. I am pretty sure this can be computed explicitly in this case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Why "minimal"? Or you mean that then we sum up things over all divisors? $\endgroup$
    – Vladimir Dotsenko
    Nov 24, 2013 at 16:39

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