Permutation and combination circle (2 Viewers)

[Darrenn001]

How many ways can you arrange 3 identical black beads and 5 identical white beads in a circle. Answer is 7 working out please.

 

[SharkeyBoy]

total number of beads: 8
therefore, if they were all different, it would be: 8!/8 = 7!
with 3 identical black beads and 5 identical white beads, you would do this:
7!/(5!*3!) = 7

 

[braintic]

total number of beads: 8
therefore, if they were all different, it would be: 8!/8 = 7!
with 3 identical black beads and 5 identical white beads, you would do this:
7!/(5!*3!) = 7

I can see that your answer is correct, but could you explain the combinatorial logic. That is, why only one factorial is decremented.

 

[braintic]

bump

 

[Carrotsticks]

bump

It's in a circle, so it would be the usual (n-1)! instead of n!.

 

[braintic]

It's in a circle, so it would be the usual (n-1)! instead of n!.

I'm actually looking for someone who can explain well why the total is reduced by one, but the subgroups are not. I can see it, but I've always found it difficult to explain without hand waving.

 

[obliviousninja]

I'm actually looking for someone who can explain well why the total is reduced by one, but the subgroups are not. I can see it, but I've always found it difficult to explain without hand waving.

Circle can be rotated, no definitive start point in comparison to arranging within a line.

 

[asianese]

The circle can be rotated exactly n ways which accounts for all the repeats. So if there are n seats, you need to do n! but divide by n, so n!/n = n(n-1)!/n = (n-1)!

 

[braintic]

OK, I mustn't have made my point clearly enough.

My students and I understand the need for (n-1)! - that has been explained and easily understood in class.
The question is why the numbers of the subgroups don't need to be modified in the same way.
As I said, I understand it (ie. I can 'see' it), but explaining it is a different matter.
I too am guilty of statements like "The circle can be rotated exactly n ways which accounts for all the repeats." But this is hand-waving. It begs the students to believe you by your authority alone. So the question is: How do you explain to a student who doesn't understand, why one or both of the subgroups are not reduced to 2! and/or 4! ? Because this is a common query.

 

[HSC2014]

^ I'm glad you are aware of things like that (statements without logical reinforcement)

