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/