# Number of ways of expressing $n$ as a sum of positive integers

a) Let $s_n$ denote the number of ways of expressing $n$ as a sum of positive integers. Thus $s_1=1$, $s_2=2$, and $s_3=4$ (the four ways are $3$, $2+1$, $1+2$, and $1+1+1$). Prove that $s_n=s_{n-1}+s_{n-2}+\cdots+s_1+1$. Hence calculate $s_{10}$. Find a formula for $s_n$ in terms of $n$.

b) Suppose that we decide not to distinguish between '$1+2$' and '$2+1$'; Let $\sigma_n$ denote the number of ways of expressing $n$ as a sum of positive integers when the order of the terms does not matter. Thus $\sigma_3=3$. Calculate $\sigma_n$ ($1\leqslant n\leqslant 6$). Find $\sigma_{10}$. Express the $n$th term $\sigma_n$ in terms of earlier terms. Then try to find a formula for $\sigma_n$ in terms of $n$.

I need help on part (b). I've done part (a), which was easy enough ($2^{n-1}$).

I'm struggling to find a formula for $\sigma_n$ though.

This is an exercise from "The Mathematical Olympiad Handbook - An introduction to problem solving".

-
This is the number of partitions of $n$. You will not find a nice closed form formula. – André Nicolas Nov 6 '13 at 19:11

As Andre pointed no nice closed form but exists a beautiful recurrence given by Euler $$p(k)=\sigma_k=\sum_{d=1}^{\infty}(-1)^{d+1}\left(p\left(k-\frac{d(3d-1)}{2}\right)+ p\left(k-\frac{d(3d+1)}{2}\right)\right)$$
If I'm not mistaken this gives the number of groups up to isomorphism for a given number n. For example $\mathbb{Z}_{32}$ is isomorphic to $\mathbb{Z}_{(2)^1} \times \mathbb{Z}_{(2)^4}$ and to 6 others because there are 7 different ways to sum to 5 without regard to order. Does anyone have any additional insights into this relationship? – Greg B. Hill Feb 25 '15 at 14:17