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
Got a credit card? use our Credit Card & Finance Calculators
Thanks to Anonymous,johnhemming,Anonymous,Rhyd6,dredd0, for Donating to support the site
Ways

 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^(n1) 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 n1 possible fences, each of which might or might not exist independently of all the others, so there are 2^(n1) 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^(21).
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
Return to “Games, Puzzles and Riddles”
Who is online
Users browsing this forum: No registered users and 3 guests