1

For example if I take $n=5$, then I can express it in the following ways:

  1. $1+1+1+1+1$
  2. $2+3$
  3. $3+2$
  4. $1+4$
  5. $4+1$
  6. $1+1+3$
  7. $1+3+1$
  8. $3+1+1$
  9. $2+2+1$
  10. $2+1+2$
  11. $1+2+2$

Please note that the order of terms in the expression of summation also counts if the terms are distinct.

Roby5
  • 4,287
ThePhysicist
  • 189
  • 9

3 Answers3

3

Take the string $ \large 1{\boxed.} 1\boxed. 1\boxed. 1\boxed. 1$

In the $\;(n-1)\;$ boxes, either put a $+\;$ or a comma.

$1,\;\;1,\;\;1+1+1$ e.g. would represent $1+1+3$

Since you have $2$ choices for each box, # of compositions = $2^{n-1}$

but as you have specified positive integers less than $n$, ans = $2^{n-1} - 1 = 2^4 -1 = 15$

1

If we count plain $n$ as a legitimate expression, there are $2^{n-1}$.

In general, let $a_n$ be the number of ways to decompose $n$. We show that $a_{n}=2^{n-1}$. The proof is by induction on $n$. Clearly $a_1=1$.

There are two types of compositions of $n+1$: (i) the ones that end with $1$ and (ii) the ones that end with a number $\ge 2$.

The Type (i) compositions of $n+1$ are obtained by appending a $1$ to a composition of $n$. By the induction hypothesis, there are $2^{n-1}$ Type (i) compositions of $n+1$.

The Type (ii) compositions of $n+1$ are obtained by adding $1$ to the last entry of a composition of $n$. There are $2^{n-1}$ of these.

This gives a total of $2^n$, and completes the induction step.

Remark: If we break with tradition and do not allow plain $n$, the number of ways to decompose $n$ is $2^{n-1}-1$.

André Nicolas
  • 507,029
0

We can also do this by finding the number of ordered partitions of $n$ into exactly $r$ parts and then summing them over from $1$ to $n$.

When we have exactly $r$ partitions of $n$, we have the generating function $(x+x^2+x^3+...)^r=x^r/(1-x)^r$

Now, we must pick the coefficient of $x^n$ from $x^r[1+\binom{r}{1}x + \binom{r+1}{2} x^2 +.....+ \binom{r+(n-r-1)}{n-r}x^{n-r}+....]$

which is $\binom{n-1}{r-1}$

This is the general expression for orders partition of $n$ into $r$ parts. To find all partitions we must evaluate

$\sum_{i=1}^n \binom{n-1}{r-1} = \binom{n-1}{0} + \binom{n-1}{1} + \binom{n-1}{2} +....+ \binom{n-1}{n-1}$

Considering the binomial expansion of $(1+x)^{n-1}$, we have

$\binom{n-1}{0} + \binom{n-1}{1}x+ \binom{n-1}{2}x^2 +....+ \binom{n-1}{n-1}x^{n-1}$

Putting $x=1$ in the above expression,we get

$\sum_{i=1}^n \binom{n-1}{r-1} =(1+1)^{n-1}=2^{n-1}$

But this also contains the partition of the form $n=n$, which is not allowed.So required number of partitions is $2^{n-1} -1$.


For this question with $n=5$, total number of required partitions is

$2^{5-1}-1=2^4-1=15$

Roby5
  • 4,287