wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> permutation: number of rings possible with n balls
        
(Message started by: allbatros on Oct 23^rd, 2009, 10:24am)

Title: permutation: number of rings possible with n balls
Post by allbatros on Oct 23^rd, 2009, 10:24am

find the distinct number of rings possible (another variation is garlands possible) with n1 balls of one color, n2 balls of another color and so on ....

Title: Re: permutation: number of rings possible with n b
Post by R on Oct 23^rd, 2009, 12:12pm

on 10/23/09 at 10:24:31, allbatros wrote:

and so on ....

How many colors are there?

Title: Re: permutation: number of rings possible with n b
Post by towr on Oct 23^rd, 2009, 3:22pm

[hide]My best guess is that it's less than or equal to ([http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i=1..k n_i ]-1)! * min _i=1..k n_i / (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_i=1..k n_i! )

If you have a color that occurs only once, you can take that as the start of the ring, and just count the combinations of the rest. But if every color occurs more than once, it's difficult to pick a starting point in some systematic way; you may end up counting the same ring more than once.[/hide]

Title: Re: permutation: number of rings possible with n b
Post by allbatros on Oct 24^th, 2009, 12:43am

Hint: [hide]something to do with gcd[/hide]?

Title: Re: permutation: number of rings possible with n b
Post by allbatros on Oct 24^th, 2009, 12:45am

on 10/23/09 at 12:12:35, R wrote:

How many colors are there?

let m colors are there ;)

Title: Re: permutation: number of rings possible with n b
Post by allbatros on Oct 25^th, 2009, 6:47am

looks like no one is interested in putting some brainstorming for this question
I posted it since this question seems to be quite interesting to me,
you can find an algorithm with little working.
i will post my solution whenever you want

Title: Re: permutation: number of rings possible with n b
Post by allbatros on Oct 25^th, 2009, 6:49am

a good test case is with 4 red balls and 4 green balls
the answer should be 10

Title: Re: permutation: number of rings possible with n b
Post by R on Oct 25^th, 2009, 8:10am

on 10/25/09 at 06:47:20, allbatros wrote:

looks like no one is interested in putting some brainstorming for this question

Not even 2 days have passed since you posted it.

Quote:

I posted it since this question seems to be quite interesting to me,

Thank you :)

Quote:

i will post my solution whenever you want

What are you waiting for? Just [hide] it. :D

Title: Re: permutation: number of rings possible with n b
Post by towr on Oct 25^th, 2009, 8:22am

on 10/25/09 at 06:47:20, allbatros wrote:

looks like no one is interested in putting some brainstorming for this question

Actually, I hadn't thought you wanted an algorithm. I was considering only a mathematical solution; which left me stuck where I ended my previous post.

Title: Re: permutation: number of rings possible with n b
Post by william wu on Oct 25^th, 2009, 8:48am

I'm assuming that when you say "rings", you are referring to what the combinatorialists call "necklaces". Basically equivalence classes modulo the cyclic group. And when the number of beads of various colors is set a priori, these are called "necklaces of fixed content."

- For only a count of the necklaces with fixed content, you can use the Polya Enumeration Theorem, also called Orbit-Stabilizer or Burnside's Lemma.

- For an efficient algorithm for actually enumerating the necklaces with fixed content, check out the useful papers of Professor Joe Sawada. I think this paper addresses your problem: http://www.cis.uoguelph.ca/~sawada/papers/alph.pdf

Actually I have had exactly this same problem of both counting and enumerating necklaces of fixed content. The two approaches above are the solutions I used.

Title: Re: permutation: number of rings possible with n b
Post by R on Oct 25^th, 2009, 2:12pm

Now I am curious to know what solution allbatros had for this. ;)

Title: Re: permutation: number of rings possible with n b
Post by allbatros on Oct 30^th, 2009, 4:22am

Hi sorry for being inactive for last couple of days.

i went through the links william gave but completely greek.
I understand the permutation groups and cyclic index but unable to get the proof behind polya enumration theorem.
Also dont know how to get the object generating function in case of fixed content.
Can someone solve this problem for me through polya enumration theorem.

well the way i solved the question is as follows:
consider there are x number of ways of placing them in a ring.
pick one such arrangement and make n line permutations out of it but cutting this ring at different locations.
now in most of the cases all these line permutations will be different but except few. let x_nr be cases when all these n line permutations are different.

now remains the cases where all the line permutations will not be different.
before that we will state few things.
1. all the line permutations will be generated by one or the other ring permutations.
2. no line permutation which is generated by one of the ring permutation will be match the line permutation generated by other ring permutation.
3. cases in which ring permutation generates similar line permutations, the line permutation will look like something like (y)^m. here y is some arrangement of a subset of given sample.

so cases with repetition will be when m is a factor of gcd(n1,n2....).
find all such m find the cases of arranging the sample set/m into ring(recursively) let this be c_m

u_c_m be cases where we get exactly m unique line permutations, so we need to subtract from c_m cases where it repeat more that that i.e. subtract all u_c_n where n is one of the factor of m.

now with all these u_c_m we know how many unique permutations it generates and we know all the unique combination possible so we will get number of cases where the ring permutations generate all unique line permutations.

summing up all the above obtained number and all the u_c_m we get our answer.

Title: Re: permutation: number of rings possible with n b
Post by fakrudeen on Feb 4^th, 2010, 12:08am

Isn't this n!/ n * n1!*n2! ... nk!?

n for the reason it is a cycle.

n1!, n2 etc. for the reason they are of the same colour!

Title: Re: permutation: number of rings possible with n b
Post by towr on Feb 4^th, 2010, 1:00am

Try that formula with two beads of one color.