The number of non-negative integral solutions of $X_1+X_2+X_3+X_4
Non-negative integral solutions of X_1+X_2+X_3+X_4
3
$\begingroup$
number-theory
inequality
-
0@a little don: it is (with slight adjustment) a [compositions](http://en.wikipedia.org/wiki/Composition_%28number_theory%29) question – 2011-04-26
2 Answers
11
It' the same as the number of integral non-negative solutions to $X_1+X_2+X_3+X_4+X_5=n-1$, where $X_5$ is the difference, which is $\binom{n-1+5-1}{5-1}=\binom{n+3}{4}$
-
1To expand on this: Each solution of $X_1+\ldots+X_5=n-1$ with nonnegative $X_i$ can be encoded as a word consisting of $n-1$ ones and $4$ zeros used as separation marks. The total number of such words is equal to the number of ways to choose a four-element subset from $(n-1)+4$ cells. – 2011-04-22
3
Start with $X_1 < n$ there are $n$ values $0,1,\cdots,n-1$ so call $S_1(n) = n$.
Now we can try $X_1 + X_2 < n$ there are a triangle of values so $S_2(n) = T(n)$.
The triangular numbers are the sum of the first $n$ numbers and in general we have $S_k(n) = \sum_{i=0}^{n} S_{k-1}(i).$
These are just the binomial coefficients.