Combinations Totaling 100
Date: 09/27/1999 at 16:36:43 From: Gregory Alan Subject: Combinations Totaling 100 Hello, and thank you for trying to answer this question for me. Here it is, as best as I can state it: The goal is to achieve a sum of 100 adding only 6 numbers together, taken from the set of integers from 1 to 44. Example: 40 + 30 + 15 + 5 + 6 + 4 = 100. You see I've taken 6 integers from the set, and now their sum is equal to 100. Conditions: A. Number set to work with: integers from 1 to 44 inclusive. B. Subset size: 6 numbers. C. Sum to achieve: 100. My question is as follows: Using this method and the numbers here (6 numbers from 1 to 44), how many sets of 6 numbers whose sum is 100 can I make? IMPORTANT: A number cannot be used more than once when making the subset, and the position of a number within the set does not matter. Thank you for all your help with this. Gregory
Date: 09/27/1999 at 17:25:47 From: Doctor Anthony Subject: Re: Combinations Totaling 100 Using generating functions you require the coefficient of x^100 in the expansion of (x + x^2 + x^3 + ... + x^44)^6 = x^6[1 + x + x^2 + ... + x^43]^6 x^6[1 - x^44]^6 = -------------- (1-x)^6 = x^6[1 - 6*x^44 + 15*x^88 - 20*x^132 + ...]* [1 + C(6,1)x + C(7,2)x^2 + ...] We must pick out terms in x^100. Clearly we can ignore terms like x^132 which are already above the required power of x. We have [x^6 - 6*x^50 + 15*x^94 - ...]*[1+C(6,1)x + C(7,2)x^2 + ...] (1) We can combine x^6 from the first bracket with x^94 from the second bracket, (2) We can combine x^50 from the first bracket with x^50 from the second bracket. (3) We can combine x^94 from the first bracket with x^6 from the second bracket. These 3 will be all the ways that we can get a term in x^100. For (1) the term in x^94 is C(99,94) = 71523144 For (2) the required term is -6*C(55,50) = -20872566 For (3) the required term is 15*C(11,6) = 6930 And so the coefficient of x^100 will be 71523144 - 20872566 + 6930 = 50657508 This will be the number of ways you can get 6 numbers from 1 to 44 inclusive to add up to 100. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.