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$?
Answer:
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
Best Answer
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.