Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can anyone confirm formula (combinations)

  1. Mar 26, 2005 #1


    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


    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


    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook