# Why Divide in Permutations of Indistinguishable Objects?

• Nov 11th 2012, 06:16 PM
samwill
Why Divide in Permutations of Indistinguishable Objects?
I was explaining Combinatorial Analysis to a friend who had never had it, and when I got to Permutations of Indistinguishable Objects and told him the formula for it, he asked "Why do you divide?"

I thought about it for a second, and realized that when I was taught this, I was really essentially told "You have to get rid of the extras, and you do that by dividing" and I accepted it. I told him that, and he accepted it, but it's bugging me now. How was this conclusion reached? Is there some kind of proof somewhere that shows why this is true?
• Nov 11th 2012, 07:14 PM
Plato
Re: Why Divide in Permutations of Indistinguishable Objects?
Quote:

Originally Posted by samwill
I was explaining Combinatorial Analysis to a friend who had never had it, and when I got to Permutations of Indistinguishable Objects and told him the formula for it, he asked "Why do you divide?"

Think about the string $ABBCCCDDDD$.
Asked about rearranging that string we have no way of knowing if $ABCDBCDCDDD$ is different from $ABCDBCDCDDD$.
However, if we add subscripts $A_1B_1C_1D_1B_2C_2D_2C_3D_3D_4$ then $A_1B_2C_2D_1B_1C_1D_2C_3D_4D_3$ it is clear that those strings are district. So divide to end duplication.
• Nov 14th 2012, 10:47 AM
samwill
Re: Why Divide in Permutations of Indistinguishable Objects?
Well yes, I know the *reason* for dividing, I wanted to know how whoever came to the conclusion that dividing was necessary got to that conclusion....Is a formal proof too high level for these forums? (I'm a third-year Computer Science major who has gone through several proof-based classes, and also new to this forum so I don't know who frequents it)
• Nov 14th 2012, 11:13 AM
Plato
Re: Why Divide in Permutations of Indistinguishable Objects?
Quote:

Originally Posted by samwill
Well yes, I know the *reason* for dividing, I wanted to know how whoever came to the conclusion that dividing was necessary got to that conclusion....Is a formal proof too high level for these forums?

I have no idea what you mean by a formal proof.
It can take several hundred pages to prove $1+1=2.$

If you "know the *reason* for dividing" then you know the proof of why it is necessary to divide. We rid ourselves of an over-count.

The string $001122$ can be arranged in $\frac{6!}{(2!)^3}$ ways.
• Nov 14th 2012, 12:10 PM
HallsofIvy
Re: Why Divide in Permutations of Indistinguishable Objects?
Is this, perhaps, a language problem? In English, at least, answer to "Why ...." will typically be "The reason is ...". So it makes no sense to say "Yes, I know the *reason*, but why?"
• Nov 14th 2012, 04:45 PM
samwill
Re: Why Divide in Permutations of Indistinguishable Objects?
It's definitely not a language problem, I'm a native English speaker...I guess I meant not "why do you divide?" in the sense that the answer is "to remove over counting" (which I clearly knew since I said that in my original post), I meant "why does dividing work?" But either way, I didn't say "Yes, I know the *reason*, but why?" I said "Yes, I know the *reason*, but how was that conclusion arrived at?"

and as for what I mean by a formal proof, I mean something like this proof of the binomial theorem formula
• Nov 14th 2012, 06:03 PM
Plato
Re: Why Divide in Permutations of Indistinguishable Objects?
Quote:

Originally Posted by samwill
It's definitely not a language problem, I'm a native English speaker...I guess I meant not "why do you divide?" in the sense that the answer is "to remove over counting" (which I clearly knew since I said that in my original post), I meant "why does dividing work?" But either way, I didn't say "Yes, I know the *reason*, but why?" I said "Yes, I know the *reason*, but how was that conclusion arrived at?"
and as for what I mean by a formal proof, I mean something like this proof of the binomial theorem formula

@samwill, I hope you are not just another troll.
We already have Hartlw as a troll. He/she has no idea about mathematical concepts. Do you? From your posts, I rather doubt that you do.
• Nov 14th 2012, 06:09 PM
samwill
Re: Why Divide in Permutations of Indistinguishable Objects?
I promise I'm not, I hoped showing an example of what I want would help, but I guess I'm just not very good at explaining what I mean. I guess just forget it, I'll look up the office hours for the professor I had for probability and go ask him instead.
• Nov 14th 2012, 06:37 PM
Plato
Re: Why Divide in Permutations of Indistinguishable Objects?
Quote:

Originally Posted by samwill
I promise I'm not, I hoped showing an example of what I want would help, but I guess I'm just not very good at explaining what I mean. I guess just forget it, I'll look up the office hours for the professor I had for probability and go ask him instead.

Well then look at an induction argument for this.
How different ways can we arrange the string $AB~?$

How different ways can we arrange the string $AAB~?$

How different ways can we arrange the string $AAAB~?$.

Once you get that, go for How different ways can we arrange the string $AABB~?$

Then try to generalize.
• Nov 29th 2012, 07:03 PM
xylif
Re: Why Divide in Permutations of Indistinguishable Objects?
Say we have n objects, k of which are indistinguishable. Let ni, i=1,2,3,...,k, be the number of indistinguishable objects of type i.

Let us now consider how many ways we can place each group of type i.

(1) How many ways can we put n1 indistinguishable objects into n positions? $C(n,n_1)=\frac{n!}{(n-n_1)!}\cdot \frac{1}{n_1!}$

Since n1 spots are now occupied, there remain n-n1 spots to place n2 indistinguishable objects.

(2) How many ways can we put n2 indistinguishable objects into n-n1 positions? $C(n-n_1, n_2)=\frac{(n-n_1)!}{(n-(n_1+n_2))!}\cdot \frac{1}{n_2!}$.

.
.
.
We continue this process for all k objects.
.
.

(k) How many ways can we put nk indistinguishable objects into n-(n1+n2+...+nk-1) positions?
$C(n-(n_1+n_2+...+n_{k-1}),n_k)=\frac{[n-(n_1+n_2+...+n_{k-1})]!}{[n-(n_1+n_2+...+n_{k-1}+n_k)]!}\cdot \frac{1}{n_k!}$

Now, we take the ways we can place these groups, the results of (1), (2), ..., (k), and multiply them (because of the Multiplication Rule).

$C(n,n_1) \cdot C(n-n_1, n_2) \cdots C(n-(n_1+n_2+...+n_{k-1}),n_k)$

$\frac{n!}{(n-n_1)!}\cdot \frac{1}{n_1!} \cdot \frac{(n-n_1)!}{(n-(n_1+n_2))!}\cdot \frac{1}{n_2!} \cdots \frac{[n-(n_1+n_2+...+n_{k-1})]!}{[n-(n_1+n_2+...+n_{k-1}+n_k)]!}\cdot \frac{1}{n_k!}$

Notice that $\sum_{i=1}^k n_i = n$ and that 0!=1. Then all the nasty stuff cancels and you are left with:

$\frac{n!}{n_1! \cdot n_2! \cdot \cdots \cdot n_k!}$

If you consider MISSISSIPPI, then

n=11
k=4
n1="M"=1
n2="I"=4
n3="S"=4
n4="P"=2

And n = n1+n2+n3+n4.

Best wishes.
• Nov 29th 2012, 07:29 PM
samwill
Re: Why Divide in Permutations of Indistinguishable Objects?
That is exactly what I was looking for xylif, thank you!
• Nov 29th 2012, 08:58 PM