Page 1 of 1
Ways
Posted: November 23rd, 2019, 10:54 am
by cinelli
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
Re: Ways
Posted: November 23rd, 2019, 6:28 pm
by Gengulphus
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
Re: Ways
Posted: November 24th, 2019, 5:36 pm
by cinelli
Congratulations, Gengulphus. That really is a very elegant solution.
Cinelli