Series for constructing integers

Question

I'm not sure about the proper terminology for what I'm asking, so bear with me:

I want to list all ways one can generate an arbitrary integer from positive multiples of the integers less than and including its self. For example...

1=1*(1)
2=2*(1) or 1*(2)
3=3*(1) or 1*(1)+1*(2) or 1*(3)
4=4*(1) or 2*(1)+1*(2) or 2*(2) or 1*(1)+1*(3) or 1*(4)
...

Is there a name for these types of combinations? How would one go about generating all of the combinations for an arbitrary integer, aside from by brute force? Is there a way to know, a priori, how many such combinations exist for an arbitrary integer?

Answer 1

These are known as partitions. They are usually described not in terms of multiples as you have done, but simply as all ways to write a nonnegative integer $n$ as a sum of positive integers (ignoring order). This is equivalent since you can group together all copies of the same integer in the sum; for instance, the partition $4=2+1+1$ corresponds to your expression $4=1\cdot 2+2\cdot 1$.

The number of partitions of a nonnegative integer $n$ is written $p(n)$. There is no nice closed formula for $p(n)$, but this function has been very extensively studied. You can find a lot of basic information on the Wikipedia page linked above. For instance, $p(n)$ is known to be asymptotic to $\frac{\exp(\pi\sqrt{2n/3})}{4n\sqrt{3}}$ when $n$ is large.

Answer 2

Using the fact that $$ \sum_{n=0}^\infty p(n)x^n=\frac{1}{\prod_{i\geq1}(1-x^i)}\tag{1} $$ and the pentagonal theorem $$ \prod_{i\geq 1}(1-x^i)=\sum_{n\geq1}(-1)^n(x^{n(3n-1)/2}+x^{n(3n+1)/2}) $$ the relation $$ \left(\sum_{n\geq1}(-1)^n(x^{n(3n-1)/2}+x^{n(3n+1)/2})\right)\left( \sum_{n=0}^\infty p(n)x^n \right)=1 $$ implies that for $n>0$, one has the recurrece relation $$ p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\dotsb\tag{2} $$ with the understanding that $p(n)=0$ for $n<0$. Equation (2) gives a way to compute $p(n)$ recursively.