Can anyone confirm formula (combinations)

  1. Mar 26, 2005 #1

    uart

    User Avatar
    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. Mar 26, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Sounds plausible.
     
  4. Mar 26, 2005 #3

    matt grime

    User Avatar
    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. Mar 27, 2005 #4

    uart

    User Avatar
    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 this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Can anyone confirm formula (combinations)
  1. Can anyone solve this? (Replies: 3)

Loading...