Htykuut

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.

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{&0qquad(n<2)cr &1qquad(ngeq2) .cr}right.$$
A recursion with respect to $k$ is obtained as follows: The oldest person among the $n$ may choose the size $jgeq 2$ of his group and then the other members of his group in ${n-1choose 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-jgeq 2(k-1)$, and leads to the recursion
$$G(n,k)=sum_{j=2}^{n+2-2k}{n-1choose j-1}G(n-j,k-1)qquad(ngeq2k, kgeq2) .$$
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)=1cdot3cdot5cdotldotscdot(2k-1)$.

We get more or less by inspection the combinatorial class

$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{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 {kchoose q} (exp(z)-1)^q (-1)^{k-q} z^{k-q}
\ = n! frac{1}{k!}
sum_{q=0}^k {kchoose q}
[z^{n+q-k}] (exp(z)-1)^q (-1)^{k-q}
\ = n! frac{1}{k!}
sum_{q=0}^k {kchoose q} q!
[z^{n+q-k}] frac{(exp(z)-1)^q}{q!} (-1)^{k-q}
\ = n! frac{1}{k!}
sum_{q=0}^k {kchoose q} q!
frac{1}{(n+q-k)!} {n+q-kbrace q} (-1)^{k-q}.$$

This simplifies to

$$bbox[5px,border:2px solid #00A000]{ G_{n,k} =
sum_{q=0}^k {nchoose k-q} (-1)^{k-q} {n+q-kbrace 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.

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 $iin {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|Psetminus bigcup_{i=1}^n P_iBig|.
$$
Using inclusion exclusion, and the symmetry of the numbers, this is
$$
|P|-binom{n}1|P_1|+binom{n}2|P_1cap P_2|-dots+(-1)^jbinom{n}j|P_1cap P_2cap dots cap P_j|+dots
$$
To count $|P_1cap P_2cap 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)^jbinom{n}j{n-j brace k-j}
$$
Reversing the order of summation (and changing $j$ to $q$) gives Marko's answer.

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