# Permutation with repetitions / non-distinguishable objects basics

The question was:

From the letters in MAGOOSH, we are going to make three-letter "words." Any set of three letters counts as a word, and different arrangements of the same three letters (such as "MAG" and "AGM") count as different words. How many different three-letter words can be made from the seven letters in MAGOOSH?

From my permutation understanding, ans should be: 7P3/2! = 105 But the answer is: 6P3+(3*5)=135 (I understand how it happens!)

But my question is, why indistinguishable object's permutation formula = nPr/K! could not be applied here.(Such as MOM = 3P3/2!=3!/2!=3)

So, I am not sure why "7P3/2!" - is not a valid answer as there is 2 "O"s. What am I missing here? Any explanations?

• The symmetry (swap the two $O's$ ) only applies to those words with two $O's$. You have to separate those cases from the others. – lulu Aug 14 '16 at 21:34
• I understood you there. But my question was, why indistinguishable objects permutation formula = nPr/K! could not be applied here.(Such as MOM = 3!/2!) – neo-nant Aug 15 '16 at 3:56
• Not following you. In the example you give, $MOM$, there are two $M's$ so the symmetry (swap $M's$) applies to every permutation. In the posted problem you have triples like $MOO$ to which the symmetry applies and triples like $MAG$ to which it does not....hence it is not the case that every permutation is "counted twice". – lulu Aug 15 '16 at 10:12

## 3 Answers

To clarify the problem with $7P3$:

The reason one might think that dividing by $2$ is a good idea is that there is a symmetry, swapping the two $O's$ That is perfectly correct but for words like $MAG$ the symmetry has no bearing.

How can we use the symmetry to count correctly? Let's start by numbering the $O's$, so we have $O_1,O_2$. Now of course the answer is exactly $7P3=7\times6\times5=210$. These split into two types: those containing neither one of the $O's$ and the rest. The first type contains $5P3=5\times4\times3=60$ words. The second type contains all those words with at least one $O$, and it has $210-60=150$ elements. Now, if we identify $O_1$ and $O_2$ we see that we have counted every word of the second type twice. For example $MOG$ is counted as $MO_1G$ and $MO_2G$ while $MOO$ is counted as $MO_1O_2$ and $MO_2O_1$. Thus, to solve your problem, we need to divide that group by $2$. Thus the final answer is $$60+\frac {210-60}2=60+75=135$$ as desired.

• Thank you! I appreciate your effort! – neo-nant Aug 15 '16 at 17:55

Alternative counting. First consider the two Os as different letters. In this way there are $7\cdot 6\cdot 5=210$ three-letter words. Now take away those with at least one O because they were counted twice. Their number is $3\cdot 5=15$ (those with two Os) plus $3\cdot 5\cdot 4 =60$ (those with one O).

Hence the total number is $210-15-60=135$.

• I understand these approaches. But my question was, why indistinguishable object's permutation formula = nPr/K! could not be applied here.(Such as MOM = 3P3/2!=3!/2!=3) – neo-nant Aug 15 '16 at 3:57
• @neo-nant Actually, I am not very familiar with this formula $nPr/k!$ when $r\not=k$. What do $n$, $r$, and $k$ mean? Where did you read it? – Robert Z Aug 15 '16 at 6:05

What you are missing is that while there are $2 O's$, division by $2!$ would be valid only for $3$ letter words actually using both the $O's$.

But there will be many $3$ letter words with just one $O$ or no $O$