0
$\begingroup$

In how many ways can a group of $8$ people be divided into committees, subject to the constraints that each person must belong to exactly one committee and each committee must contain at least two people?

The answer I got is ${8\choose 1}{ 8\choose 2} $. Is this correct?

$\endgroup$
  • $\begingroup$ So, the number of the committees is one, two, three or four? $\endgroup$ – mathlove Dec 27 '13 at 11:33
  • 1
    $\begingroup$ It is not clearly stated, but the question seems to only make sense if (unlike real-life committees which are convened for a particular purpose) the individual committees themselves have no identity: the only information of an assignment of people to committees is the partition of the $8$ people it defines (which pairs are on a same committee, which pairs are not). Alternatively, the question ask for the number of equivalence relations (of being on a same committee) on a set of $8$ can be defined such that each equivalence class has at least two elements. The question should clarify this. $\endgroup$ – Marc van Leeuwen Dec 27 '13 at 12:24
  • 1
    $\begingroup$ The reason I say the question only makes sense without identity for the committees is that with a variable number of committees possible, one cannot decide which number of identities to work with. But the absence of identities implies that swapping committees in a $(4,4)$ partition makes no difference, whence there are only $\binom84/2=35$ such partitions. $\endgroup$ – Marc van Leeuwen Dec 27 '13 at 12:34
2
$\begingroup$

$8=8$ gives $\frac{8!}{8!}$ possibilities.

$8=2+6$ gives $\frac{8!}{2!6!}$ possibilities.

$8=3+5$ gives $\frac{8!}{3!5!}$ possibilities.

$8=4+4$ gives $\frac{8!}{4!4!}$ possibilities.

$8=2+2+4$ gives $\frac{8!}{2!2!4!}$ possibilities.

$8=2+3+3$ gives $\frac{8!}{2!3!3!}$ possibilities.

$8=2+2+2+2$ gives $\frac{8!}{2!2!2!2!}$ possibilities.

Here e.g. $8=2+3+3$ represents the situation of $1$ committee of $2$ persons and $2$ committees of $3$ persons. Persons A,B,C belonging to the 'first' committee of $3$ is thought of as distinct from persons A,B,C belonging to the 'second' committee of $3$.

$\endgroup$
  • $\begingroup$ I don't like this solution because every case has it's own calculation, but I can't think of any other (simple) way to calculate the number of possibilities. $\endgroup$ – Ragnar Dec 27 '13 at 12:01
  • $\begingroup$ @Ragnar. Neither can I. If there is indeed a simpler way then that will surprise me. $\endgroup$ – drhab Dec 27 '13 at 12:11
  • 2
    $\begingroup$ It is not at all clear from the question that we are to distinguish between the 'first' and 'second' committee of $3$. The more natural interpretation (it seems to me) is that we want the number $a_n$ of partitions of an $n$-element set (for $n=8$) into (unlabeled) blocks of size at least $2$. Analogously to the Bell numbers, these numbers satisfy the recurrence $a_{n+1}=\sum_{k=0}^{n-1}\binom{n}{k} a_k$ and have the exponential generating function $\exp(\exp(x)-1-x)$; this is OEIS sequence A000296, and $a_8=715$. $\endgroup$ – bof Dec 27 '13 at 12:34

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.