Results 1 to 4 of 4

Math Help - find the number of ways

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    11

    find the number of ways

    Given a positive number x, find the number of ways in which n positive numbers can be added to get a sum x.
    n<=x

    example x=8,n=2
    answer = 4
    The combinations are:

    (1,7)
    (2,6)
    (3,5)
    (4,4)

    example 2: x=8,n=3
    answer = 5
    The combinations are:
    (1,1,6)
    (1,2,5)
    (1,3,4)
    (2,3,3)
    (2,2,4)


    example 3: x=8,n=4
    answer=4
    (1,1,1,5)
    (1,1,2,4)
    (1,1,3,3)
    (1,2,2,3)

    I was just wondering if i can obtain a formula from above.
    Sorry if i posted in the wrong forum. I could not find a forum for combinatorics.

    Regards
    lali
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2009
    Posts
    9
    I am not sure if this is right but whenever you right a number as the sum of two other numbers (without considering the order): let x=z+w one of z,w must be less than x/2 and the other greater.In the case where z=x/2 then => w=x/2.
    Hence if you count how many inegers you have in [1,x/2] you find the number of ways that x can be written as the sum of two integers.
    i.e. the number x=100 has 50 integers{1,2,3....50} less than equal to 100/2.=> there are 50 ways to write 100 as the sum of two positive integers.
    in general you can say that x can be written as the sum of two possitive integeres with x/2 different ways if 2 divides x and with (x-1)/2 ways if 2 does not divide x.

    this is for n=2.if you work on the same way you will not need combinatorics and you will buid the formula you want.
    Last edited by lakiz; April 17th 2009 at 03:00 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by lali View Post
    Given a positive number x, find the number of ways in which n positive numbers can be added to get a sum x.
    n<=x

    example x=8,n=2
    answer = 4
    The combinations are:

    (1,7)
    (2,6)
    (3,5)
    (4,4)

    example 2: x=8,n=3
    answer = 5
    The combinations are:
    (1,1,6)
    (1,2,5)
    (1,3,4)
    (2,3,3)
    (2,2,4)


    example 3: x=8,n=4
    answer=4
    (1,1,1,5)
    (1,1,2,4)
    (1,1,3,3)
    (1,2,2,3)

    I was just wondering if i can obtain a formula from above.
    Sorry if i posted in the wrong forum. I could not find a forum for combinatorics.

    Regards
    lali
    Hi lali,

    I can give your problem a name, but I don't have much help otherwise.

    This is the problem of "partitions of an integer into a fixed number of parts". You can find discussions of the problem in many combinatorics books, and the problem has been studied from at least the time of Euler, but I don't think anyone knows a simple formula for it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2009
    Posts
    11
    Thanks for your replies. This is a special case of subset sum problem(an NP complete problem). I didn't know about this problem earlier and just came across it while going through ideas to solve another problem.

    Thank you all.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of ways ?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 14th 2011, 07:39 AM
  2. Number of ways
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 30th 2009, 03:08 PM
  3. Replies: 4
    Last Post: April 10th 2009, 02:03 PM
  4. Replies: 10
    Last Post: April 8th 2009, 11:56 AM
  5. different number of ways
    Posted in the Statistics Forum
    Replies: 2
    Last Post: July 21st 2008, 02:09 PM

Search Tags


/mathhelpforum @mathhelpforum