Author |
Topic: permutation: number of rings possible with n balls (Read 1117 times) |
|
allbatros
Newbie
Posts: 50
|
 |
permutation: number of rings possible with n balls
« on: Oct 23rd, 2009, 10:24am » |
 Quote  Modify
|
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 ....
|
|
 IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender: 
Posts: 502
|
|
Re: permutation: number of rings possible with n b
« Reply #1 on: Oct 23rd, 2009, 12:12pm » |
Quote Modify
|
on Oct 23rd, 2009, 10:24am, allbatros wrote:
How many colors are there?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: permutation: number of rings possible with n b
« Reply #2 on: Oct 23rd, 2009, 3:22pm » |
Quote Modify
|
My best guess is that it's less than or equal to ([ i=1..k ni ]-1)! * min i=1..k ni / ( i=1..k ni! )
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
allbatros
Newbie
Posts: 50
|
|
Re: permutation: number of rings possible with n b
« Reply #3 on: Oct 24th, 2009, 12:43am » |
Quote Modify
|
Hint: something to do with gcd?
|
| « Last Edit: Oct 24th, 2009, 12:48am by allbatros » |
IP Logged |
|
|
|
allbatros
Newbie
Posts: 50
|
|
Re: permutation: number of rings possible with n b
« Reply #4 on: Oct 24th, 2009, 12:45am » |
Quote Modify
|
on Oct 23rd, 2009, 12:12pm, R wrote:
How many colors are there?
|
|
let m colors are there 
|
|
IP Logged |
|
|
|
allbatros
Newbie
Posts: 50
|
|
Re: permutation: number of rings possible with n b
« Reply #5 on: Oct 25th, 2009, 6:47am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
allbatros
Newbie
Posts: 50
|
|
Re: permutation: number of rings possible with n b
« Reply #6 on: Oct 25th, 2009, 6:49am » |
Quote Modify
|
a good test case is with 4 red balls and 4 green balls
the answer should be 10
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: permutation: number of rings possible with n b
« Reply #7 on: Oct 25th, 2009, 8:10am » |
Quote Modify
|
on Oct 25th, 2009, 6:47am, 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. 
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: permutation: number of rings possible with n b
« Reply #8 on: Oct 25th, 2009, 8:22am » |
Quote Modify
|
on Oct 25th, 2009, 6:47am, 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.
|
| « Last Edit: Oct 25th, 2009, 8:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: permutation: number of rings possible with n b
« Reply #9 on: Oct 25th, 2009, 8:48am » |
Quote Modify
|
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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: permutation: number of rings possible with n b
« Reply #10 on: Oct 25th, 2009, 2:12pm » |
Quote Modify
|
Now I am curious to know what solution allbatros had for this.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
allbatros
Newbie
Posts: 50
|
|
Re: permutation: number of rings possible with n b
« Reply #11 on: Oct 30th, 2009, 4:22am » |
Quote Modify
|
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 xnr 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 cm
u_cm be cases where we get exactly m unique line permutations, so we need to subtract from cm cases where it repeat more that that i.e. subtract all u_cn where n is one of the factor of m.
now with all these u_cm 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_cm we get our answer.
|
| « Last Edit: Oct 30th, 2009, 4:23am by allbatros » |
IP Logged |
|
|
|
fakrudeen
Newbie
Posts: 5
|
|
Re: permutation: number of rings possible with n b
« Reply #12 on: Feb 4th, 2010, 12:08am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: permutation: number of rings possible with n b
« Reply #13 on: Feb 4th, 2010, 1:00am » |
Quote Modify
|
Try that formula with two beads of one color.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print