Tell me more ×
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.
up vote 1 down vote favorite

Given an integer $n >0$, how many ways can we express $n$ as the sum of three natural numbers $n_1,n_2,n_3$ ?

share|improve this question
That definition doesn't define a function. – Thomas Andrews Feb 12 '12 at 17:54
1  
I do not really understand what you mean by "cardinality of $f(n)$" as this is just one element of $\mathbb{N}^3$. If you want to phrase your question with the help of a function then you are more likely asking for the cardinalities of the fibers of the map $g: \mathbb{N}^3 \rightarrow \mathbb{N}, (n_1,n_2,n_3) \mapsto n_1+n_2+n_3$. – Matthias Klupsch Feb 12 '12 at 17:56
The function made things confusing, I have edited the question – Freeman Feb 12 '12 at 17:57

3 Answers

up vote 5 down vote accepted

Judging by the comments and other answer I think I might be missing out on something. yet- This might still be right, so I post this answer, please let me know if I'm horribly wrong :-)

I think we this question can be reformulated in the following manner:

Suppose we have $n+2$ balls, $n$ of which are white, and the other two are black. Now, each different way in which you order the $n+2$ balls gives you a different partition of $n$ in to $3$ natural numbers ($0$ included)- just count how many white balls are between any two black ones.

Moreover- any partition of $n$ to naturals $n_1+n_2+n_3=n$, can be visualized as an ordering of the above $n+2$ balls:

Just put the first $n_1$ white balls in a row, followed by a black one, then the next $n_2$ white balls, followed by a black one and then the last $n_3$ white ones.

So the question reduces to how many ways can you arrage $n$ white balls, and two black ones in a row-

This is easily seen to be $\binom{n+2}{2}$.

(once the positions for the two black ones has been set, the partition is determined)

share|improve this answer
Clever! This is definitely correct. In my simplex answer, I mistakenly assumed that he wanted $n_1,n_2,n_3 > 0$, so it would give a different answer, but still, the answer would probably reduce to something quite simple, and would match a similar combinatorial formula. – Lieven Feb 12 '12 at 18:16
This is very enlightening, thanks for making the effort to make this understandable. – Freeman Feb 12 '12 at 19:08
@LHS: sure thing :) – kneidell Feb 12 '12 at 23:09
@LHS: This answer assumes that you find (1,2,3) different from (3,2,1)-that is, you are using ordered partitions. If you want ordered partitions and require all the numbers be >0, you just have $\binom {n-1}{2}$. The same argument holds, but you can't put black balls at the ends or next to each other. – Ross Millikan Feb 13 '12 at 1:35
up vote 3 down vote

I mistakenly assumed that you wanted $n_1,n_2,n_3 > 0$, so the following answer is not correct. I won't remove it, since I think it might still be interesting.

It's the number of lattice points in the interior of a dilation of the standard 2-simplex. Then, using a change of basis, this can be changed into the question of how many lattice points lie inside 2D triangle, which can be found using pick's theorem.

share|improve this answer
Thank you for your contribution, this is still interesting like you say! – Freeman Feb 12 '12 at 19:09
up vote 1 down vote

I hope I understood you correctly, here is my try $$f(n) = \begin{cases} (0,0,0), & n=0 \\ (0,0,1), & n=1 \\ (0,0,2), & n=2 \\ \Big(\frac{n-a}{3},\frac{n-a}{3},\frac{n-a}{3}+a\Big), & n>2 \end{cases}$$ Here $n\equiv a\mod 3$. Also, there are $\tbinom{3 + n - 1}{n}$ ways, by http://en.wikipedia.org/wiki/Stars_and_bars_%28probability%29

share|improve this answer

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.