So we have three possible rotations of the string 011
:
011
110
101
- Each of these rotations are unique, since they can be totally ordered usinglexicographic ordering. Indeed, for any string other than
000
, 111
,all of its rotations are unique.
- So we can count the above 7 strings with equivalence class representatives.These representatives are those strings that are the lex smallest in theircyclic shifts. (Why are cyclic shifts so important?)
Cyclic subshifts of strings:
---------------------------
000, 000, 000
001, 010, 100
011, 110, 101
111, 111, 111
- We've written the strings along with their cyclic subshifts, with therepresentative of the equivalence class as the first element. So therepresentatitives are
000, 001, 011, 111
. Note that two of these (000, 111
)are equal to their cyclic subshifts. All of the others are distinct, and generate3 elements.
- So we can count the above strings as:
all strings = {shifts of 001, 011}U{000, 111}
|all strings| = |{shifts of 001, 011}|+|{000, 111}|
no. of shifts = 3*(no. of representatives)
2^3 = 3 * (no. of representatives) + 2
2^3 = 3 * (no. of representatives) + 2
2^3 % 3 = 2
In general, for x^p % p
, we will get x
strings that contain the same letter.
These will not have elements in their cyclic shift equivalence classes. The
other strings will be generated as the smallest cyclic subshift of some
string.
§ Why does this not work when p
is not prime?
Let p = 4
. In this case, I can pick the string s = 0101
. It has shifts:
0101 <-
1010
0101 <-
1010
so two of its shifts overlap, hence we will double-count the string 0101
if I counted its equivalence class as having size 4
.
§ Relationship to group theory?
- How does this relate to group theory? Well, what we are doing is providingan action of the group
Z/pZ
into the set of strings X^p
where X
issome set. Our group action for a number n ∈ Z/pZ
takes astring s ∈ X^p
to its cyclic shift by n
characters.
- We are then using the fact that the orbits of an action when
p
is primehas size either 1
or p
, since the size of the orbit divides thesize of the group Z/pZ
, which is p
, a prime. The divisors ofp
are only 1
and p
. Therefore, the size of the orbit is either 1
or p
.
- Only necklaces that have identical elements like
000
and 111
haveorbits of size 1
. We have |X|
such necklaces.
- All other necklaces have size
p
.
- The rest of the proof follows similarly as before.
§ References