7
$\begingroup$

Let W be a finite word on a two symbol alphabet {0,1}; let us say that W is maximal if it is the last item in the list of all its cyclic permutation (ordered lexicographically).

So, for instance: {0,1} are the maximal words of length 1; {00, 10, 11} are the maximal words of length 2; {000, 100, 110, 111} are the maximal words of length 3; {0000, 1000, 1010, 1100, 1110, 1111} are the maximal words of length 4; {00000, 10000, 10100, 11000, 11010, 11100, 11110, 11111} are the maximal words of length 5; ... und so weiter.

Let k(n):= number of maximal words of length n

Is there some formula for k(n)?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Isn't this just asking for the number of equivalence classes under cyclic permutations? These are called necklaces (or possibly bracelets, I can never remember the difference) and are well studied. See oeis.org/A000031 $\endgroup$
    – Gordon Royle
    Commented Sep 14, 2010 at 7:54
  • 1
    $\begingroup$ By definition, every cyclic conjugacy class of words of length n contains a unique maximal word. So this problem can be restated as: how many orbits are there for the action of the cyclic group of order n on the words of length n over alphabet {0,1} by cyclic rotations. $\endgroup$
    – Victor Protsak
    Commented Sep 14, 2010 at 7:54
  • $\begingroup$ @Gordon A necklaces is the equivalence class of a word under cyclic permutation, a bracelet is the equivalence class of a word under cyclic permutation and reflection. $\endgroup$
    – Mark Bell
    Commented Sep 14, 2010 at 17:32

2 Answers 2

Reset to default
6
$\begingroup$

For aperiodic (sometimes also called, full period) strings, the term you are looking for is Lyndon words. These are the (unique lexicographically-least) representative of a full-period necklace (as stated in the comments, a necklace is the equivalence class under cyclic rotation). The number $k(n)$ you ask for is exactly the number of necklaces, and again, as stated in the comments, it is given by $k(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}$. You can check out a proof for this in S.W.Golomb's book "Shift Register Sequences" (in the 1967 edition, start looking at around page 171 and look for the cycles of $PCR_n$).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks to everybody! As a matter of fact, I had checked if the first few items of the sequence were already listed in the "Encyclopedia of integer sequences", but -alas!- I did not find the right answer because of a mistake in the count of 8-letters "maximal" words :-( I hope this will not affect my reputation ;-) $\endgroup$
    – ccarminat
    Commented Sep 16, 2010 at 6:52
6
$\begingroup$

please see wikipedia : http://en.wikipedia.org/wiki/Necklace_(combinatorics)

It represents a structure with n circularly connected beads of up to k different colors or numbers.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks! Beware: there is a flaw in your link, due to the fact that the final ")" is missing in the url. $\endgroup$
    – ccarminat
    Commented Sep 16, 2010 at 6:56

You must log in to answer this question.

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