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?
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)
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
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_{1} indistinguishable objects into n positions?
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? .
.
.
.
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?
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_{1}="M"=1
n_{2}="I"=4
n_{3}="S"=4
n_{4}="P"=2
And n = n1+n2+n3+n4.
Best wishes.
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.