Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
2  
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
1  
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
    
Related: Four positive numbers less than 10 must add up to 12. –  MJD Aug 15 '13 at 20:09

2 Answers 2

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.

share|improve this answer

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

share|improve this answer
    
I do not require direct answer. I want to solve it by permuatation and combinations –  Prannoy Mittal Nov 9 '12 at 8:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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