Combinatorial Madness!
a + b + c + d + e = 1 5 ∑ a b c d e
Given that a , b , c , d , e are positive integers satisfying a + b + c + d + e = 1 5 , find the value of the above expression, where the sum is taken over all satisfying ordered quintuplets ( a , b , c , d , e ) .
The answer is 92378.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Hi can you please explain the thought process behind how you solved this problem. I don't fully understand your work. Thank You!
Log in to reply
Since f ( x ) = ( a = 1 ∑ ∞ a x a ) 5 = ( a = 1 ∑ ∞ a x a ) ( b = 1 ∑ ∞ b x b ) ( c = 1 ∑ ∞ c x c ) ( d = 1 ∑ ∞ d x d ) ( e = 1 ∑ ∞ e x e ) = a , b , c , d , e = 1 ∑ ∞ a b c d e x a + b + c + d + e we see that the coefficient of x 1 5 in f ( x ) is a + b + c + d + e = 1 5 ∑ a b c d e which is what we want to evaluate. The rest is, I hope, clear.
I used the exact same trick. Good solution.
Here is a quick Dynamic Programming approach to the problem. Denote the sum of product of all m positive integers summing up to k by S ( m , k ) . We require S ( 5 , 1 5 ) .
Now it is easy to notice that for m ≥ 2 , S ( m , k ) satisfies the following recursions S ( m , k ) = i = 1 ∑ k − 1 S ( m − 1 , i ) ( k − i ) , with the initial condition S ( 1 , k ) = k , ∀ k
These recursions can be easily solved (numerically or otherwise) to get the answer S ( 5 , 1 5 ) = 9 2 3 7 8 .
1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9 ∣ 1 0 ∣ 1 1 ∣ 1 2 ∣ 1 3 ∣ 1 4 ∣ 1 5 ∣ 1 6 ∣ 1 7 ∣ 1 8 ∣ 1 9
Consider choosing 9 objects out of 1 9 objects. The number of ways to do this is obviously ( 9 1 9 ) = 9 2 3 7 8 .
But then, you can choose objects 2 , 4 , 6 , 8 first in the set of objects ensuring there is at least one unchosen object to the left and right of the chosen objects. There are 1 5 unchosen objects, and we need to choose 5 more.
Let the number of ways to choose the 1st object, to the left of the 2nd object be a . Let the number of ways to choose the 3rd object, to the right of the 2nd object and left of the 4th object be b and so on. So, our set becomes like this
a ∣ 2 n d ∣ b ∣ 4 t h ∣ c ∣ 6 t h ∣ d ∣ 8 t h ∣ e
where the number of objects in a , b , c , d , e is the number of ways you can choose from that interval, and a b c d e is the number of ways to choose the 5 remaining objects from any configuration of objects 2 , 4 , 6 , 8 . But , since there are 15 remaining objects, a + b + c + d + e = 1 5 , and since the number of ways to choose 1 9 objects is the sum of all possible configurations of a , b , c , d , e over all configuration of objects 2 , 4 , 6 , 8 , we get the number of ways to choose 9 objects out of 19 objects to be a + b + c + d + e = 1 5 ∑ a b c d e = ( 9 1 9 ) = 9 2 3 7 8 .
I don't get your logic. Perhaps add an explanation. Why choosing 9 objects from 19 object ? I think that lacks explanation. I have solved this problem using another approach though.
Log in to reply
For any 1 ≤ p < q < r < s ≤ 1 9 , how many ways are there of choosing 9 numbers from 1 9 if the 2nd number is p , the 4th number is q , the 6th number is r and the 8th number is s ?
Answer: There are p − 1 numbers between 1 and p − 1 , so p − 1 choices for the 1st number. There are q − p − 1 numbers between p + 1 and q − 1 , so q − p − 1 choices for the 3rd number. Similarly there are r − q − 1 choices for the 5th number, s − r − 1 choices for the 7th number and 1 9 − s choices for the 9th number, so there are ( p − 1 ) ( q − p − 1 ) ( r − q − 1 ) ( s − r − 1 ) ( 1 9 − s ) ways of making these choices.
If we sum over all the possibilities, we must obtain ( 9 1 9 ) , so 1 ≤ p < q < r < s ≤ 1 9 ∑ ( p − 1 ) ( q − p − 1 ) ( r − q − 1 ) ( s − r − 1 ) ( 1 9 − s ) = ( 9 1 9 )
Now change variables.
If we now write a = p − 1 , b = q − p − 1 , c = r − q − 1 , d = s − r − 1 and e = 1 9 − s , then there are a b c d e ways of choosing 9 numbers out of 1 9 , where the 2nd number is a + 1 , the 4th number is a + b + 2 , the 6th number is a + b + c + 3 and the 8th number is a + b + c + d + 4 , where we note that a , b , c , d , e ≥ 0 and a + b + c + d + e = 1 5 . Summing a b c d e over all tuples ( a , b , c , d , e ) with a + b + c + d + e = 1 5 just runs through all the possibilities. Since the contribution of any tuple with a zero coefficient to the sum is zero, these can all be ignored. Thus the sum is ( 9 1 9 ) .
Log in to reply
Yaay, thank you very much for the explanation :)
The sum is the coefficient of x 1 5 in the series expansion of ( a = 1 ∑ ∞ a x a ) 5 = ( ( 1 − x ) 2 x ) 5 = x 5 ( 1 − x ) − 1 0 ∣ x ∣ < 1 and hence is the coefficient of x 1 0 in ( 1 − x ) − 1 0 = n = 0 ∑ ∞ ( n n + 9 ) x n ∣ x ∣ < 1 . Thus the sum is ( 1 0 1 9 ) = 9 2 3 7 8 .