Newsquestions22012-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

(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

Chip eastham2012-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

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

Newsquestions22012-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.

so thanks!

## Leave a Reply

You must be logged in to post a comment.