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?

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 $\displaystyle ABBCCCDDDD$.

Asked about rearranging that string we have no way of knowing if $\displaystyle ABCDBCDCDDD$ is different from $\displaystyle ABCDBCDCDDD$.

However, if we add subscripts $\displaystyle A_1B_1C_1D_1B_2C_2D_2C_3D_3D_4$ then $\displaystyle A_1B_2C_2D_1B_1C_1D_2C_3D_4D_3$ it is clear that those strings are district. So divide to end duplication.

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)

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 $\displaystyle 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 $\displaystyle 001122$ can be arranged in $\displaystyle \frac{6!}{(2!)^3}$ ways.

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?"

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

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.

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.

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 $\displaystyle AB~?$

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

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

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

Then try to generalize.

Re: Why Divide in Permutations of Indistinguishable Objects?

Say we have n objects, k of which are indistinguishable. Let n_{i}, 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 n_{1} indistinguishable objects into n positions? $\displaystyle C(n,n_1)=\frac{n!}{(n-n_1)!}\cdot \frac{1}{n_1!}$

Since n_{1} spots are now occupied, there remain n-n_{1} spots to place n_{2} indistinguishable objects.

(2) How many ways can we put n_{2} indistinguishable objects into n-n_{1} positions? $\displaystyle 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 n_{k} indistinguishable objects into n-(n_{1}+n_{2}+...+n_{k-1}) positions?

$\displaystyle 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).

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

$\displaystyle \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 $\displaystyle \sum_{i=1}^k n_i = n$ and that 0!=1. Then all the nasty stuff cancels and you are left with:

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

If you consider MISSISSIPPI, then

n=11

k=4

n_{1}="M"=1

n_{2}="I"=4

n_{3}="S"=4

n_{4}="P"=2

And n = n1+n2+n3+n4.

Best wishes.

Re: Why Divide in Permutations of Indistinguishable Objects?

That is exactly what I was looking for xylif, thank you!

Re: Why Divide in Permutations of Indistinguishable Objects?

Re: Why Divide in Permutations of Indistinguishable Objects?

Quote:

Originally Posted by

**Link**

I'm not sure what you mean by 'reverse.' But in general, as a word of caution, be careful not to fall into the fallacy of P => Q is equivalent to Q => P. This is not the case! The converse is not always valid.

Such is the case for the Rule of Product. If I remember correctly, a condition on the Rule of Product states that the events must be independent. If you're calculating dependent probability, you'd still multiply, but the factors would not correspond to independent events.