Can anyone confirm formula (combinations)

  1. uart

    uart 2,776
    Science Advisor

    Hi, I've been scratching around trying to figure out a formula for the following problem and I've got one that I think is correct. Just wondering if anyone can confirm it for certain (like maybe you have it in a text book or know it well etc). Thanks.

    Problem : You need to partition n=k*m distinct objects into k sets each containing m objects. How many ways can you do this?



    Proposed Answer :

    Number of possible distinct partitionings = n! / ( k! * (m!)^k )

    (I think it's correct).
     
    Last edited: Mar 26, 2005
  2. jcsd
  3. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Sounds plausible.
     
  4. matt grime

    matt grime 9,396
    Science Advisor
    Homework Helper

    Are the sets into which we partition indistinguishable? Ie if we partition n into n sets there are n! ways of doing this if we consider order, or just 1 if we say that they are all equivalent. I'm guessing fromyour formula order doesn't matter.

    So there are nCm ways of picking the first set, mutliplied by (n-m)Cm for the second and so on, but we need to divide by k! to forget the ordering which is, I suspect, exactly what your formula is.
     
  5. uart

    uart 2,776
    Science Advisor

    Your guess is correct Matt, the way I set it up is that order doesn't matter. So in the example of partitioning n items into n sets of one item each then yes there is only one way to do it, not n! ways.

    An example of the type of problem that I wanted to solve is : say you have 12 people meet to play 6 games of chess, how many distinct ways can you organize that round of 6 games.

    BTW, I can prove for certain that the formula works for the m=2 case (like in the chess example) but I was just a little unsure if it was correct for m>2.
     
    Last edited: Mar 27, 2005
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?