

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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$.

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

Your Answer


