[Math] Expressing a positive integer as a sum of positive integers

combinatoricsdiscrete mathematicsnumber theory

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.

Best Answer

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

Related Question