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)?

$\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$ 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$ 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
    Sep 14, 2010 at 17:32

2 Answers 2

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$).

$\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
    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.

$\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
    Sep 16, 2010 at 6:56

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.