# Non-negative integral solutions of $X_1+X_2+X_3+X_4<n$

The number of non-negative integral solutions of $X_1+X_2+X_3+X_4<n$ (where $n$ is a positive integer) is?

-
Is this the same as for the sum from i=1 to n of the partitions of n in to 4 parts? – futurebird Apr 22 '11 at 13:05
I dont think so... – prem shekhar Apr 22 '11 at 13:06
Please make me understood using more words – prem shekhar Apr 22 '11 at 13:07
So, this isn't a partitions question? I'm confused... – futurebird Apr 22 '11 at 15:44
@a little don: it is (with slight adjustment) a compositions question – Henry Apr 26 '11 at 17:06

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}$

-
To 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. – Christian Blatter Apr 22 '11 at 18:23

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.

-