MHB How Many Ways Can a Positive Integer Be Written as a Sum of Positive Integers?

[hxthanh]

$\boxed 1$ How many ways writing positive integer $n\;$ as the sum of the positive integers different each pairs? (no permutation)

Example: $6=6=1+5=2+4=1+2+3 \quad $ (4 ways)

$\boxed 2$ How many ways writing positive integer $n\;$ as the sum of the positive integers? (no permutation)

Example: $\begin{align*} 6&=6\\ & =1+5 = 2+4 = 3+3 \\&= 1+1+4 =1+2+3 =2+2+2\\ &=1+1+1+3 =1+1+2+2 \\& =1+1+1+1+2 \\&=1+1+1+1+1+1 \end{align*}\quad $ (11 ways)

 

[soroban]

Re: Write n=a+b+c+...


If permutations are allowed, the problem is elementary.

Consider a board n inches long.
Mark the board in one-inch intervals.

. . . . \underbrace{\square\!\square\!\square\!\square \cdots \square}_{n-1\text{ marks}}

At each mark, we have 2 choices: cut or do not cut.

Hence, there are 2^{n-1} possible decisions.

Therefore, there are 2^{n-1} possible addition problems.Example: n = 4
. . \begin{array}{c} 4 \\ 1+3, \;\; 2+2, \;\;3+1 \\ 1+1+2, \;\; 1+2+1, \;\; 2 +1+1 \\ 1+1+1+1+1 \end{array}\quad(2^3 = 8\text{ ways)}However, if permutations are not allowed,
. . the problem become very difficult.

Many years ago, my then-wife was in Special Education.
She asked me how many addition problems would total 5.
I did some scribbling and came up with the formula.
I proudly announced 2^4 = 16 problems and listed them.

Then she asked how many if permutations were not allowed.
I spent the rest of the weekend and got nowhere. .On Monday,
I gave the problem to my fellow math professors. .Within
weeks we had huge spreadsheets and vainly tried find the
underlying pattern.

After several months, I gave up and wrote to Martin Gardner.
He replied that the problem was solved in the 1930's (virtually
yesterday!) and gave me reference. .I finally found the book
at the Boston Public Library. .There is a recurrence relation,
but it was very complicated, being quadratic in form.

The notes are somewhere in my vast archives. .(My wife says
they are half-vast. . I think that's what she said.)

Good luck in your search.