If $n$ is a natural number $\geq 2$, how many ways are there to partition $n$ with natural numbers $\geq 2$?

Question

The partitions are "ordered", meaning that for 5, from (2,3), (3,2) and (5) all are valid.

So for the first few numbers one gets:

 2   3   4     5     6       7
(2) (3) (2,2) (2,3) (2,2,2) (2,2,3)
        (4)   (3,2) (2,4)   (2,3,2)
              (5)   (3,3)   (2,5)
                    (4,2)   (3,2,2)
                    (6)     (3,4)
                            (4,3)
                            (5,2)
                            (7)

In other words, the total number of ways to partition $n$ is $\text{Fibonacci}(n-2)$, but why? I get why there have to be at least as many possibilities for $n$ as there are for $n-1$, but what is the conceptual argument for also $n-2$?

Answer 1

(These are actually compositions, not partitions.) You get one composition of $n$ by adding $1$ to the last element of each composition of $n-1$; you also get one by appending a last part $2$ to each composition of $n-2$. The resulting sets of compositions of $n$ don’t overlap: each one in the first set has a last element that is at least $3$, while those in the second set all have last element $2$.

To put it a little differently, you can decompose the compositions of $n$ into parts greater than $1$ into those that end in $2$ and those that end in a number greater than $2$. The ones that end in $2$ are obtained by appending $2$ to any acceptable composition of $n-2$. The onees that end in a number greater than $2$ are obtained by adding $1$ to the last element of some acceptable composition of $n-1$. Every acceptable composition of $n$ arises in exactly one of these two ways.

Answer 2

Hint: You can produce the list for $8$ by appending $2$ to each entry in the list for $6$ and adding $1$ to the final number in each entry in the list for $7$.