Newsquestions2 2012-07-17 06:28:54
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
as there are (mk)! permutations of the characters in a string mk in
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
However there are only two cyclically different strings AABB and ABAB
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
Chip eastham 2012-07-17 23:25:32
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
George Polya developed a theory for counting these
arrangements. You might be interested in this nicely
written introduction to those methods:
Newsquestions2 2012-07-26 17:05:36
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.