2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$
    – drhab
    Nov 29 '18 at 13:13
  • $\begingroup$ The groups are indistinguishable $\endgroup$ Nov 29 '18 at 13:21
  • 1
    $\begingroup$ 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)$$ $\endgroup$
    – saulspatz
    Nov 29 '18 at 13:56
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Nov 29 '18 at 15:15
  • $\begingroup$ Thanks a lot for the explanation! $\endgroup$ Nov 29 '18 at 15:53
  • $\begingroup$ Upvoted (+1). Matches the closed form. $\endgroup$ Nov 29 '18 at 19:28
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 30 '18 at 18:09
0
$\begingroup$

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$

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