# The number of triples that sum to a constant

Problem:
How many triples are there of the form $$(x_0,x_1, x_2)$$ where $$x_0 \in I$$, $$x_1 \in I$$, $$x_2\in I$$ $$x_0 \geq 0$$, $$x_1 >= 0$$, $$x_2 >= 0$$ and $$n = x_0 + x_1 + x_2$$ where $$n \in I$$?
Let $$c(n)$$ be the number of tuples we can have for a given $$n$$. For $$n = 0$$, the only valid triple is $$(0,0,0)$$, hence $$c(0) = 1$$.
For $$c(1) = 3$$, the set of valid triples is: $$(0,0,1 ), (0,1,0), (0,0,1)$$ Hence $$c(1) = 3$$.
For $$c(2) = 6$$, the set of valid triples is: $$(1,0,1 ), (0,1,1 ), (0,0,2 ), (1,1,0), (0,2,0), (0,0,2)$$ Hence $$c(2) = 6$$.
Using the information on this URL:
How many $k-$dimensional non-negative integer arrays $(x_1,\cdots,x_k)$ satisfies $x_1+x_2+\cdots+x_k\le n$

I find the answer to be: $$c(n) = {{n+3}\choose{3}} - {{n+2}\choose{3}}$$ $$c(n) = \frac{(n+3)!}{3!n!} - \frac{(n+2)!}{3!(n-1)!}$$ $$c(n) = \frac{(n+3)(n+2)(n+1) - (n+2)(n+1)(n)}{6}$$ $$c(n) = \frac{(n+2)(n+1)(n+3 - n)}{6}$$ $$c(n) = \frac{3(n+2)(n+1)}{6}$$ $$c(n) = \frac{(n+2)(n+1)}{2}$$ Do I have that right?
Thanks,
Bob

• This is equivalent to $\frac12(n+1)(n+2)$ which agrees with the supplied values. Jul 12 '19 at 23:07
• Like this? Jul 12 '19 at 23:10
• en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) Jul 12 '19 at 23:16

Yes - this is correct. This can also be found by defining a helper function $$b(n)$$, which counts the number of ways to write $$n$$ as a sum of two numbers. Clearly, $$b(n) = n+1$$, as the first value, $$v$$, can be anything from $$0$$ to $$n$$, while the second value is $$n - v$$.

The function $$c(n)$$ is then equal to $$\sum_{i = 0}^{n}b(n-i)$$ This is because the first value, $$i$$, can be anything from $$0$$ to $$n$$. The number of ways to write the remaining two numbers so that the total sum is $$n$$ is $$b(n-i)$$. Plugging in the formula finds $$c(n) = \sum_{i = 0}^{n} (n-i+1) = n(n+1) - \frac{n(n+1)}{2} + n+1 = \frac{(n+2)(n+1)}{2}$$

which is the same formula you arrived at.

This is a prototypical “stars and bars” problem. Here we have $$n$$ stars and $$2$$ bars, with $$\binom{n+2}2 = {(n+2)(n+1)\over2}$$ ways to choose among the $$n+2$$ possible positions for the two bars.

Another way: The number of partitions of $$n$$ into three non-negative integers is equal to the coefficient of $$z^n$$ in the formal power series $$(1+z+z^2+z^3+\cdots)^3$$. This coefficient can be found using the generalized binomial theorem: $$(1+z+z^2+z^3+\cdots)^3 = \frac1{(1-z)^3} = \sum_{k=0}^\infty \binom{-3}{k} z^k = \sum_{k=0}^\infty \binom{k+2}2 z^k.$$ The number of partitions is therefore $$\binom{n+2}2$$ as before.

• All of these were mentioned in the comments, ~9h earlier. Jul 13 '19 at 8:19
• @rtybase Your point being? If you though the question was a duplicate of some other, you should’ve flagged it as such.
– amd
Jul 13 '19 at 8:21
• Something genuinly different is required. But up to you really ... I don't think the question is a duplicate. To begin with I don't know what $I$ is (in $x_0 \in I$ for example). Nobody clarrified this. Jul 13 '19 at 8:22