Number of ways to divide n people into k groups with at least 2 people in each group

Question

I'm trying to figure out the number of ways to divide n people into k groups with at least 2 people in each group. Should I first decide a recurrence relation of the number? I don't know how I could prove such a relation.

Answer 1

Denote by $G(n,k)$ the number of partitions of $n$ people into $k$ groups of size $\geq2$. It is obvious that $G(n,k)=0$ if $n<2k$. Furthermore $$G(n,1)=\left\{\eqalign{&0\qquad(n<2)\cr &1\qquad(n\geq2)\ .\cr}\right.$$ A recursion with respect to $k$ is obtained as follows: The oldest person among the $n$ may choose the size $j\geq 2$ of his group and then the other members of his group in ${n-1\choose j-1}$ ways. There are then $n-j$ people left over, which have to be partitioned into $k-1$ groups of size $\geq2$. This enforces $n-j\geq 2(k-1)$, and leads to the recursion $$G(n,k)=\sum_{j=2}^{n+2-2k}{n-1\choose j-1}G(n-j,k-1)\qquad(n\geq2k, \ k\geq2)\ .$$ In the case $g(k):=G(2k,k)$ one obtains a closed formula with double factorials. By letting the oldest person make the first choice one immediately obtains the recursion $g(k)=(2k-1)g(k-1)$, so that $g(k)=1\cdot3\cdot5\cdot\ldots\cdot(2k-1)$.

Answer 2

The the number of ways in which n people can be divided into k groups of which first contain $r_1$ people, second contains $r_2$ people etc. is $\frac{n!}{r_1!r_2!...r_k!}$

Where $r_1,...r_k$ are integers such that $ r_1+r_2 +...+r_k=n, r_i\geq 0$

Answer 3

We get more or less by inspection the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}_{=k}(\textsc{SET}_{\ge 2}(\mathcal{Z})).$$

This yields per the generating function

$$G_{n,k} = n! [z^n] \frac{1}{k!} (\exp(z)-z-1)^k \\ = n! [z^n] \frac{1}{k!} \sum_{q=0}^k {k\choose q} (\exp(z)-1)^q (-1)^{k-q} z^{k-q} \\ = n! \frac{1}{k!} \sum_{q=0}^k {k\choose q} [z^{n+q-k}] (\exp(z)-1)^q (-1)^{k-q} \\ = n! \frac{1}{k!} \sum_{q=0}^k {k\choose q} q! [z^{n+q-k}] \frac{(\exp(z)-1)^q}{q!} (-1)^{k-q} \\ = n! \frac{1}{k!} \sum_{q=0}^k {k\choose q} q! \frac{1}{(n+q-k)!} {n+q-k\brace q} (-1)^{k-q}.$$

This simplifies to

$$\bbox[5px,border:2px solid #00A000]{ G_{n,k} = \sum_{q=0}^k {n\choose k-q} (-1)^{k-q} {n+q-k\brace q}.}$$

I.e. we get for $n=10$ the sequence

$$1, 501, 6825, 9450, 945, 0, \ldots$$

which points us to OEIS A008299, where these data are confirmed and, incidentally, shown to match the accepted answer.

Answer 4

Here is a derivation of Marko Riedel's formula using the principle of inclusion-exclusion.

Let $P$ be the set of partitions of your set of $\{1,2,\dots,n\}$ elements into $k$ groups (without the $\ge 2$ restriction). For each $i\in \{1,2,\dots,n\}$, let $P_i$ be the number of partitions where $i$ is in a group of size $1$. We want to count $$ \Big|P\setminus \bigcup_{i=1}^n P_i\Big|. $$ Using inclusion exclusion, and the symmetry of the numbers, this is $$ |P|-\binom{n}1|P_1|+\binom{n}2|P_1\cap P_2|-\dots+(-1)^j\binom{n}j|P_1\cap P_2\cap \dots \cap P_j|+\dots $$ To count $|P_1\cap P_2\cap \dots \cap P_j|$, note that elements $1,2,\dots,k$ are all alone, so we must partition the remaining $n-j$ elements into $k-j$ parts. This can be done in ${n-j \brace k-j}$ ways, by defintion of the Stirling numbers of the second kind. Therefore, the final result is $$ \sum_{j=0}^k(-1)^j\binom{n}j{n-j \brace k-j} $$ Reversing the order of summation (and changing $j$ to $q$) gives Marko's answer.