Finding the number of ways to arrange identical balls in a circle

  • Thread starter Thread starter songoku
  • Start date Start date
songoku
Messages
2,469
Reaction score
382
Homework Statement
Find the number of ways to arrange 2 red balls, 2 blue balls and 1 yellow ball in a circle
Relevant Equations
cyclic permutation = (n - 1)!

permutation with identical objects = ##\frac{n!}{r_{1}! r_{2}! ...}##
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense.

Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities?

Thanks
 
Physics news on Phys.org
I assume that two arrangements are considered equal if they are equal after rotation?

If so, you could start by fixing the position of the yellow ball.
 
songoku said:
##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense.
Why 4 ?
 
And assume balls of the same color are undistinguishable, i.e. , b1b2= b2b1, etc.?
 
They're identical? The answer is one.


🤔 :wink:
 
songoku said:
permutation with identical objects = ##\frac{n!}{r_{1}! r_{2}! ...}##

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense.
Let's take a closer look at your 2 red balls and 2 blue example. The number of combinations for arranging them in a row is 4!/(2!2!)=6. It is easy to list them explicitly:

Group A:
rrbb
rbbr
bbrr
brrb

Group B:
rbrb
brbr

Each group is an equivalence class when we bend the row to form a circle. So the answer for this case is 2 (different arrangements in a circle). Since group A contains 4 members while B has only 2, this explains why simply replacing n! by (n-1)! , as you tried in OP, doesn't work.
 
PeroK said:
I assume that two arrangements are considered equal if they are equal after rotation?
Yes. Let R = red ball and B = blue ball. Arrangement of BBRR in circle will be the same as BRRB

PeroK said:
If so, you could start by fixing the position of the yellow ball.
So, the strategy is to list all the possible arrangements?

BvU said:
Why 4 ?
I was considering another case where there are only 2 red balls and 2 blue balls so n = 4

WWGD said:
And assume balls of the same color are undistinguishable, i.e. , b1b2= b2b1, etc.?
Yes

DaveC426913 said:
They're identical? The answer is one.


🤔 :wink:
I have tried listing several possibilities for the case of 2 red balls, 2 blue balls and 1 yellow ball
1) RRBBY (which will be identical to RBBYR, BBYRR, BYRRB, YRRBB)
2) RYRBB (which will be identical to YRBBR, RBBRY, BBRYR, BRYRB)
3) RYBRB (which will be identical to YBRBR, BRBRY, RBRYB, BRYBR)

I only consider the identical arrangements in clockwise direction (although I am not sure this is the approach I should take)

JimWhoKnew said:
Let's take a closer look at your 2 red balls and 2 blue example. The number of combinations for arranging them in a row is 4!/(2!2!)=6. It is easy to list them explicitly:

Group A:
rrbb
rbbr
bbrr
brrb

Group B:
rbrb
brbr

Each group is an equivalence class when we bend the row to form a circle. So the answer for this case is 2 (different arrangements in a circle). Since group A contains 4 members while B has only 2, this explains why simply replacing n! by (n-1)! , as you tried in OP, doesn't work.
I understand
 
The idea of fixing the yellow ball is that it picks out the set of solutions that cannot be equivalent under rotation. If there were, say, two balls of each red blue and yellow, then you could fix the two yellows in positions 1,2 then 1 3 then 1, 4. Those solutions cannot be equivalent under rotation. Note that the yellow balls in positions 1, 5 is rotationally equivalent to positions 1,3; and positions 1,6 equivalent to 1,2.

Likewise, any other permutation is identified by the spacing between the yellow balls.

Then you arrange the remaining balls in the remaining spaces as many different ways as possible.
 
songoku said:
I tried to combine those 2 formulas but it didn't work.
For the case 1 yellow, 2 red, 2 blue, I get 6 arrangements in a circle, which is the same as (5-1)!/(2!2!1!) . How many do you get?

For any number of balls and colors, if there is a ball whose color is different from all others (like the yellow in OP), then you can use @PeroK's observation in #2 and #8 to show that the number of arrangements in a circle is$$\frac{(n-1)!}{r_1!r_2!\dots} \quad.$$Here, arrangements that differ by clockwise or anti-clockwise rotations are considered the same, but mirrored arrangements are different in the general case: ybrbr is different from yrbrb.

If there are 2 or more balls of each (participating) color, you have to deal with the complexity as in #6 and #8.
 
  • #10
songoku said:
Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities?
You do not need any formula to solve this problem. With two blue balls and two red balls you have two cases BBRR and BRBR.
How many different options do you have when you insert the yellow ball into BBRR?
How many different options do you have when you insert the yellow ball into BRBR?
 
  • #11
songoku said:
So, the strategy is to list all the possible arrangements?
No, the ##(5-1)!## gives you the number of circular permutations for the five balls and the ##\displaystyle{\frac 1 {2!2!} } ## corrects for the identicals.

( expression works for 1 yellow, 3 red, 3 blue: ##\displaystyle{\frac {(7-1)!}{3!3!}}=20## which matches the brute force result :rolleyes: )


songoku said:
I was considering another case where there are only 2 red balls and 2 blue balls so n = 4
Now it's my turn to be puzzled: There are ##3!=6## circular permutations for four balls of different colours. But for this 2 red plus 2 blue case not ##6\over {2!2!}## but ##2##

What am I missing ?

##\ ##
 
  • #12
BvU said:
No, the ##(5-1)!## gives you the number of circular permutations for the five balls and the ##\displaystyle{\frac 1 {2!2!} } ## corrects for the identicals.

( expression works for 1 yellow, 3 red, 3 blue: ##\displaystyle{\frac {(7-1)!}{3!3!}}=20## which matches the brute force result :rolleyes: )



Now it's my turn to be puzzled: There are ##3!=6## circular permutations for four balls of different colours. But for this 2 red plus 2 blue case not ##6\over {2!2!}## but ##2##

What am I missing ?

##\ ##
List them and see what happens when you make two balls the same.
 
  • #13
BvU said:
Now it's my turn to be puzzled: There are ##3!=6## circular permutations for four balls of different colours. But for this 2 red plus 2 blue case not ##6\over {2!2!}## but ##2##

What am I missing ?
Take a look at post #6.

BvU said:
( expression works for 1 yellow, 3 red, 3 blue: ##\displaystyle{\frac {(7-1)!}{3!3!}}=20## which matches the brute force result :rolleyes: )
Take a look at post #9.
 
  • #14
For more complicated problems than this one in the original post the formula is $$ N=\frac1n\sum_{d|gcd(n_1,n_2,...,n_k)}^{}\phi(d)\binom{n/d}{n_1/d,n_2/d,...,n_k/d} $$ where:
## n ## - the number of balls,
## k ## - the number of colors,
## n_i ## - the number of balls of the i-th color,
## gcd(n_1,n_2,...,n_k) ## - the greatest common divisor,
## d ## - the factor of ## gcd(n_1,n_2,...,n_k) ##
## \phi(d) ## - Euler's totient function and $$ \binom{n/d}{n_1/d,n_2/d,...,n_k/d}=\frac{(n/d)!}{(n_1/d)!(n_2/d)!\cdot\cdot\cdot(n_k/d)!} $$.
 
  • #15
How about this: Starting with 5 identical balls, there is a total of 5!=120 arrangements. Now consider the distinction. Then: By rotation, each arrangement corresponds to , or generates 5 permutation, so we divide by 5. In addition, each arrangement, involving 2 red balls is double-counted. Same for 2 blue balls. We end up with ## \frac {5!}{5*2!*2!}=6## balls.
 
Back
Top