# Thread: Generating function for a sum without number repetition

1. ## Generating function for a sum without number repetition

Hi

Just wondering how to get a generating function to tell me the total number of combinations that add up to a particular number as follows.

1. 4 numbers added together that have a total of say 20.
2. The 4 numbers used must all be different and must be contained between say 1 and 30 inclusive.

e.g.

a+b+c+d = 20

1+2+3+14 = 20

cannot have 1+1+2+17 = 20

Not sure how to do this? Any ideas?

2. Originally Posted by eei
Hi

Just wondering how to get a generating function to tell me the total number of combinations that add up to a particular number as follows.

1. 4 numbers added together that have a total of say 20.
2. The 4 numbers used must all be different and must be contained between say 1 and 30 inclusive.

e.g.

a+b+c+d = 20

1+2+3+14 = 20

cannot have 1+1+2+17 = 20

Not sure how to do this? Any ideas?
I assume from your examples that the order of the summands is not significant, i.e. 1+2+3+14 is the same as 14+3+2+1.

Consider
$\displaystyle \prod_{j=1}^{30} (1 + u t^j)$

The number of arrangements that add up to 20 with 4 summands is the coefficient of $\displaystyle u^4 t^{20}$ in this function when expanded.

A combinatorist would call these arrangements "partitions into unequal parts with at most 4 parts and with no part greater than 30".

Not sure if this is exactly what I am looking for....can you confirm..

The conditions are as follows:

1. 4 numbers added together that have a total of say 20 (must be 4 numbers only, 1,2, or 3 will not do).
2. The 4 numbers used must all be different and must be contained between say 1 and 30 inclusive. No repition of numbers in the sum e.g. 1,1,3,15 (NOT ALLOWED).
3. Like you say order does not matter.

Actually where does the formula come from, so I can read up...Thanks for all the help. Very much appreciated.

4. Thanks, very nice idea.

In more detail (by the way, every number of those four does not exceed 14).

Consider this expression: $\displaystyle (1+ut)(1+ut^2)(1+ut^3)\dots(1+ut^{13})(1+ut^{14})$. When you perform actual multiplication, you select either 1 or $\displaystyle ut^j$ from each of the 14 factors and then multiply together what you have chosen, e.g.: $\displaystyle 1^4\cdot ut^5\cdot ut^6\cdot 1^2\cdot ut^9\cdot 1^5$. And you use all possible ways to do so, then add all those things together.

Now let's consider the coefficient of $\displaystyle u^4t^{20}$. Since the power of $\displaystyle u$ is just 4, you have to choose $\displaystyle ut^j$ from only 4 factors, and 1 from all the rest. Now, the power of $\displaystyle t$ in each factor is different, so when you select 4 different factors, you will get 4 different numbers that add to the total power of $\displaystyle t$, i.e., 20.

5. ## Shortcut method

Makes sense. Is there a shortcut method to getting the particular value from a expansion? Thanks !!

6. I don't know any shortcuts for this, but since it is clear how to do it, there is limited value of doing it yourself. I would use a computer (ideally programs like Mathematics or Maple).

7. Originally Posted by eei
Not sure if this is exactly what I am looking for....can you confirm..

The conditions are as follows:

1. 4 numbers added together that have a total of say 20 (must be 4 numbers only, 1,2, or 3 will not do).
2. The 4 numbers used must all be different and must be contained between say 1 and 30 inclusive. No repition of numbers in the sum e.g. 1,1,3,15 (NOT ALLOWED).
3. Like you say order does not matter.

Actually where does the formula come from, so I can read up...Thanks for all the help. Very much appreciated.
Hi eei,

Emakarov has already done a good job of explaining the generating function. But since you asked for a source, one book is "An Introduction to Combinatorial Analysis" by Riordan. I am sure there are many other sources-- just look for "partitions" in the table of contents or index.

8. ## Thanks

Sure, thanks for all the help, very much appreciated.

9. ## Further Info

Just to let you know I used software called Maxima to expand the expression and works very nicely. Thanks to all.