Finding the number of ways to arrange identical balls in a circle (3 different colors)

[songoku]

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

 

[PeroK]

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.

 

[BvU]

$\frac{(4-1)!}{2!2!}=\frac{3}{2}$ which does not make sense.

Why 4 ?

 

[WWGD]

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

 

[DaveC426913]

They're identical? The answer is one.

 

[JimWhoKnew]

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.

 

[songoku]

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

If so, you could start by fixing the position of the yellow ball.

So, the strategy is to list all the possible arrangements?

Why 4 ?

I was considering another case where there are only 2 red balls and 2 blue balls so n = 4

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

Yes

They're identical? The answer is one.

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)

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

 

[PeroK]

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.

 

[JimWhoKnew]

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.

 

[Gavran]

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?

 

[BvU]

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 )

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 ?

$\$

 

[PeroK]

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 )



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.

 

[JimWhoKnew]

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.

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

Take a look at post #9.

 

[Gavran]

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)!} $$.

 

[WWGD]

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.

Edit: Like the case of the arrangements of 'Mississippi' , but with 11 rotations instead of 5 here.

 

[songoku]

I understand. Thank you very much for all the help and explanation PeroK, BvU, WWGD, DaveC426913, JimWhoKnew, Gavran

 

[haruspex]

It isn't clear to me whether reflections are considered to be the same, e.g. is YRRBB the same as YBBRR? If so, there are only four.

 

[Gavran]

It isn't clear to me whether reflections are considered to be the same, e.g. is YRRBB the same as YBBRR? If so, there are only four.

Only rotations are considered to be the same.