0
$\begingroup$

Let $n\geq 4$. Prove that the number of partitions of $n$ into 4 parts equals the number of partitions of $3n$ into 4 parts of size at most $n-1$.

I am stuck on this problem but I suspect I need to establish a bijection by possibly looking at the conjugate of the Ferrer's diagram. Thanks for any help.

$\endgroup$
  • $\begingroup$ What have you tried so far? $\endgroup$ – platty Dec 5 '18 at 17:42
  • 1
    $\begingroup$ You have asked enough questions here to know that the right way to ask for help is to edit this one to show us what you tried and where you are stuck. $\endgroup$ – Ethan Bolker Dec 5 '18 at 17:43
  • 4
    $\begingroup$ Hint: A quadruple $(x_1,x_2,x_3,x_4)\in\mathbb{Z}_{>0}^4$ with $x_1\leq x_2\leq x_3\leq x_4$ partitions $n$ if and only if $(n-x_4,n-x_3,n-x_2,n-x_1)$ partitions $3n$. $\endgroup$ – Batominovski Dec 5 '18 at 17:46
0
$\begingroup$

Proof: Let $n\geq 4$. The number of partitions of $n$ into 4 parts is a solution to the system $x_1+x_2+x_3+x_4=n$ for $x_1\geq x_2\geq x_3\geq x_4\geq 1$. Let $y_1=n-x_4$, $y_2=n-x_3$, $y_3=n-x_2$, and $y_4=n-x_1$. We know that $x_1\geq x_2\geq x_3\geq x_4\geq 1$ which implies $-x_1\leq -x_2\leq -x_3\leq -x_4\leq -1$ and thus $n-x_1\leq n-x_2\leq n-x_3\leq n-x_4\leq n-1$. So, $1\leq y_4\leq y_3\leq y_2\leq y_1\leq n-1$. Hence $y_1+y_2+y_3+y_4=4n-(x_1+x_2+x_3+x_4)=4n-n=3n$ which yields a solution to the number of partitions of $3n$ into 4 parts of size at most $n-1$. Thus there is a bijection between the system $y_1+y_2+y_3+y_4=3n$ for $n-1\geq y_4\geq y_3\geq y_2\geq y_1\geq 1$ and the system $x_1+x_2+x_3+x_4=n$ for $x_1\geq x_2\geq x_3\geq x_4\geq 1$. Therefore, the number of partitions of $n$ into 4 parts equals the number of partitions of $3n$ into 4 parts of size at most $n-1$.

$\endgroup$

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.