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