# how to find number of different combination of 100

• January 26th, 2013, 01:32 AM
freakycoder
how to find number of different combination of 100
How many different ways can one hundred be written as a sum of at least two positive integers?

I am not getting algo. please any one can give me write solution of this problem
• January 26th, 2013, 06:48 AM
Norm
Re: how to find number of different combination of 100
• January 26th, 2013, 08:16 AM
curmudgeon
Re: how to find number of different combination of 100
Quote:

Originally Posted by freakycoder
...I am not getting algo. please any one can give me write solution of this problem

That's not how this forum works.
• January 26th, 2013, 10:16 PM
Zaphod_b
Re: how to find number of different combination of 100
Quote:

Originally Posted by freakycoder
How many different ways can one hundred be written as a sum of at least two positive integers?

I am not getting algo

Does "algo" mean algorithm?

Well...

This is related to a well-known topic in number theory: Integer Partitions

Here is an illustration of how calculation of a partition number (size of the set of partitions of a positive integer) relates to your assignment:

Let's look at the number of ways of writing a particular number, 5, as the sum of positive integers:

Note that p(5) = 7 and the seven ways of writing 5 as the sum of positive integers are:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Note also that, except for the first one, each of these lines (called parts or partitions of the number) consists of the sum of two or more positive integers.

Making a slight inductive leap (without formal proof):

The algorithm for finding the number of ways of writing 100 as the sum of two or more positive integers is:

1. Calculate p(100).

Finally, note that using partition number calculations as outlined in the Wikipedia article (and myriads of other references) depends on the following convention:

Two sums that differ only in the order of their terms are considered to be the same partition.
That is, 2+3 is the same as 3+2, so you don't count that as two different partitions.
Similarly, 2+2+1 is the same as 2+1+2, and is the same as 1+2+2.
Etc.

Cheers!

Z