[Math] Number of ways to divide $N$ identical things into groups of size at least $K$

combinatorics

We are given $N$ and $K$, we have to find number of ways to divide $N$ identical items into groups of size at least $K$.

Example 1: $N = 4, K = 2$

Answer: $2$

The given divisions are $(4)$ and $(2,2)$

Example 2: $N=6 , K= 2$

Answer: $4$

The divisions are $(6)$, $(2,2,2)$, $(4,2)$ and $(3,3)$.

NOTE: we consider $(4,2)$ and $(2,4)$ as the same.

Best Answer

There's no nice formula. As I said in the comments, there's no nice way even to compute the answer for the trivial case $K=1$. If $K=1$, then the number of partitions is just the total number of partitions of $N$, up to reordering. We write this as $p(N)$. If you want a sort of formula for $p(N)$, it's the coefficient of $X^N$ in the infinite series:

$$ \prod_{k=1}^\infty\left(\frac1{1-X^k}\right) $$

This does not give an efficient method for computing $p(N)$, however. In fact, the best way to try and work out what $p(N)$ is, is by considering partitions where each set has size at most $K$, as you are asking for.

Write $p(K, N)$ for the total number of partitions of $N$ items into sets of size at most $K$, up to reordering. For example, $p(1, N)=p(N)$. The following three facts are quite easy to show:

  1. $p(K, N)=0$ if $K>N$
  2. $p(K, N)=1$ if $K=N$
  3. (the most important one) $p(K, N)=p(K+1, N)+p(K, N-K)$ otherwise.

After you've shown these three facts (only the third is at all tricky), you can find $p(K, N)$ for arbitrary $K, N$ using the following algorithm: draw up a table of values for $p(K, N)$ for $N=1,2,\dots$ and $K=1,2,\dots$, and then fill in the table using the three rules above until you reach your desired value.

To get you started, you can immediately fill in some of the table by putting $1$s along the diagonal (where $N=K$) and $0$s below it (where $K>N$). Then you can tackle the case $N=K+1$: using rule (3.), you get

$$ p(K, K+1)=p(K+1,K+1)+p(K,1) $$

You can use this to fill in the diagonal just below the diagonal you've filled with $1$s. Then just keep going: you should be able to work out how to go on from here!

Related Question