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?
 A: 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. 
A: 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.
