1
$\begingroup$

Given an integer partition of $n$, represented by a Young diagram $\lambda$, we define $s(\lambda)$ as the dimension of the largest square contained in the diagram, that includes the leftmost box in the top row. I think this is also called a Durfee square. Let $f_k (n)$ denote the number of partitions $\lambda$ of $n$, such that $s(\lambda)=k$. Prove that $f_k (n) \leq \frac{n^{2k}}{(k!)^2}$.

I found an identical question here: Number of partitions of $n$ with Durfee square of size $k$ , but I coudn't understand the answer.

My first observation was the following. By using the transpose transformation, we can show that the number of ways to place all the $n-k^2$ boxes under the Durfee square is equal exactly to the number of ways to place all them to the right of the Durfee square. So, firstly we can try to count how many ways there are to put $n-k^2$ boxes under the Durfee square. Later, we can count how many ways there are to choose a subset of rows, transpose each of them, and move it to the right of the Durfee square. This approach led me to a dead end.

My second attempt was to do as follows. Let $x_1,x_2,...,x_k$ denote the number of boxes in the columns $1,2,...,k$ respectively, that are placed under the Durfee square (namely in rows $k+1,...,n$). Let $y_1,y_2,...,y_k$ denote the number of boxes in the rows $1,2,...,k$ respectively, that are placed to the right of the Durfee square (namely in columns $k+1,...,n$). Then, for every valid partition we have: $$ x_1 +\cdots +x_k+y_1 + \cdots + y_k==n-k^2 \\ x_1 \geq x_2 \geq \cdots \geq x_k \\ y_1 \geq y_2 \geq \cdots \geq y_k $$

The number of solutions to $x_1 +\cdots +x_k+y_1 + \cdots + y_k=n^2-k$ is well known as $\binom{2k+(n-k^{2})-1}{2k-1}=\binom{n-k^{2}+2k-1}{2k-1}$. Also, it is clear that if we ommit the constraints $$ x_1 \geq x_2 \geq \cdots \geq x_k \\ y_1 \geq y_2 \geq \cdots \geq y_k $$ we will still get an upper bound.

I would appreciate any help solving this problem.

$\endgroup$
1
$\begingroup$

Hint

In order to count nonnegative integer solutions to... $$ x_1 +\cdots +x_k+y_1 + \cdots + y_k=n-k^2 \\ x_1 \leq x_2 \leq \cdots \leq x_k \\ y_1 \leq y_2 \leq \cdots \leq y_k $$ introduce new variables $x_i'$ and $y_i'$, defined by $$ x_i'=x_i+(i-1),\qquad y_i'=y_i+(i-1),\qquad i\in \{1,\dots,k\}. $$ These new variables satisfy $$ x_1' +\cdots +x_k'+y_1' + \cdots + y_k' = n-k \\\tag{*} x_1' < x_2' < \cdots < x_k' \\ y_1' < y_2' < \cdots < y_k' $$ Without the inequality constraints, the number of solutions would be $$\binom{n-k+2k-1}{2k-1}=\binom{n+k-1}{2k-1}.$$ Now, since the values $x_1',\dots,x_k'$ are distinct, and similarly for $y_1',\dots,y_k'$, you can safely divide the number of unconstrained solutions to $x_1' +\cdots +x_k'+y_1' + \cdots + y_k' = n-k$ by $(k!)^2$ to get the number of solutions to $(*)$. Therefore, you get the upper bound $$ \frac1{(k!)^2}\binom{n+k-1}{2k-1} $$ and you just need to show this is at most $\frac{n^{2k}}{k!^2}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much! This is a very beautiful solution. $\endgroup$ – Ido Jun 24 at 20:31
  • $\begingroup$ I am not sure I understand why it is safe to divide $\binom{n+k-1}{2k-1}$ by $(k!)^2$. I understand that given the fact $y_1 '< y_2 '< \cdots <y_k '$ and given the fact $x_1' < x_2 '<\cdots < x_k'$ it is safe to divide by $k!$ twice. However, the number $\binom{n+k-1}{2k-1}$ also counts assignments of $y_1',...,y_k',x_1',...,x_k'$ such that there exist some $i,j$ for which $x_i'= x_j'$ or $y_i' = y_j'$... In this case it seems like dividing by $k!$ is wrong. $\endgroup$ – Ido Jun 24 at 20:43
  • $\begingroup$ @Ido When you divide by $(k!)^2$, you will get the number of solutions to $(*)$, plus some extra fractional stuff resulting from the fact that $\binom{n+k-1}{2k-1}$ includes solutions with two variables equal. But having extra fractional stuff is OK, because we just want an upper bound. $\endgroup$ – Mike Earnest Jun 24 at 21:54

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.