5
$\begingroup$

I am having a bit of trouble beginning the following:

Prove that for all positive integers $n$, the inequality $p(n)^2<p(n^2+2n)$ holds, where $p(n)$ is defined as the number of all partitions of $n$.

I initially considered weak induction on n, but am not sure if that is the correct way to begin. Is there an alternate, stronger path (such as a combinatorial proof) I should consider? I feel like I'm making this more difficult than it should be, and I apologize if this is the case.

Thank you in advance!

$\endgroup$
10
$\begingroup$

If you know what a Young diagram is and how it relates to partitions, here's a neat argument:

Take a $n$ by $n$ box and put a Young diagram partitioning n on the right side, and one underneath it. What do you get? a Young diagram partitioning $n^2 + 2n$. What if you take the box away? You get a pair of Young diagrams each partitioning $n$. This gives an injection of pairs of $n$ partitions into partitions of $n^2 + 2n$

If you don't know about Young diagrams ( you should learn them! They're really interesting, fun, and important ), the same argument can be made less geometrically. Take any two partitions of $n$ and add $n + n + n + \ldots + n$ ( $n$ added $n$ times ) to the first partition. What you get is a partition of $n^2 + n$ with parts all greater than or equal to $n$, so you just add your other partition of $n$ to that, and you get a partition of $n^2 + 2n$. It's not too hard to see this algorithm is injective.

Example where $n = 6$ $$ f = 3 + 2 + 1 $$ $$ g = 3 + 3 $$ $$ h = 9 + 8 + 7 + 6 + 6 + 6 + 3 + 3 $$

So $f$ and $g$ are partitions of $n$ and $h$ is a partition of $n^2 + 2n$ formed in the way described above.

Really the Young diagram version is cuter though!

Oh, to get strict inequality, just take the partition which is all ones of $n^2 + 2n$

$\endgroup$
  • $\begingroup$ That was an excellent answer! I'm familiar with Young diagrams (via Ferrers diagrams), but I'm glad you provided proofs both with and without them. Thank you very much! $\endgroup$ – Spectre Sep 27 '13 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.