Is it true that $ \binom{n}{k}^2 \le \binom{n^2}{k} $?

Question

Is it true that $ \binom{n}{k}^2 \le \binom{n^2}{k} $?

I checked this for $k=1,n-1,n-2$. Is there an easy way to prove this for general $1 \le k \le n-1$?

Answer 1

We have $$ \binom{n}{k}^2 = \frac{n^2(n-1)^2\cdots(n-k+1)^2}{k!^2}\\ \binom{n^2}{k} = \frac{n^2(n^2-1)(n^2-2)\cdots(n^2-k+1)}{k!} $$ and we observe the following two things:

• The two numerators have the same number of factors, and apart from $n^2$, every single factor in the first fraction is smaller than the corresponding factor in the second fraciton, thus the first numerator is smaller than the second numerator (the first fraction counts consecutive square numbers down from $n^2$, while the second fraction counts consecutive integers)
• The denominator in the first fraction is clearly larger than the denominator in the second fraction

So the first fraction has a smaller numerator and a larger denominator than the second, which makes it clear that the fraction itself is also smaller.

Edit: Combinatorial proof

Take an $n\times n$ square grid of cells. Then $\binom{n^2}k$ is the number of ways to pick $k$ of those cells, without any restrictions.

Now, let's impose the restriction that no chosen cell can be in the same row or column as another chosen cell. That reduces the possible number of ways to choose. And let's instead just care about which rows and which columns have a chosen cell somewhere in them. That's even fewer, since any given arrangement of $k$ rows and $k$ columns corresponds to a number of different choices of cells ($k!$ different choices, to be exact).

The number of ways to choose $k$ rows and $k$ columns is $\binom nk^2$.

Answer 2

We need to prove that $$\frac{\prod\limits_{i=0}^{k-1}(n^2-i)}{k!}\geq\frac{\prod\limits_{i=0}^{k-1}(n-i)^2}{(k!)^2}$$ or $$\prod_{i=0}^{k-1}\frac{(n-i)^2}{n^2-i}\leq k!$$ or $$\prod_{i=0}^{k-1}\frac{(n-i)^2}{n^2-i}\leq \prod_{i=0}^{k-1}(i+1),$$ for which it's enough to prove that $$\frac{(n-i)^2}{n^2-i}\leq i+1,$$ which is $$i(n^2+2n-2i-1)\geq0,$$ which is obvious.