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$
Sum of four numbers less than a particular value
-
0Related: [Four positive numbers less than 10 must add up to 12](http://math.stackexchange.com/questions/372624/probability-of-random-integers-digits-summing-to-12). – 2013-08-15
2 Answers
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$.
-
0I do not require direct answer. I want to solve it by permuatation and combinations – 2012-11-09