# Number of compositions of a natural number $n \in \mathbb{N}$ with at least two parts.

So I have to show that the number of partitions of $$n \in \mathbb{N}$$ is $$2^{n-1} -1$$. ( the order is important ).

So here is my attempt. Please be strict. If you find any mistake or something that iritates you, let me know:

We rewrite $$n \in \mathbb{N}$$:

$$n = 1 + \cdots + 1$$ .( we sum $$1$$ $$n$$-times). We want to find the number of compositions with at least two parts, so we consider "$$+$$". For each "$$+$$" between the summands we have to decide if the summands are a "new" summand or not. We get $$2^{n-1}$$ decisions. But we don't count the solution $$n = n$$ , so we have $$2^{n-1} -1$$.

What do you say? Remark: Please focus on my work. Thank you in advance.

• That's not what I call partitions. – Lord Shark the Unknown Oct 22 '18 at 17:23
• ok. any other suggestions? – Memories Oct 22 '18 at 17:25
• Partitions where order matters are usually called "compositions". In addition $n$ would usually be considered a composition of itself, so you're looking to count compositions of $n$ with at least two parts. – Michael Lugo Oct 22 '18 at 17:26

## 1 Answer

The wikipedia page https://en.wikipedia.org/wiki/Composition_(combinatorics) confirms both your answer and your argument.