Number of partitions of $n$ with Durfee square of size $k$

391 Views Asked by At

Show that the number of partitions of $n$ with Durfee square of size k is $\leq \dfrac{n^{2k}}{(k!)^2}$

I've thought it's equivalent to the number of partitions of $n$ such that $k$ of the numbers are $\geq k$ and the rest of them $\leq k$,
which is equivalent to the number of partitions of $n-k^2$ such that $k$ of the numbers are $\geq 0$ and the rest are $\leq k$.
I got stuck in getting from that to the requested bound.

1

There are 1 best solutions below

2
On

Consider the parts below the Durfee square. Each of these parts is at most $k$ and there are at most $n$ parts, so they contribute at most $\frac{n^k}{k!}$, where we've divided by the $k!$ possible reorderings.

Parts to the right of the Durfee square may be bounded analogously. Thus, together, we get a bound of $$\left(\frac{n^k}{k!}\right)^2.$$