I'm struggling to prove this as I'm not sure how to do so with words/equations as opposed to visually. $p^2(n,k)$ denotes the number of partitions of n having exactly k parts with each part greater than or equal to 2
Asked
Active
Viewed 198 times
-2
-
Ramanujan and Hardy constructed a formula to find partitions. Although it is large, it might do the trick? – Mr Pie Apr 12 '18 at 15:13
-
I don't need the partitions specifically, just the proof that this theorem is accurate – Demi Townson Apr 12 '18 at 15:50
1 Answers
0
Consider two cases for the partitions counted by $p(n,k)$:
the partition has at least one 1, or
each part of the partition is 2 or more.
The type 2 partitions are exactly counted by your $p^2(n,k)$ (although the notation makes me shudder). To show that $p(n-1,k-1)$ counts the type 1 partitions, use the following bijection.
- Given a type 1 partition, delete the last 1 (we are guaranteed there is at least one 1). This leaves a partition of $n-1$ with $k-1$ parts.
- Given a partition counted by $p(n-1,k-1)$, add a $k$th part 1 at the end* to produce a $k$ part partition of $n$ which, by construction, has at least one 1.
*One has to be careful about adding parts to a partition, e.g., putting a 2 at the end of (3, 1) would not work. But adding a 1 is always OK.
Brian Hopkins
- 2,257