Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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|improve this answer
    
Awesome! Thank you, sir! :) –  Sh4pe Oct 11 '12 at 11:56

Your Answer

 
discard

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.