0
$\begingroup$

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.

1 Answers 1

3

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.

  • 0
    Awesome! Thank you, sir! :)2012-10-11