Number of partitions of n with Durfee square of size k

Question

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.

Answer 1

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}$.