Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.