Return to Answer

Let $C_k$ be the set of partitions of $n$ containing $k$.

Following @MaxAlekseyev's point we have, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ This is the # of partitions containing both 1 and 2, minus the # of partitions containing neither 1 nor 2.

This number is nonnegative since to any partition containing neither 1 nor 2, writing it in nonincreasing order as $t_1,\dots, t_k$, we can associate the partition $t_1,\dots,t_k-3,2,1$ which does contain 1 and 2 (and this map is one-to-one).

Thus for $n\ge 4$ certainly, $P(n-1)+P(n-2)-P(n)$ is exactly counting

how many partitions of $n$ contain both 1 and 2, and are not of the form $t_1,\dots,t_{k-1},t_k-3,2,1$ where $t_1\ge\dots\ge t_k\ge 3$.

For $n=5$, this includes only one: $2+1+1+1$.

Let $C_k$ be the set of partitions of $n$ containing $k$.

Following @MaxAlekseyev's point we have, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ This is the # of partitions containing both 1 and 2, minus the # of partitions containing neither 1 nor 2.

This number is nonnegative since to any partition containing neither 1 nor 2, writing it in nonincreasing order as $t_1,\dots, t_k$, we can associate the partition $t_1,\dots,t_k-3,2,1$ which does contain 1 and 2 (and this map is one-to-one).

Thus for all $n$, $P(n-1)+P(n-2)-P(n)$ is exactly counting

how many partitions of $n$ contain both 1 and 2, and are not of the form $t_1,\dots,t_{k-1},t_k-3,2,1$ (removing $t_k-3$ if it is 0) where $t_1\ge\dots\ge t_k\ge 3$.

For $n=5$, this includes only one: $2+1+1+1$.

Let $C_k$ be the set of partitions of $n$ containing $k$.

Following @MaxAlekseyev's point we have, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ This is the # of partitions containing both 1 and 2, minus the # of partitions containing neither 1 nor 2.

This number is nonnegative since to any partition containing neither 1 nor 2, writing it in nonincreasing order as $t_1,\dots, t_k$, we can associate the partition $t_1,\dots,t_k-3,2,1$ which does contain 1 and 2 (and this map is one-to-one).

Thus $P(n-1)+P(n-2)-P(n)$ is exactly counting

how many partitions of $n$ contain both 1 and 2, and are not of the form $t_1,\dots,t_{k-1},t_k-3,2,1$ where $t_1\ge\dots\ge t_k\ge 3$.

For $n=5$, this includes only one: $2+1+1+1$.

Let $C_k$ be the set of partitions of $n$ containing $k$.

Following @MaxAlekseyev's point we have, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ This is the # of partitions containing both 1 and 2, minus the # of partitions containing neither 1 nor 2.

This number is nonnegative since to any partition containing neither 1 nor 2, writing it in nonincreasing order as $t_1,\dots, t_k$, we can associate the partition $t_1,\dots,t_k-3,2,1$ which does contain 1 and 2 (and this map is one-to-one).

Thus for $n\ge 4$ certainly, $P(n-1)+P(n-2)-P(n)$ is exactly counting

how many partitions of $n$ contain both 1 and 2, and are not of the form $t_1,\dots,t_{k-1},t_k-3,2,1$ where $t_1\ge\dots\ge t_k\ge 3$.

For $n=5$, this includes only one: $2+1+1+1$.

It's counting the partitions $t_1+\dots+t_k$, of $n-2$ such that neither of (1), (2) hold:

1. Adding 2 to some term $t_i$, where $t_i+2\ge t_j$ for all $j$, produces a special partition of $n$.
2. $n$ is even and $p$ is the specific partition $(2+2+\dots+2)+1+1$.

Here a special partition is one with no 1 terms (all terms $\ge 2$). [In (2), adding 1 to each of the 1s produces the special partition $2+\dots+2$.]

Examples:

• For $n=4$ we need a partition of $2$, either 2 or $1+1$, but $1+1$ fits condition (2) and 2 fits (1).
• For $n=5$ we have $3=2+1=1+1+1$, and $1+1+1$ does not fit either of (1),(2).
• For $n=6$ we have $4=3+1=2+2=2+1+1=1+1+1+1$. Here $2+1+1$ fits (2), $4$, $2+2$ and $3+1$ fit (1), and only $1+1+1+1$ is left over.
• For $n=7$ we have $5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1$ where $5$, $4+1$, $3+2$ $2+2+1$ fit (1), and the leftover ones are $1+1+1+1+1$, $2+1+1+1$, and $3+1+1$.

Let $C_k$ be the set of partitions of $n$ containing $k$.

Following @MaxAlekseyev's point we have, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ This is the # of partitions containing both 1 and 2, minus the # of partitions containing neither 1 nor 2.

This number is nonnegative since to any partition containing neither 1 nor 2, writing it in nonincreasing order as $t_1,\dots, t_k$, we can associate the partition $t_1,\dots,t_k-3,2,1$ which does contain 1 and 2 (and this map is one-to-one).

Thus $P(n-1)+P(n-2)-P(n)$ is exactly counting

how many partitions of $n$ contain both 1 and 2, and are not of the form $t_1,\dots,t_{k-1},t_k-3,2,1$ where $t_1\ge\dots\ge t_k\ge 3$.

For $n=5$, this includes only one: $2+1+1+1$.