# Generating function for a sum without number repetition

• Nov 17th 2009, 02:42 PM
eei
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?
• Nov 17th 2009, 05:27 PM
awkward
Quote:

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
$\prod_{j=1}^{30} (1 + u t^j)$

The number of arrangements that add up to 20 with 4 summands is the coefficient of $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".
• Nov 18th 2009, 05:59 AM
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.
• Nov 18th 2009, 06:28 AM
emakarov
Thanks, very nice idea.

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

Consider this expression: $(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 $ut^j$ from each of the 14 factors and then multiply together what you have chosen, e.g.: $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 $u^4t^{20}$. Since the power of $u$ is just 4, you have to choose $ut^j$ from only 4 factors, and 1 from all the rest. Now, the power of $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 $t$, i.e., 20.
• Nov 18th 2009, 02:29 PM
eei
Shortcut method
Makes sense. Is there a shortcut method to getting the particular value from a expansion? Thanks !!(Nod)
• Nov 18th 2009, 02:47 PM
emakarov
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).
• Nov 18th 2009, 03:04 PM
awkward
Quote:

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.
• Nov 19th 2009, 01:55 AM
eei
Thanks
Sure, thanks for all the help, very much appreciated.(Smirk)
• Nov 20th 2009, 08:58 AM
eei
Further Info
Just to let you know I used software called Maxima to expand the expression and works very nicely. Thanks to all.(Hi)