Counting Distinct Group Combinations

[Gridvvk]

Let's say you have a group of 22 people, which you would like to break into 5 different groups -- 3 groups of 4 and 2 groups of 5. How many distinct ways can you form such groups?

I don't want to double count groups. Let's say I number the people from A - V. The group ABCDE and ACDBE should be considered the same group since they have the same elements.

I imagine the numerator is
[(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ]

I'm not sure what to divide by to get rid of counting extras.

 

[pbuk]

Order the 5 bins, and order each position in each bin; there are then clearly 22! permutations. The items in the first 3 bins can be ordered 4! different ways and the items in the last 2 bins can be ordered 5! different ways, so there are a total of 4!4!4!5!5! orderings within bins.

It is not clear whether {ABCD, EFGH, ...} and {EFGH, ABCD, ...} are to be considered the same: if so, you need to reduce further by a factor of 3!2!.

 

[pbuk]

Observe that the familiar forumula for combinations $\frac{n!}{k!(n-k)!}$ is derived in the same way where there are n objects and 2 bins containing k and n-k objects respectively, but when we use this we are not generally interested in the contents of the second bin.

 

[Gridvvk]

Thank you. I wanted combinations not permutations though. So my first term would be [(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ]. If I understand correctly, then the inner ordering within the groups is already taken care of by the combination formula (dividing by k!). I did want to consider {ABCD, EFGH, ...} and {EFGH, ABCD, ...} to be the same, so I would divide by a factor of 3! 2! because I have 3 groups of size 4 and 2 groups of size 5. The 3! and 2! term are coming from the number of groups, not the sizes.

So the question:
How many ways to divide group of 22 people into 3 groups of 4 people and 2 groups of 5 people?

has the answer:
[(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ] / (3! * 2!) =
470531961900.

 

[pbuk]

Thank you. I wanted combinations not permutations though. So my first term would be [(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ]. If I understand correctly, then the inner ordering within the groups is already taken care of by the combination formula (dividing by k!). I did want to consider {ABCD, EFGH, ...} and {EFGH, ABCD, ...} to be the same, so I would divide by a factor of 3! 2! because I have 3 groups of size 4 and 2 groups of size 5. The 3! and 2! term are coming from the number of groups, not the sizes.

So the question:
How many ways to divide group of 22 people into 3 groups of 4 people and 2 groups of 5 people?

has the answer:
[(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ] / (3! * 2!) =
470531961900.

I have given you combinations, we get the same answer.

Note that a number of terms can be canceled from the expression you gave to arrive at the expression I gave: $$\frac{22!}{4!18!}.\frac{18!}{4!14!}.\frac{14!}{4!10!}.\frac{10!}{5!5!}.\frac{5!}{5!0!}.\frac{1}{3!2!} = \frac{22!}{4!^35!^2}.\frac{1}{3!2!}$$

 

[Gridvvk]

Right, that eases the computation. Thanks a lot for the help!