Combination with at least two people.

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?

• So, the number of the committees is one, two, three or four? – mathlove Dec 27 '13 at 11:33
• 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. – Marc van Leeuwen Dec 27 '13 at 12:24
• 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. – Marc van Leeuwen Dec 27 '13 at 12:34

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

• 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. – Ragnar Dec 27 '13 at 12:01
• @Ragnar. Neither can I. If there is indeed a simpler way then that will surprise me. – drhab Dec 27 '13 at 12:11
• 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$. – bof Dec 27 '13 at 12:34