So:
We set aside one bead (either black or white, doesn't matter) to serve as a reference point.
Then there are 7! arrangements for the remaining beads.
However there STILL exists on the circle 3 black and 5 white beads (the bead taken aside before does not magically disappear!), hence the need to divide by 3!.5! to remove duplicity

 

[Carrotsticks]

We reduce the factorial by a degree of 1 to account for rotational invariance (this only needs to be done once).

We have already accounted for that when we did the (n-1)! instead of n!. By reducing the degree of the sub-groups, we are 'doubly compensating' for the rotation, which is unnecessary. So for that reason, we don't reduce them.

When I imagine a perms + combs problem, I imagine a 'checklist', where each box has to be ticked exactly once to get the final answer. Each box is something like "Account for the identical elements" or "Arrange the boys" or "Account for rotations". By reducing the sub-groups too, we are ticking the 'account for rotations' box three times.

 

[braintic]

^ I'm glad you are aware of things like that (statements without logical reinforcement)

So:
We set aside one bead (either black or white, doesn't matter) to serve as a reference point.
Then there are 7! arrangements for the remaining beads.
However there STILL exists on the circle 3 black and 5 white beads (the bead taken aside before does not magically disappear!), hence the need to divide by 3!.5! to remove duplicity

But what about the extreme case - ie. all 8 beads are black.
The method suggest that the answer should be 7!/8!, which of course is rubbish.
Also the method definitely works with 7 blacks and one white, as 7!/7! = 1, which is the expected answer.
What is happening there logically?

 

[HSC2014]

Well, we set aside one bead as a reference point to DISTINGUISH the start/ends of the circle
However if all beads are identical, then pulling aside one does not do anything as a reference point and thus the 'method' breaks down. It is then clear that there is only 1 possible arrangement for the 8 identical beads.
Though, I am having a problem showing this algebraically (if it's possible), as it is just something one would 'see'.

 

[Carrotsticks]

The method highlighted only works (roughly) for the case where we have 2 different colours, where we have approximately ways of arranging (n-k) and n identical elements in a circle.

The reason why I say approximately is because it really does depend on the values of (n-k) and n, because different values result in different rotational symmetries (from which the problem heavily circulates, pardon the pun). The fact that using the formula for your example with the 8 black beads yields 7!/8! (when the actual answer is 1) leads me to believe that the formula I stated above is lower bound approximation.

EDIT: I am 99% sure that it is a lower bound approximation. Bashed out a couple of cases and consistently got a small degree (no more than 1) off the actual answer.

I'm currently trying to figure out why the formula gives the exact answer in the case where we have 3 and 5 beads, yet fails for say 6 and 2 beads.

My gut feeling is telling me that it's something to do with 3 and 5 being co-prime, but will need to explore that idea a bit more.

 

[braintic]

Its good to know that there was actually something behind my inability to see this as obvious.

 

[hit patel]

Since In a circle doesn't matter where a person sits the first person would be able to be distinguished in a position because all places around the circle are considered as one arrangement.

 

[braintic]

Since In a circle doesn't matter where a person sits the first person would be able to be distinguished in a position because all places around the circle are considered as one arrangement.

I don't think you are addressing the issue of the identical elements, which is the problem here. To be honest, its not clear to me what you are saying.

 

[seanieg89]

The method highlighted only works (roughly) for the case where we have 2 different colours, where we have approximately ways of arranging (n-k) and n identical elements in a circle.

The reason why I say approximately is because it really does depend on the values of (n-k) and n, because different values result in different rotational symmetries (from which the problem heavily circulates, pardon the pun). The fact that using the formula for your example with the 8 black beads yields 7!/8! (when the actual answer is 1) leads me to believe that the formula I stated above is lower bound approximation.

EDIT: I am 99% sure that it is a lower bound approximation. Bashed out a couple of cases and consistently got a small degree (no more than 1) off the actual answer.

I'm currently trying to figure out why the formula gives the exact answer in the case where we have 3 and 5 beads, yet fails for say 6 and 2 beads.

My gut feeling is telling me that it's something to do with 3 and 5 being co-prime, but will need to explore that idea a bit more.

I will try to explain what's going on here. (Apologies if it is not entirely coherent, I am not particularly good at combinatorics.)

One way of thinking about the division when counting things like circular arrangements is that we are counting groups of objects that are in some sense "the same".

Eg/ The circle arranged by writing ABC clockwise from the top is in some sense the same as a circle with BCA written clockwise from the top.

In mathematical parlance, the strings {ABC,BCA,CAB} form what is called an equivalence class, with the equivalence relation in question being rotational symmetry.

In the simplest of counting problems that involve equivalence classes, all classes will be of the same size. This reduces the problem to division.

Eg/ How many ways can Alfredo, Beethoven and Charlemagne be arranged at a circular table?

We can form 3! = 6 strings out of the letters A,B,C. But we view a rotation of a given arrangement as the same arrangement (note that this is a convention, much of what makes combinatorics tricky at first is ambiguous wording!), and so we really want to count equivalence classes modulo rotational symmetry. As we saw in the previous example, (and jumbling the order of A,B,C does not affect this argument) each of these equivalence classes has size 3. Hence there are 6/3=2 arrangements. This of course generalises to give us that there are (n-1)! ways of arranging n people around a table, something I hope you all knew already.

Alas we cannot in general hope that equivalence classes all have the same size, and this is the issue here.

Suppose we have n meals, k of them meat, n-k vegetarian (0 < k < n), and we wish to count all possible ways to prepare a circular n-place dining table. It is straightforward that we can form n!/(k!(n-k)!) strings out of k Ms and n-k Vs. How many strings correspond to each arrangement? By rotating the string by one character, we obtain a (usually!!!) different string that gives you the same dinner table.

Eg/ MMV,MVM,VMM all correspond to the same dinner table.

If rotation of such a string gave you something different every time until you got a full rotation (rotation of VMM brings us back around to MMV for example), then each dinner table arrangements corresponds to n such strings. (choose one corresponding string arbitrarily and rotate it n-1 times to give you n different strings in total, all corresponding to the same table arrangement.) As we know the total number of strings we need only divide by n to finish the problem.


Unfortunately, it is the "usually" that rears its ugly head here. If we rotate the string MVMV only twice, we will get the same string again. In the language of equivalence classes, there are only two strings in the equivalence class corresponding to the alternating table with four meals. Compare this to the arrangement where vegetarian meals are adjacent, here we have four objects in the equivalence class {MMVV,MVVM,VVMM,VMMV}.

This means that the problem of arranging two meat meals and two vegetarian meals at a circular table is no longer a matter of divison by 4. (This point of view should also make it clear why such an erroneous calculation is an underestimate).

tl;dr make sure you know why you do things like the standard division in counting circular arrangements so you know when you have to get your hands dirty with some manual counting.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Part 2: Why the naive approach works in this instance (k=3,n=8)

It turns out that this phenomenon of symmetry under partial rotations is related to something called modular arithmetic.

Claim: If k is coprime to n in the meat/veg problem, then all equivalence classes have the same size, and our result is (n-1)!/(k!(n-k)!)

By writing m(0),m(1),...,m(k-1) to denote the number of veg meals between consecutive meats, the issue of invariance under partial rotation can only arise if we have m(j)=m(j+l) for all j and for some fixed 0 < l < k (sums taken modulo k).

If this is the case and l is coprime to k, then l is a multiplicative generator of Z/kZ and we get that each m is equal. This cannot occur if k and n are coprime.

Let us now suppose that l and k have gcd = g > 1. Then l generates the subgroup gZ/kZ, and we get that we can split the ms up into g subsets each of size k/g. If S is any one of these subsets, then the sum of m(j) for j in S must then be divisible by k/g.

Hence k/g divides the sum of m(j) over j=0,1,...,k-1, which is n-k (remember what these ms are!)

Hence k/g divides n. But since g is a proper divisor of k and k is coprime to n, this is impossible.


NB: I proved the above for a table rather than a bracelet to avoid dealing with the additional "flip" symmetry. Something similar can probably be proved for bracelets.

 

[Carrotsticks]

Cheers for the explanation Sean. My gut was telling me there was a relationship between rotational symmetry, divisibility and the lower bound, but I couldn't really pinpoint what it was exactly.

Now it's all connected =)

 

[seanieg89]

Of course there are several unanswered questions like how things change when we consider bracelets instead of tables, and how things change when beads are of > 2 different colours that might be fun to think about.