# Thread: find the number of ways

1. ## 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
The combinations are:

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

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

example 3: x=8,n=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

2. 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.

3. Originally Posted by lali
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
The combinations are:

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

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

example 3: x=8,n=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.

4. 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.