While solving PE and reading SICP I found, that there are two problems, that produce the same OEIS sequence:
http://oeis.org/A001399 is a number of partitions of n into at most 3 parts
http://oeis.org/A069905 is a number of partitions of n into 3 positive parts
My questions are:
- how to prove, that they are equivalent?
- are they equivalent for n > 3?
If you look more closely, you’ll see that they aren’t identical: the indices are offset by $3$. Let $a_n$ be the number of partitions of $n$ into at most $3$ parts, and let $b_n$ be the number of partitions of $n$ into $3$ positive parts; then $a_n=b_{n+3}$.
This is actually quite easy to see. Let $\mathscr{P}_n$ be the set of partitions of $n$ into at most $3$ parts, and let $\mathscr{P}_n^*$ be the set of partitions of $n$ into $3$ positive parts. For each $\pi\in\mathscr{P}_n$ let $\hat\pi$ be the partition of $n+3$ obtained by adding $1$ to each part of $\pi$; clearly $\hat\pi\in\mathscr{P}_{n+3}^*$, and the map $\pi\mapsto\hat\pi$ is injective. Conversely, if $\pi\in\mathscr{P}_n^*$, let $\pi'$ be the partition obtained by subtracting $1$ from each part of $\pi$. Clearly $n\ge 3$, $\pi'\in\mathscr{P}_{n-3}$, and the map $\pi\mapsto\pi'$ is also injective. Finally, $(\hat\pi)'=\pi$ for each $\pi\in\mathscr{P}_{n-3}$, so these maps are bijections.