# Sum of four numbers less than a particular value

I have four positive numbers $a_1,\dots,a_4$, each less than $45$. How many different ways are there for $a_1+a_2+a_3+a_4<90$? I require different permutations i.e $a_1a_2a_3a_4$ is different from $a_2a_1a_4a_3$

-
Any numbers? Perhaps you mean integers, or positive integers? Your question is ambiguous. If any numbers are allowed, there are infinitely many combinations. – glebovg Nov 9 '12 at 6:15
Also, would you consider $a_1=21$, $a_2=a_3=a_4=20$ to be a different answer than $a_2=21,$ $a_1=a_3=a_4=20$, or the same thing? That makes a crucial difference. It looks like you probably interpret them to be different, given the permutations tag. Is this correct? – Cameron Buie Nov 9 '12 at 6:25
it should be positive integers – Prannoy Mittal Nov 9 '12 at 6:26
Rolled back: The previous edit introduced 3 changes: each a_i should be positive, each a_i is less than 45, the sum of the a_i's should be less than 90. – Douglas S. Stones Nov 9 '12 at 8:25
– MJD Aug 15 '13 at 20:09

Here is one solution by generating functions: Let $F(x)=(x+x^2+\cdots+x^{44})^4(x+x^2+\cdots)$. I claim that we seek the coefficient of $x^{90}$. Indeed, the statement is equivalent to $a_1+a_2+a_3+a_4+c=90$, for some positive $a_1,\cdots a_4,c$ with $a_1,\cdots a_4<45$. The coefficients of $(x+x^2+\cdots+x^{44})^4$ represent the number of ways to choose $1\le a_1,\cdots a_4\le 44$ such that they add to a certain exponent. The $(x+x^2+\cdots)$ term does the same thing, but there is no upper bound.
Now, we rearrange and obtain $$F(x)=\frac{x^5(1-x^{44})^4}{(1-x)^5}=\frac{x^{181}-4 x^{136}+6 x^{93}-4 x^{49}+x^5}{(1-x)^5}$$ It is well known that the coefficient of $x^k$ in $\frac{1}{(1-x)^m}$ is $\binom{m+k-1}{k}$ (this can be easily proven by induction by using $\frac{1}{(1-x)}=1+x+x^2+\cdots$). Then the number that we seek is $$-4\binom{45}{41}+\binom{89}{85}=1845646$$ Which was confirmed with Java.
If you consider $(a_1,a_2,a_3,a_4)$ the same as $(a_1,a_2,a_4,a_3) \ \ldots$ then according to python the answer is $90316$. If $(a_1,a_2,a_3,a_4)$ and $(a_1,a_2,a_4,a_3)$ are considered different $\ldots$ then the answer is $1898622$.