# Combinatorial proof of ${2n\choose n}n!\le (2n)^{n}$

Initially I was supposed to prove the proposition $$n^n\ge \prod_{r=1}^{r=n}(2r-1)\forall n\in\mathbb{N}$$. So I have basically simplified this question down to proving $${2n\choose n}n! \le (2n)^{n}$$ by carrying out the following operations.

\begin{aligned}n^{n}\prod_{r=1}^{n}2r&\ge \prod_{r=1}^{n}(2r-1)\prod_{r=1}^{n}2r\\ 2^{n}n^nn!&\ge(2n)!\\ (2n)^{n}&\ge {2n\choose n}n!\end{aligned}

Any ideas on how to prove this inequality. The right side of the inequality represents the arrangement of $$n$$ objects chosen out of $$2n$$ object. And the left side represents the arrangement of $$n$$ objects into $$2n$$ vacancies. Any hints are appreciated. Thanks.

The lefthand side of the inequality in the title is the number of ways to put $$n$$ balls numbered $$1$$ through $$n$$ into $$2n$$ slots numbered $$1$$ through $$2n$$ if no slot is allowed to contain more than one ball. The righthand side is the number of ways to put the same $$n$$ balls into the same $$2n$$ slots with no restrictions on how many balls can occupy any slot.

Consider the ratio:

$$\frac{2n \times 2n \times 2n \times \cdots \times 2n} {(2n) \times (2n-1) \times (2n-2) \times \cdots \times (2n + 1 - n)}.$$

Clearly, the numerator is bigger than the denominator.

• You do have to rewrite $\binom{2n}{n}n!$ as a product whose terms can be paired with the terms of $(2n)^n$ (written as a product), which is some degree of insight for a newcomer.
– anon
Commented Jan 7, 2021 at 6:08
• @runway44 fair point, and normally conclusive. However, the OP's query shows work that demonstrates comparable insight. Commented Jan 7, 2021 at 6:14

Let $$X = [n] = \{1,2,\ldots,n\}$$, and $$Y = [2n] = \{1,2,\ldots ,2n\}$$.

Observe that $$(2n)^n$$ is the number of functions $$f:X\to Y$$. Indeed, for each $$i\in X$$, you have $$2n$$ choices to assign $$f(i)$$.

Next, note $${2n \choose n}n!$$ is the number of injective functions $$f:X\to Y$$. Indeed, for an injective (one-to-one) function, we first pick an image for $$f$$, which is a size $$n$$ subset of $$Y$$. There are $$2n\choose n$$ many ways. Now with the image chosen, we have $$n!$$ ways to assign them to $$f(i)$$.

Since the set of all injective functions is a subset of all functions $$X\to Y$$, we have the desired inequality.

Note: In general $${|Y| \choose |X|} |X|!$$ is the number of injective functions $$X\to Y$$ (whenever sensible), while $$|Y|^{|X|}$$ is the total number of functions $$X\to Y$$.