#### Got a credit card? use our Credit Card & Finance Calculators

Thanks to Anonymous,johnhemming,Anonymous,Rhyd6,dredd0, for Donating to support the site

## Ways

cinelli
Lemon Slice
Posts: 290
Joined: November 9th, 2016, 11:33 am
Has thanked: 87 times
Been thanked: 51 times

### Ways

The number 3 can be expressed as a sum of one or more positive integers in four ways, namely as 3, 1+2, 2+1 and 1+1+1. In how many ways can any positive integer n be expressed?

Cinelli

Gengulphus
Lemon Quarter
Posts: 3137
Joined: November 4th, 2016, 1:17 am
Been thanked: 1695 times

### Re: Ways

cinelli wrote:The number 3 can be expressed as a sum of one or more positive integers in four ways, namely as 3, 1+2, 2+1 and 1+1+1. In how many ways can any positive integer n be expressed?

Spoiler...

The integer n can be expressed in 2^(n-1) ways. The proof is just to imagine a row of n objects (which I'll represent with asterisks) and with a possible fence (which I'll represent with "|") between each pair. There are n-1 possible fences, each of which might or might not exist independently of all the others, so there are 2^(n-1) possible patterns of fences. From any particular pattern of fences, I can create a sum of positive integers adding up to n by replacing a row of m asterisks without fences between them by m and fences by plus signs, and that transformation is fully reversible to transform a sum of positive integers adding up to n into such a row of objects and fences. So the number of sums of positive integers adding up to n is also 2^(2-1).

For example, for n=4:

`* * * * corresponds to 4* * *|* corresponds to 3+1* *|* * corresponds to 2+2* *|*|* corresponds to 2+1+1*|* * * corresponds to 1+3*|* *|* corresponds to 1+2+1*|*|* * corresponds to 1+1+2*|*|*|* corresponds to 1+1+1+1`

Gengulphus

cinelli
Lemon Slice
Posts: 290
Joined: November 9th, 2016, 11:33 am
Has thanked: 87 times
Been thanked: 51 times

### Re: Ways

Congratulations, Gengulphus. That really is a very elegant solution.

Cinelli