Can anyone confirm formula (combinations)

uart

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).

Hurkyl

Sounds plausible.

matt grime

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.

uart

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.