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.

  • 1
    $\begingroup$ That's not what I call partitions. $\endgroup$ – Lord Shark the Unknown Oct 22 '18 at 17:23
  • $\begingroup$ ok. any other suggestions? $\endgroup$ – Memories Oct 22 '18 at 17:25
  • $\begingroup$ 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. $\endgroup$ – Michael Lugo Oct 22 '18 at 17:26

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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