Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.