# How to count possible separations of N items into K clusters?

How many ways are to separate N same items into K clusters.

For N=10, K=4 are there 9 ways:

(7,1,1,1), (6,2,1,1), (5,2,2,1), (4,2,2,2), (5,3,1,1), (4,4,1,1), (4,3,2,1), (3,3,3,1) and (3,3,2,2).

Is there any formula for this?

-
For your specific example: see formula 64 here. Formula 59 in that link gives you an efficient recursion relation for evaluating the partition number. – J. M. Sep 1 '11 at 16:13
@J.M. That'd be good as an answer :) – Zev Chonoles Sep 1 '11 at 16:17
@Zev: Will do, give me a few minutes. (The closed form expression is hella long!) – J. M. Sep 1 '11 at 16:28

This can be thought of as a "constrained" partition number. Letting $p(n,k)$ denote the number of ways $n$ can be written as a sum of $k$ terms, MathWorld gives a recurrence relation you can use for computations:

$$p(n,k)=p(n-1,k-1)+p(n-k,k),\quad p(n,0)=0,p(n,n)=1,p(n,k)=0 \text{ if }n < k$$

For the specific case of a partition into four terms, there is a closed form:

\begin{align*}p(n,4)&=\frac1{864}\left(-39-27n+18n^2+6n^3-96\cos\left(\frac{2n\pi}{3}\right)\right.+\\&\left.27(1+n)(-1)^n+32\sqrt{3}\sin\left(\frac{2n\pi}{3}\right)\right)+\frac18(-1)^{n/2}(n+1)\bmod 2\end{align*}

Closed forms for other values of $k$ are also listed in the link I gave.

-

There are two ways to caclulate this, by recursion or by generating functions.

You can find here a Java applet (and code) which calculates this and similar questions by recursion.

For generating functions, you want the co-efficient of the $x^{10}$ term in the expansion of $$\frac{x^4}{(1-x)(1-x^2)(1-x^3)(1-x^4)}.$$

OEIS A026810 may be of interest.

-