Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $\mathcal{M}(n,k) := \{ \, m\in\mathbb{N}^n \,\,\lvert \,\,\, \sum_{i=1}^n m_i = k \,\}$, where $\mathbb{N}$ denotes the natural numbers with the $0$. Also, let $M(n,k) := |\mathcal{M}(n,k)|$ denote the number of elements in this set.

I assume that the numbers $M(n,k)$ are well known. I'm looking for a general formula for them. With basic calculations, I've found out that $M(1,k) = 1$, $M(2,k) = k+1$, $M(3,k)=\frac{1}{2} (k+1)(k+2)$ and $M(4,k) = \frac{1}{6}(k+1)(k^2+5k+6)$. I could not come up with an inductive proof for general $M(n,k)$, however.

And I'm not very interested in a proof, as I assume - maybe naively - that such a proof will be inductive, using only elementary calculations. I'm more interested in the result.

Do these numbers have a name? Is there a formula for $M(n,k)$?

Thank you for your help.

share|cite|improve this question
up vote 2 down vote accepted

While I'm not sure if $M(n,k)$ has a name (it's an ordered partition of $k$ into $n$ pieces, but this is a bit bulky), there is a nice way to find the formula for it, which often goes under the name Stars and Bars.

To give an example, if we want to break $7$ into $3$ pieces, say $4+1+2$, we can represent it graphically as


Such a sum is determined by the places where we place the bars. We have 7+2=9 symbols, and there are $\binom{9}{2}$ ways in which to place the $2$ bars. More generally, $M(n,k)=\binom{n+k-1}{n-1}$.

There is a very small change required if you want the terms in the sum to be nonzero. Since you didn't ask for it, I leave it to you as an exercise.

share|cite|improve this answer
Awesome! Thank you, sir! :) – Sh4pe Oct 11 '12 at 11:56

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.