Permutations with identical objects

Question

So, in my secondary Algebra II class we have gotten to the unit on probability and counting and as part of that we are looking at permutations. We have looked at permutations of $n$ objects, permutations of $n$ objects taking $r$ at a time, and permutations with identical objects. The first two types of permutations my students understand pretty well, both intuitively and the formulas. We talked about these in terms of "slots and options", i.e. "If you have three slots and ten objects, then you have 10 options for the first slot, 9 options for the second slot, and 8 options for the third slot and by the fundamental counting principle we multiply these to get the total number of permutations." I was actually able to have the students get up and physically perform these permutations by standing in different orders in front of the class and this really seemed to cement in these first two types of permutations.

The problem arose when we got to the idea of permutations with identical objects. I tried to explain it as "the total number of permutations for the objects ($n!$) and then divide out the number of repeats ($r_1!r_2!...$)" A few of my students were good with this but for the most part, the class was not able to see the connection between the situations we were looking at and the formula and ended up very confused. Does anyone have a better, more intuitive way to explain permutations with identical objects? or perhaps a demonstration, similar to what I did with having my students line up in front of the class, that could make this concept clear?

Answer 1

Here are three ideas:

Numbered letters

The classic problem of this type is "How many ways are there to arrange the letters in MISSISSIPPI?" Our previous knowledge of permutations only applies to ones where everything is different, so label the letters so we can tell them apart:$M_1I_1S_1S_2I_2S_3S_4I_3P_1P_2I_4$.

Now there will be $11!$ arrangements, but if you took off the labels you'd find you couldn't tell them apart so you need to take that into account. Actually listing several arrangements and removing the labels on just one type of letter (say the S's) will make this clearer.

Masked students

You have already had the students line up and rearrange themselves, so reuse the same idea.

This time give the students masks so that there are several students with each mask.

Rearrange the students, and then get all the students with a particular mask to rearrange themselves. The class will see that the arrangement of masks doesn't change. So we will have counted all those permutations too many times.

Really this is just the same as "numbered letters" but more interactive and cute.

Choose where things go

There is a completely different way to think about this situation using combinations instead of permutations.

To construct an arrangement of MISSISSIPPI, you can think of the final arrangement as having 11 spots: ()()()()()()()()()()(). We have to choose which of these spots is M; then out of the 10 remaining spots, we have to choose which two of them are P; then out of the remaining 8 spots, we have to choose which four of them are I; and all the rest are S's.

So the number of arrangements is: $$ {{11}\choose{1}} {{10}\choose{2}}{{8}\choose{4}}{{4}\choose{4}}. $$ If you expand this out a whole lot of stuff will cancel and come to the formula you said.

I quite like showing students this at some point because it does highlight that there is often more than one way to do things. It also reinforces the idea that if you can have a story for how to construct the arrangement, then you can count how many ways each step of the story happens.

Answer 2

Use colors!

Variant 1

Use different objects like a red apple, a green apple and a pear. (Both apples should look the same except for their color. Let the students permute these objects. They count 6 different permutations. Then apply a color filter, e.g. transform into grayscale. Now, both apples look the same. In your originally 6 different permutations, there are now 3 pairs of identical permutations, leaving 3 different permutations.

Variant 2

Use identical objects like three apples and a pear, all in black-white. (The apples should look the same.) Let each of the students permute these objects. Everyone'll find 4 different permutations (the place of the peach being the differing aspect) and be pretty certain that these are all. Now let everybody color their food using red, green and yellow for the apples and a mix (or whatever) for the pear. Every one will still have 4 permutations on his sheet of paper, but after exchanging them, they'll have more, although everyone hat the same set of 4 original permutations.

Background

The real problem is not the counting or the fundamental counting principle. The real problem is the students' idea of identiy, equality and difference. Although all apples look the same, the students think they know all apples are different. But what's the difference? What are sufficient conditions to say, two anything are equal or identical?

• If all of their atoms are identical
• If all properties are equal
• If all relevant properties are equal
• if all measurable properties are equal

After having discussed this, point them to the fact, that non of these conditions are mathematical or mathematically usable. The first one is physical. The apples on the papers aren't even real apples. They are ink on paper. What makes them apples is our imagination. The second one is impractical, as one can always invent a new property, like name (apple "Harry", apple "Sandra" and apple "Nr. 5".). The third one is philosophical/metaphysical. And the last one is scientific.

Identity, equality and difference in mathematical terms are formal definitions. We, the mathematicians say, that these apples are equal or different. It doesn't matter, what. It does matter, what's the result of it.