Thread: 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?

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 .
Asked about rearranging that string we have no way of knowing if is different from .
However, if we add subscripts then it is clear that those strings are district. So divide to end duplication.

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)

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

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 can be arranged in ways.

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

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

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.

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.

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

How different ways can we arrange the string

How different ways can we arrange the string .

Once you get that, go for How different ways can we arrange the string

Then try to generalize.

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₁ indistinguishable objects into n positions?

Since n₁ spots are now occupied, there remain n-n₁ spots to place n₂ indistinguishable objects.

(2) How many ways can we put n₂ indistinguishable objects into n-n₁ positions? .

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

(k) How many ways can we put n_k indistinguishable objects into n-(n₁+n₂+...+n_k-1) positions?


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





Notice that and that 0!=1. Then all the nasty stuff cancels and you are left with:



If you consider MISSISSIPPI, then

n=11
k=4
n₁="M"=1
n₂="I"=4
n₃="S"=4
n₄="P"=2

And n = n1+n2+n3+n4.

Best wishes.

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

It's just a "reverse" use of Rule of product - Wikipedia, the free encyclopedia

Originally Posted by Link

It's just a "reverse" use of Rule of product - Wikipedia, the free encyclopedia

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.