[Math] 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

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.