Proof number-partitions $P_n = \sum_{k=1}^{n} P_{n,k}$ in positive summands

binomial-coefficientscombinatorics

Let $n \in \mathbb{N}$. Let $P_n$ be the number of number-partitions of $n$ in positive summands, i.e. $$P_n = \sum_{k=1}^{n} P_{n,k}$$

How can one prove the following?

  1. The amount of number-partitions of an even number $n$ in positive summands (which are all even) is $P_{n/2}$

  2. The amount of number-partitions of an even number $n$ in positive summands, in which every summand has an even multiplicity, is $P_{n/2}$

  3. The amount of number-partitions of $n$ in positive summands, which are all at least $2$, is $P_n – P_{n-1}$

I know that $$P_{n,k} = P(n-k,k)+P(n-1, k-1)$$ and the following picture shows example values of $P_{n,k}$

enter image description here

For example $P_{8,4}=5$, because

$$2+2+2+2 = 8 \\ 1+1+3+3 = 8 \\ 1+2+2+3 = 8 \\ 1+1+2+4 = 8 \\ 1+1+1+5 = 8$$

And I also know that $P_{n,n} = 1$, because $1+…+1 = n$ is the only number partition. As well as $P_{n,n-1} = 1$, because $1+…+1+2 = n$ is the only number partition.

And for all natural numbers $n$ and $k$ with $1 < k < n$ we have $$P_{n,k} = \binom{n-1}{k-1}$$

I tried to prove it, but even with the given information I don't really know how to do it.

Best Answer

We can use combinatorial arguments here.

  1. Given a partition of $2n$ into even summands, you can recover a partition of $n$ into any summands by just taking half of each summand. For example, $8 = 2 + 2 + 4 \mapsto 1 + 1 + 2 = 4$. It shouldn't be too hard to show that this actually defines a bijection between the sets.
  2. Similarly, given a partition of $2n$ where each summand appears an even number of times, just take one copy of each to get a partition of $n$. For example, $8 = 1 + 1 + 3 + 3 \mapsto 1 + 3 = 4$.
  3. Consider an arbitrary partition of $n$. Either all of its summands are at least 2, or at least one of them is equal to 1. The total count over both of these cases is $P_n$. But the latter case can be counted by noticing that removing one of the summands equal to 1 defines a partition of $n-1$. Again, it should be clear that this is a bijection, so there are $P_{n-1}$ partitions of the latter form. This gives that the number of partitions of the first variety is simply $P_n - P_{n-1}$.
Related Question