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

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.

• I reckon that the persons are distinguishable. Are the groups also distinguishable (I suspect only on cardinality, but it is essential information and must be given)? Nov 29 '18 at 13:13
• The groups are indistinguishable Nov 29 '18 at 13:21
• Let $G(n,k)$ be the desired number. When we add a new person, we can either add him to an existing group, or we can pair him with one of the $n$ persons, and group the remaining $n-1$ persons into $k-1$ groups of at least two people.$$G(n+1,k)=k(G(n,k)+nG(n-1,k-1)$$ Nov 29 '18 at 13:56

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.

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

• I see. This is really helpful! Suppose that I want to consider the special case where n=2k, is there a way to find a formula for rn,k? Nov 29 '18 at 15:15
• Thanks a lot for the explanation! Nov 29 '18 at 15:53
• Upvoted (+1). Matches the closed form. Nov 29 '18 at 19:28

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.

• Good work. Verified (+1). For some reason I did not complete the simplification at the end. I will leave my answer as is so that your observations / concluding remarks keep making sense. Nov 30 '18 at 18:09

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