Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search