Counting strings up to cyclic rotation

I want to know a formula for the number of strings containing m of
each of k > 1 distinct characters (so the strings are of length mk)
that are "cyclically different". What i mean by this is "can't be
rotated to make the same string"...so the strings ABC BCA and CAB are
all the same cyclically, but they are all different to, for example,
the string ACB.

I reckon the number of strings with m occurences of each of k
characters is simply

(mk)!
-----
(m!)^k

as there are (mk)! permutations of the characters in a string mk in
length,
but the m occurences of each of the k characters can be permuted
without making a difference.

However, I can't tell what I need to divide the above number by to get
the number of cyclically different strings.

An example might help to explain. Imagine i wanted to get all
cyclically different strings containing two As and two Bs (so of
length 4). The formula above gives me the answer six, corresponding
to the six strings
i/ AABB
ii/ ABAB
iii/ ABBA
iv/ BABA
v/ BAAB
vi/ BBAA

However there are only two cyclically different strings AABB and ABAB
as
i/,iii/,v/ and vi/ are all in the same class as AABB, and ii/ and iv/
are both in the same class as ABAB.

How do I tell how many cyclic equivalence classes there are (so I know
what to divide my formula by)? Or how do I count the number of
cyclically different strings of length mk containing m occurrences of
each of my k characters in some other way? I'm stuck!

Thanks in advance for any help

Apparently you've thought about this enough to realize
what the central difficulty in this sort of problem is.

These are sometimes referred to as "bead problems"
or "necklace problems" because of the equivalence
of an arrangement of colored beads on a necklace
under rotation.

George Polya developed a theory for counting these
arrangements. You might be interested in this nicely
written introduction to those methods:

http://www.geometer.org/mathcircles/polya.pdf

regards, chip

great -- that explains what i wanted to know perfectly. incidentally,
having read and tried to apply polya's method to the results of a
computer program i'd written, i found a disagreement -- this was
because the program was losing some permutations along the way -- i'd
never have noticed this without knowing the correct number.

so thanks!

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode test 33Switch to Hybrid Mode Switch to Threaded Mode

3 26th July 17:05 newsquestions2003 External User Posts: 1	Counting strings up to cyclic rotation great -- that explains what i wanted to know perfectly. incidentally, having read and tried to apply polya's method to the results of a computer program i'd written, i found a disagreement -- this was because the program was losing some permutations along the way -- i'd never have noticed this without knowing the correct number. so thanks!