Combinatorics – How Many Ways Can N Elements Be Partitioned into Subsets of Size K?

combinatoricsset-partition

Let's have 2 numbers, N and K, where K divides N. The number of K-combinations from a given set S of N elements is a well known formula. Let's concatenate N/K groups (resulting in N elements) such as the resulting set is N. How many possibilities are there, i.e. what's the formula?

For instance:
N=4, K=2, C(4, 2) = 6 {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}
The 3 possibilities are: 

  {1,2},{3,4}
  {1,3},{2,4}
  {1,4},{2,3}

I generated these combinations and I think the number goes like this:

(4, 2): 3
(6, 3): 10
(6, 2): 15
(10, 5): 126
(9, 3): 280
(10, 2): 945
(14, 7): 1716
(12, 4): 5775
(15, 5): 126126
(15, 3): 1401400

Apparently, the result always divides with (N-1).

Best Answer

You want to count the number of set partitions of a set of $n$ elments, into $n/k$ parts each of size $k$. (It is assumed that $k$ divides $n$.)

Method 1.

We can generate such a partition by writing down the $n$ elements in a sequence, and then declaring that the first $k$ elements are the first part, the next $k$ elements are the second part, and so on. There are $n!$ ways of writing $n$ elements in a sequence, but each partition is generated multiple times: for each of the $n/k$ parts, there are $k!$ orderings of the $k$ elements in that part that would lead to the same partition, as you don't care about the order within each part. Further, there are $(n/k)!$ orderings of the parts themselves, for the same partition.

The number of partitions is therefore: $$\frac{n!}{(k!)^{n/k} (n/k)!}$$

Method 2.

You can choose the elements of the first part in $\binom{n}{k}$ ways, then choose the elements of the second part as $k$ out of the remaining $n-k$ in $\binom{n-k}{k}$ ways, and so on. But as different orderings of the $(n/k)$ parts don't change the partition, the number of partitions is

$$\frac{\binom{n\vphantom{k}}{k}\binom{n-k}{k}\cdots\binom{k}{k}}{(n/k)!} = \frac{n!}{(k!)^{n/k}(n/k)!}$$ as before.

You can verify that this accords with all your cases. For instance, for $n=15$ and $k=5$, you get $\frac{15!}{5!^3 3!} = 126126$. These numbers are tabulated in OEIS A060540, and no simpler formula is listed.

Related Question