Results 1 to 13 of 13

Math Help - Why Divide in Permutations of Indistinguishable Objects?

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1

    Re: Why Divide in Permutations of Indistinguishable Objects?

    Quote Originally Posted by samwill View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    5

    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)
    Last edited by samwill; November 14th 2012 at 10:54 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1

    Re: Why Divide in Permutations of Indistinguishable Objects?

    Quote Originally Posted by samwill View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,259
    Thanks
    1800

    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?"
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1

    Re: Why Divide in Permutations of Indistinguishable Objects?

    Quote Originally Posted by samwill View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,925
    Thanks
    1764
    Awards
    1

    Re: Why Divide in Permutations of Indistinguishable Objects?

    Quote Originally Posted by samwill View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2012
    From
    urth
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    5

    Re: Why Divide in Permutations of Indistinguishable Objects?

    That is exactly what I was looking for xylif, thank you!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Why Divide in Permutations of Indistinguishable Objects?

    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Nov 2012
    From
    urth
    Posts
    2

    Re: Why Divide in Permutations of Indistinguishable Objects?

    Quote Originally Posted by Link View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Tensions between three objects
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: September 19th 2009, 05:03 PM
  2. Replies: 1
    Last Post: February 13th 2009, 07:01 AM
  3. permutations with repeated objects?
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 9th 2009, 02:15 PM
  4. Ways to divide objects
    Posted in the Statistics Forum
    Replies: 2
    Last Post: September 27th 2007, 03:49 PM
  5. gravity between 2 objects
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: December 24th 2006, 10:31 AM

Search Tags


/mathhelpforum @mathhelpforum