2
$\begingroup$

I came across an interesting problem the other day.

Let $P_n$ be the number of partitions of a positive integer $n$. For instance $P_4$ = $5$, as there are five ways of partitioning $4$:

  • $4$
  • $3+1$
  • $2+2$
  • $2+1+1$
  • $1+1+1+1$

Prove that $P_n$ < $\sqrt{P_{n(n+2)}}$.

The way I tried to prove this is by bounding $P_n$ from above by some function $F(n)$ and bounding $P_{n(n+2)}$ from below by some function $G(n)$ such that $(F(n))^2$ < $G(n)$. Unfortunately, I wasn't able to find bounds that would satisfy the inequality. How to go about proving this?

$\endgroup$
1
  • $\begingroup$ Can you use the asymptotic formula? $\endgroup$
    – Will Fisher
    Jul 11, 2017 at 3:14

1 Answer 1

Reset to default
2
$\begingroup$

You want to prove that $P_n^2<P_{n^2+2n}$. Consider Ferrers diagrams. Start with an $n$-by-$n$ square, and put Ferrers diagrams of partitions of $n$ to the right and below.

$\endgroup$
2
  • $\begingroup$ I figured a possible solution might have something to do with Ferrers diagrams, but I still not quite get how to go about representing $P_{n}^2$... $\endgroup$
    – shooqie
    Jul 11, 2017 at 20:46
  • $\begingroup$ @shooqie, maybe it's more obvious if you generalise to $P_a P_b \le P_{ab+a+b}$ (with equality only when either $a$ or $b$ is zero): for each partition of $a$ and partition of $b$ you can build the Ferrers diagram with an $a\times b$ rectangle, placing the partition of $a$ below it and the partition of $b$ to the right. $\endgroup$
    – Peter Taylor
    Jul 14, 2017 at 11:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .