2
$\begingroup$

Many questions on this site involve counting the number of ways one can divide a set of n people into equally-sized groups, but how would one do so for unequally-sized groups?

The answers for this question don't provide an explanation of how to do this.

More specifically, what are the number of ways I can divide a set of 10 people in the following groups:

  • Two groups will contain 3 people.
  • One group will contain 2 people.
  • One group will contain 1 person.

For this specific question, I was thinking

$$ \frac{\dbinom{10}{3} \dbinom{7}{3} \dbinom{4}{2} \dbinom{2}{1}}{4!} $$

The numerator represents the grouping and the denominator represents the fact that the order of the grouping does not matter.

However, the answers to the referenced question show that this is incorrect.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Since $3+3+2+1=9$, one of the $10$ people will not be in any group. Fine, but it's confusing to call that "dividing $10$ people into groups". $\endgroup$ – bof Oct 30 '13 at 4:10
1
$\begingroup$

Because the groups of $2$ and $1$ are distinct sizes, you don't have to consider reordering those groups. The denominator should be $2!=2$ because there are $2$ ways to order the two groups of three. The numerator is correct.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you please explain further? The set {{ABC}, {DEF}, {GH}, {I}} has 4 items. Shouldn't we take care of ordering them? If not, where is this taken care of? $\endgroup$ – FearlessFuture Oct 30 '13 at 3:31
  • $\begingroup$ No, the only other order that represents the same grouping is $\{\{DEF\},\{ABC\},\{GH\},\{I\}\}$ You can require that the doubleton and singleton come last-you can tell those sets apart by the number of elements. If you had $4+4+4+3+3+2+2$ the denominator would be $3!2!2!$ because you could reorder each size. $\endgroup$ – Ross Millikan Oct 30 '13 at 3:36
  • $\begingroup$ Although the OP labels the groups as Group 1, Group 2, Group 3, and Group 4, you are assuming that the labels don't matter. This is not clear to me. Perhaps a clarification from the OP would be in order. $\endgroup$ – bof Oct 30 '13 at 4:08
  • $\begingroup$ Yes, those labels don't matter. It could be rephrased as two groups of 3, one group of 2, and one group of 1. $\endgroup$ – FearlessFuture Oct 30 '13 at 4:17
  • $\begingroup$ @RossMillikan, but because those group labels don't matter, the same grouping can be represented by { {GH}, {I}, {ABC}, {DEF} }, { {I}, {ABC}, {GH}, {DEF} }, etc. I am still confused why we don't divide by 4! to eliminate the ordering of the groups. $\endgroup$ – FearlessFuture Oct 30 '13 at 10:56
0
$\begingroup$

I think this might be a case of 'combination with repetition'(combination with the amounts not set) for the general case.

${(n-1)+r}\choose r$ for $r$ elements placed into one of $n$ groups. So if there were $10$ x's and $4$ groups it would look something like $x|xx|xx|xxxxx$ and be ${13\choose 10}=1716$. For this case you can never divide it into $4$ equally sized groups so do not need to worry about overcounting in that regard but if you did I believe it would just be the one case if $n$ evenly divides $r$. This would also count all cases where there are $0$ in a given group(s) so that would also be overcounting if you wanted at least $1$ per group.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.