Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
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 –  Gordon Royle Sep 14 '10 at 7:54
1  
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. –  Victor Protsak Sep 14 '10 at 7:54
    
@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. –  Mark Bell Sep 14 '10 at 17:32
add comment

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
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 ;-) –  ccarminat Sep 16 '10 at 6:52
add comment

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.

share|improve this answer
1  
Thanks! Beware: there is a flaw in your link, due to the fact that the final ")" is missing in the url. –  ccarminat Sep 16 '10 at 6:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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