Mombu the Science Forum sponsored links

Go Back   Mombu the Science Forum > Science > Counting strings up to cyclic rotation
User Name
Password
REGISTER NOW! Mark Forums Read

sponsored links


Reply
 
1 17th July 06:28
newsquestions2003
External User
 
Posts: 1
Default 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
  Reply With Quote


  sponsored links


2 17th July 23:25
chip eastham
External User
 
Posts: 1
Default Counting strings up to cyclic rotation


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
  Reply With Quote
3 26th July 17:05
newsquestions2003
External User
 
Posts: 1
Default 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!
  Reply With Quote
Reply


Thread Tools
Display Modes




Copyright 2006 SmartyDevil.com - Dies Mies Jeschet Boenedoesef Douvema Enitemaus -
666