Results 1 to 9 of 9

Math Help - Generating function for a sum without number repetition

  1. #1
    eei
    eei is offline
    Newbie
    Joined
    Nov 2009
    Posts
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by eei View Post
    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".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    eei
    eei is offline
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Follow up

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    eei
    eei is offline
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Shortcut method

    Makes sense. Is there a shortcut method to getting the particular value from a expansion? Thanks !!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    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).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by eei View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    eei
    eei is offline
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Thanks

    Sure, thanks for all the help, very much appreciated.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    eei
    eei is offline
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Further Info

    Just to let you know I used software called Maxima to expand the expression and works very nicely. Thanks to all.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding probability function of moment generating function
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: July 4th 2011, 05:03 PM
  2. Replies: 2
    Last Post: January 11th 2011, 06:34 AM
  3. generating function
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 8th 2010, 08:33 AM
  4. Moment generating function and distribution function?
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: January 25th 2009, 03:02 PM
  5. Generating Function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2008, 02:50 PM

Search Tags


/mathhelpforum @mathhelpforum