5
$\begingroup$

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?

  • 0
    @Zev: Will do, give me a few minutes. (The closed form expression is hella long!)2011-09-01

2 Answers 2

3

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.

3

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.