Is this a Permutation Question or a Combination Question?
Today I had my middle schoolers working on some of the new MATHCOUNTS Club problems. One of them was the following:
A bracelet is made by stringing together four beads. Each bead is either red or green. How many different color patterns are possible for the bracelet, where patterns are considered the same if turning one will produce the other, as shown here?
Since we had just recently been working on Permutations and Combinations (and one day I may even get around to finishing the blog post I’ve been planning on that topic), one boy asked, “Is this a permutation question or a combination question?”
It was a question that had never occurred to me before, and I thought it was a great question. After thinking about that for a moment, I replied that it was sort of a permutation question, since the order of the beads does matter, but that since the permutations were arranged on circles, so that there was no fixed start or end of the sequence, it wouldn’t yield to a basic permutation approach (or for that matter a basic combination approach).
I suggested that in this case, “Make and Organized List” was probably the most fruitful strategy. But for a larger bracelet, that would break down, of course. Is there a good way to solve this problem for, say, a bracelet with 10 beads, each of which may be red or blue? It seems like you would need to still consider casework for the number of red (or blue) beads, and then figure permutations, adjusting for overcounting due to both identical items and rotational symmetry.
Ramblings of a Math Mom 
Permutation question, with extra number-theoretical goodness.
You’re looking for permutations, with an added equivalence relation (which makes some permutations equivalent).
The equivalence relation has the property that if x and y are equivalent, then x and y have the same number of r’s and g’s. Thinking algebraically, if it wasn’t for the cyclic permutation, you’d have:
(r+g)^n = C(n,0) r^n + C(n,1) r^(n-1)g + … + C(n,i) r^(n-i)g^i + … + C(n,n)g^n
(You can recover the actual number by setting r=g=1.)
Applying the equivalence relation can essentially be understood as dividing each coefficient in that expansion by the number of possible symmetries. It’ll look something like this:
(r+g)^n = C(n,0) r^n + …+ C(n,i) / f(n,i) r^(n-i)g^i + … + C(n,n)g^n
for some function f.
In general, it’s going to depend on the prime expansion of n and i; I’m guessing you’re going to find a totient function (or something very much like it) somewhere in there.
One more thing, while I think about it.
One of the reasons why you might have been asking the question is that “combinations” really are just “permutations” divided by the number of symmetries. “Bracelets” are “permutations” divided by fewer symmetries.
Think of choosing a k-permutation from n elements. There are n possible choices for the first element in the permutation, n-1 for the second and so forth up to (n-k). So the number of ways to choose such a permutation is:
n! / (n-k)!
To choose a combination, you simply divide this by the order of the symmetry. In this case, each permutation is “equivalent” to k! of them including itself. So simply divide by k!:
n! / (k! (n-k)!)
A lot of combinatorics problems lie between these two extremes. At one end, you have “no permutations are equivalent”, and at the other end, you have “all of them are”.
Yes, Pseudonym, as I’ve been writing about in the Permutations & Combinations post I never manage to finish, I teach the kids combinations the way you described. I don’t like to have them memorize formulas; I want them to know logically what they are doing. So I have them think about figuring out the permutations first, then dividing by how many times they counted each answer (which is itself another mini-permutation question).
I like your point about the bracelets being just a limited set of symmetries. That’s a great way of thinking of it.
This problem, even with the symmetry is not really a k-permutation anyhow, or at least it is a more complicated one due to the additional issue of identical items. If the beads were in a row, there would be 2^k possibilities since there are two choices for the color of each bead. Then you need to figure out which permutations are symmetric under rotation, which is of course the challenge!
Thanks for your comments.
I teach combinations that way, too: Find the total number of possible arrangements (permutations), then divide by the number of ways any one set can be rearranged.
If you were given any certain number of different beads and told to make a bracelet, you would be dealing with permutations, since the order that you put the beads in matter. 4 beads can make 24 permutations, for instance. But once the bracelet is tied in a circle, if you make the knot small enough to slip through the beads, then you can’t tell which bead was the first one — so you would have to divide by the number of beads in the bracelet, to account for rotations. That is, design ABCD would be equivalent to BCDA or CDAB or DABC, for a 4-bead bracelet. And then, you would also have to divide by 2, to account for the fact that a bracelet can be flipped over (a mirror-image of the bead pattern is equivalent to the original). So, if I am counting correctly, a set of 4 different beads can make only 3 bracelet designs.
BUT as you said, this is not a permutation bracelet, because we are not given 4 different beads. We have an unlimited supply of two sets of identical beads to make a 4-bead bracelet. I don’t know any short-cut for this, except to make an organized list and check for rotations and mirror patterns. When I made the list (2^4 = 16 possibilities), I found that each solid-color arrangement was counted only once. The two 1&3 bead arrangements were each counted four times, and the two 2&2 bead arrangements were each counted 3 times.
But the big question is, how can we predict the overcounting in advance? So that if we were going to make a 10-bead bracelet, we could figure out how many arrangements there would be without writing out all 1,024 strings and sorting them…
Denise, if I were to do the 10-bead bracelet problem, I think I would use a constructive approach rather than an overcounting approach.
With 0 red (all blue) there is only 1 design.
With 1 red, there is also only 1 design.
With 2 reds, we have:
– 1 design where the 2 reds touch
– 1 design where the 2 reds have 1 blue (or equivalently 7 blues) between them.
– 1 design where the 2 reds have 2 blues (or 6 blues) between them
– 1 design where the 2 reds have 3 blues (or 5 blues) between them
– 1 design where the 2 reds have 4 blues between them
So that’s 5 distinct designs for 2 reds
of course, with more reds than that, the casework starts getting uglier, but then when we get to 5 reds, we’re done, because the 6 reds case is going to be the same as the 4 reds case (but with colors reversed). And this doesn’t give us an efficient method for doing even larger bracelets. But I think a key point to keep in mind with combinatorics questions is that sometimes you really do have to do the casework. I think this may be one of those cases.
With 3 reds, you could have gap sizes of
(0, 0, 7), (0, 1, 6), (0, 2, 5), (0, 3, 4),
(1, 1, 5), (1, 2, 4), (1, 3, 3), (2, 2, 3),
(3, 3, 1)
So there are 9 of those. In this case the order of the gaps doesn’t matter because there are only 3 gaps, so each gap is “next to” the other two gaps. This is sort-of related to the question of partitions of a number, but I don’t know if there is a formula for partitions of a certain size (i.e. we need to break 7 up into at most 3 chunks). I’d claim that what I did above is easier than drawing the C(10,3) = 120 bracelets with 3 reds and trying to sort them into equivalence classes.
With 4 reds, now the order of the gaps matters somewhat too. Hmm, maybe it’s time to start leaving this as an exercise for the reader. 😉 I mean after all, I’ve done 4 out of the 6 necessary cases, right? 😉 C(10,4) is 210, so I still feel like constructing is better than sorting, but perhaps it’s just too early for such a thing…
“This is sort-of related to the question of partitions of a number, but I don’t know if there is a formula for partitions of a certain size (i.e. we need to break 7 up into at most 3 chunks).”
I think that to break 7 into at most 3 chunks would be C(9,2). You have 7 slots for beads and 2 slots for dividers. Example:
(first color) ^ (second color) ^ (third color)
_ _ ^ _ _ ^ _ _ _
You just have to find out how many different places the dividers can go. But connecting the ends to make it into a bracelet will make some of those designs equivalent.
Denise, I think C(9,2) is too many because it repeats combinations of chunk sizes. It would consider (2,2,3) as different from (2,3,2).
I guess that is what you were saying about some of them being equivalent under rotation.
Partitions is closer (I think) because order doesn’t matter, but it would include things like (1,1,1,1,1,1,1) which doesn’t work here.
Oh, I was still thinking of different-colored beads, in which case (2,2,3) would be different from (2,3,2). But you are right — if all we are doing is sorting same-color beads into different piles, these are identical. Hmm. If we just want chunk sizes, perhaps we would divide by 3! to cancel out the overcounting?
What I meant about rotations was that, if we tried to apply this to our bracelet by alternating two colors and inserting dividers, we would still have to go through and watch for things like:
(2,2,3) matching (1,2,5)
And, of course, we would still have to go through a whole list of possible divisions. We could have no dividers (all one color) or one divider, or two…up to a divider between every bead.
I think I’ll stick to the simpler problems for now. Maybe some day I’ll buy the AoPS book on combinatorics and work my way up to the tough ones.
This was for 2 colors of beads, but I was counting the sizes of the gaps between the reds (or the blues of course).
I do have the AoPS Intro to Combinatorics book, and actually did look up whether they cover problems like this, but they don’t seem to. They cover arranging things around a circle, but only where they are all different.
There is a beautiful theorem of group theory which enables you to solve problems like these (i.e. counting problems which involve symmetry transformations) and it is called Burnside’s Lemma. Check it out on Wikipedia for a quick summary and the similar application of counting the number of ways to paint the faces of a cube with 3 colors.
What happens is that you approach the problem from the point of view of the symmetries, and for each symmetry of the necklace (e.g. rotation clockwise by one bead, e.g. flipping across the horizontal axis, etc.), you count the NUMBER of colorings which are fixed by the symmetry. The sum of these, over all the symmetries, divided by the number of symmetries, is exactly the number of “essentially different” colorings you are trying to count. I apologize for being a bit vague, but to keep the comment short, the results for the necklace with 2 colors and 4 beads is
(16+2+2+4+8+8+4+4)/8 = 6. With 2 colors and 10 beads you’d get
( 1024(1) + 2(4) +4(4) +32(1) + 32(5) +64(5) )/20 = 78.
In the latter example, I combined the symmetries of the same type instead of writing out a sum of twenty numbers. If you have an abstract algebra book which covers basic group theory, check the index for Burnside’s Lemma or “group actions” for more information. I don’t know of any general way to solve these sorts of problems without using group theory or exhaustively counting cases, since the “overcounting” you get by ignoring the symmetries does not happen “uniformly”, so, for example, there’s no way to simply divide the 16 (colorings of the four beads) by some fixed factor to get the number 6 (of “different” necklaces).
Hi, Ned, thanks for the help and the pointer to the Lemma we needed!
If you have time, could you explain somewhat how you got the numbers you added in the 4 bead case? I’m not following what you mean by “fixed by the symmetry”. I’m also not clear on why there are 8 symmetries for the 4-bead necklace. There are 4 rotations, but do they each need to be reflected too? Don’t the reflections turn out to be the same as some of the rotations?
I had embarked on a “solve a simpler problem and find a pattern” approach to solving the problem, and have (I believe) solutions for 2 colors and 3,4,5,6,and 7-bead necklaces (after which it gets very, very messy to count by hand). But I’d love to run through the Burnside algorithm for those numbers and see if I got them right.
In the meantime, I’ll head on over to Wikipedia and see what I can learn about Burnside’s Lemma!
Thanks!
We label the four beads from the top clockwise. Let’s look at one of the 8 symmetries of the necklace, namely “rotation clockwise by 180 degrees (i.e by 2 beads)”. Now the following colorings are fixed by this symmetry: RRRR, BBBB, RBRB, BRBR, since in each of these cases, applying the rotation to the coloring yields the same coloring (try it). On the other hand, the other 12 colorings are not fixed our example symmetry, e.g RRRB is transformed to RBRR, RRBB is transformed to BBRR, etc. Here comes a list of all eight symmetries and the colorings which are fixed by them.
SYMMETRY FIXED COLORINGS how many
(identity) all colorings xyzw 16
rot. by 90 RRRR, BBBB (i.e. xxxx) 2
rot by 270 RRRR, BBBB (i.e. xxxx) 2
rot. by 180 xyxy 4
flip on vert. axis xyzy 8
flip on horz. axis xyxz 8
flip on diag / xxyy 4
flip on diag \ xyyx 4
TOTAL 48
The number of different necklaces is 48/8 = 6, these are RRRR, BBBB, RRBB, RBRB, RRRB, and BBBR.
You can see that there are five types of symmetries here : identity, (2) rotations by 90, rotation by 180, (2) vertex flips, (2) edge flips. In the Wikipedia cube example and the 10 bead example, this kind of repetition is used to reduce the actual number of different symmetries you need to look at.
For the four bead necklace with two colors, yes you only get the same 6 necklaces even if you don’t allow reflections (it will be the first four rows of the table 16 + 2 + 2 + 4 = 24 divided by 4 equals 6) but for necklaces with either more beads or more colors, then allowing reflections ( as I did here) will reduce the number of different necklaces. There are two distinct problems for each pair (N,k) with N beads and k colors, one which allows only rotations to be considered as the same necklace and the other which also allows flips. For N=4, k =2, the two counts come out the same.
Have fun!….Ned
Thanks again, Ned! When I was reading the page on Wikipedia I was wondering if it was the flips that you were counting. Thanks for clarifying, and also for clarifying about the different problems you can have (with our without counting flips as different necklaces).
there are 8 students appearing in examination,of which 3 have to ppear in maths paper nad remaining 5 in different subjects,in how many ways can made to sit in a row if the candidates of mats cant sit next to each other.
This Problem is from cyclic permutation .
Thanks Hemant; that is what Pseudonym said above as well. 🙂
Thanks to Ned! I have been trying to solve this problem for quite a while and it is now done using Burnside’s Lemma.
However, I think there is a slight mistake when Ned explains the number of symmetries through reflections. It should be 4 (not 8) for reflection through horizontal/vertical axis and 8 (not 4) for flip through diagonals.
In the case of horizontal/vertical axis, there will be two beads on each side. The colour(s) and arrangement of the beads on one side need to be identical to those on the other side (for the whole thing to remain identical after reflection). So, with 2 beads and 2 colours – 2^2=4 possible ways when reflected through any axis.
For flip through any diagonal, there is one bead on each side. To remain identical after reflection, they have to be the same colour. In this case, they need to both red or both green. So, 2 possible combination. But the two beads on the ends of a diagonal can be arranged in 2^2 = 4 ways. Thus for each diagonal there are 2*4=8 symmetries.
One more thing….
Burnside’s Lemma considers symmetries through both rotations and reflections. If you only want to find ‘rotationally distinct’ ones i.e., ones that cannot be obtained by rotating the other, then only calculate symmetries for the rotations, add them up and divide the sum with the number of rotations.
Let’s see the example of 6 six beads and 2 colours. Applying Burnside’s Lemma (considering both rotation and reflection), 13 distinct arrangements (or permutations). If we only consider them to be rotationally distinct then there are 14. These are:
RRRRRR
RRRRRB
RRRRBB
RRRBRB
RRRBBB
RRBRRB
RRBRBB
RRBBRB
RRBBBB
RBRBRB
RBRBBB
RBBRBB
RBBBBB
BBBBBB
No matter how you rotate these permutations, they can never be same with another. It may make more sense if you draw them on paper. However, reflecting RRBRBB will give RRBBRB. In case of a necklace or bracelet, imagine looking at RRBRBB from behind (or flip it) and you will see RRBBRB. That’s why we get 13 (one less) permutations considering both rotation and reflection. This number is same for 4 beads.
Considering both rotation and reflection, there are 30 and 78 permutations for 8 and 10 beads respectively (2 colours). But if only rotation is considered, for 4,5,6,7,8,9,10,11 and 12 beads (for 2 colours) there are 8, 14, 20, 36, 60, 108, 186 and 352 respectively. Hope this makes sense :-).
Hi there Abu. I was thinking of the beads set up as in the picture in the post, with the beads at the top, bottom left , right so that e.g. the flip on vertical axis will interchange left-right and leave top and bottom ones fixed, so that there are eight fixed colorings. I’m guessing that you are seeing the four beads as corner of a flat square, in which case the roles of the vert-horz flips versus the diag flips will be “flipped” (so to speak) from the visualization I had in mind.
Yes Burnside’s Lemma is very powerful. For example, having done all these cases for two colors, generalizing to 3, 4, or even n colors (in terms of n) is quite easy, because you can see that the only role played the “2” in all your examples is as a base for a bunch of exponentials 2, 4, 8, 16, etc. When generalizing to n colors, it’s the same except replace the 2 by “n”. That’s all there is to it! The harder part is counting and classifying the symmetries, which you’ve already done in the k=2 colors case. It’s really cool!
drats, I forgot which parameter is the number of colors, n or k. sorry about that. regardless, working with an arbitrary number of colors is surprisingly easy…. Ned