Is there a formula for the number of k-partitions of a set?

Question

In how many ways can a set be partitioned into k non-empty subsets?

Answer 1

If the set is non empty, it can be calculated with a recursive formula.

Let $S_{n,k}$ be the number of $k$-partitions of a set $X$ ($n\ge k \ge 1$).

Simple observations: $S_{n,1}=1,\enspace S_{n,n}=1$.

Let us now suppose $n>k>1$. Let $x_0\in X$, and consider a $k$-partition $\mathcal P$ of $X$.

• Either $\{x_0\}$ is a member of $\mathcal P$. Then $\mathcal P'=\mathcal P\setminus\bigl\{\{x_0\}\bigr\} $ is a $k-1$-partition of $X'=X\setminus \{x_0\}$. These are $S_{n-1,k-1}$ in number.
• Or $\{x_0\}$ is a not a member of $\mathcal P$. Then $\mathcal P$ induces a $k$-partition of $X'$, by taking the intersections of its members with $X'$. Conversely, from a $k$-partition of $X'$, you get a $k$-partition of $X$ by adjoining $x_0$ to one of its members. As there are $p$ choices for this adjunction, these partitions are $kS_{n-1,k}$ in number.

Conclusion: we obtain the following recurrence relation:

$$S_{n,k}=S_{n-1,k-1}+kS_{n-1,k}.$$

We can compute the values of the $S_{n,k}$s in a way very similar to Pascal's triangle. Here are the first values: $$ \begin{array}{r|*{8}{c}} k = &1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline n = 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 3 & 1 \\ 4 & 1 & 7 & 6 & 1\\ 5 & 1 & 15 & 25 & 10 & 1 \\ 6 & 1 & 31 & 90 & 65 & 15 & 1\\ 7 & 1 & 63 & 301 & 350 & 140 & 21 & 1\\ 8 & 1 & 127 & 969 & 1701 & 1050 & 266 & 28 & 1 \end{array}$$

Answer 2

Following the above notation, the number of non-empty $k$-partitions in a set of $n$ elements is:

$$S_{n,k} = \frac{1}{(k-1)!}\sum_{j=0}^{k-1}{(-1)^{j}\binom{k-1}{j}}(k-j)^{n-1}$$

For example:

$$S_{n,2} = \sum_{j=0}^{1}{(-1)^{j}\binom{1}{j}(2-j)^{n-1}} = 2^{n-1} - 1$$

$$S_{n,3} = \frac{1}{2}\sum_{j=0}^{2}{(-1)^{j}\binom{2}{j}}(3-j)^{n-1} = \frac{3^{n-1}-2^{n}+1}{2}$$

and so on.

The following is just an anecdotal extra, but I remember writing this formula when I played Final Fantasy VIII Remastered a while ago to calculate the number of ways to assign GF to the three active party members, which turned out to be a problem equivalent to finding out the number of distinct 3-partitions of the set of acquired GFs.