1
$\begingroup$

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

$\endgroup$
3
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ All of these were mentioned in the comments, ~9h earlier. $\endgroup$
    – rtybase
    Jul 13 '19 at 8:19
  • $\begingroup$ @rtybase Your point being? If you though the question was a duplicate of some other, you should’ve flagged it as such. $\endgroup$
    – amd
    Jul 13 '19 at 8:21
  • $\begingroup$ 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. $\endgroup$
    – rtybase
    Jul 13 '19 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.