# Expressing a positive integer as a sum of positive integers

I am trying to find a way for the positive integers written as the sum of other positive integers.( expressed in terms of some functions)

I searched a bit and I came across with Partitions But in my case the order matters. What I mean is for example if we write for 4, there would be 7 ways to express 4 as;

         1 + 3

2 + 2

3 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 1 + 1 + 1


Can anyone guide me in approaching to the solution of my problem? Thanks in advance.

-
What happens when you go from $4$ to $5$? Can you express the number of sums for a given $n$ using, say, an exponential function? – abiessu Dec 5 '13 at 3:14
What do you mean? The same procedure will apply, but the ways to express 5 as a sum of other positive integers will increase? – Bledi Boss Dec 5 '13 at 3:16

From the standard point of view, you have left out plain $4$. If we allow it, we have $8$ ways of doing the job.

Think of our positive integer $n$ as given by $n$ stars, like this: $$\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast.$$ There are $n-1$ "gaps" between these $n$ $\ast$.

We will choose $0$ or more of these gaps to put a separator into. So at each gap, we say yes or no to inserting a separator.

The number of ways to say yes/no is the number of ways to express $n$ as the ordered sum of $1$ or more positive integers. So there are $2^{n-1}$ ways to do it, $2^{n-1}-1$ if, like you did, one does not accept plain undivided $n$ as an option.

A division of $n$ as an ordered sum of $1$ or more positive integers is called a composition of $n$. For a further discussion, and references, please see this Wikipedia article.

Remark: There is a natural one to one correspondence between compositions of $n$ and $n-1$ bit numbers. That may give a useful way of generating the compositions of $n$.

-
I left it intentionally because in my problem it is excluded. Thanks for the answer – Bledi Boss Dec 5 '13 at 3:18