Inequality proof involving multinomial coefficients

Question

How may I proceed to prove/disprove following inequality?

$$\frac{n^n}{p_1^{p_1}\cdot p_2^{p_2}\cdots p_k^{p_k}}>\frac{n!}{p_1! p_2!\cdots p_k!} $$ where $\sum_{i=1}^k p_i=n$

It seems, using Stirling approximation I need to show that $\sqrt{\frac{p_1 +p_2+...+p_k}{p_1 .p_2...p_k}(2\pi)^{1-k}}$ is less than one for all $n$ and $p_i$.

Answer 1

Shorter proof :

The inequality is :

$$(p_1+p_2+\ldots+p_k)^{n} > \binom{n}{p_1,p_2,\ldots,p_k} p_1^{p_1} \cdot p_2^{p_2} \cdot \ldots \cdot p_k^{p_k}$$

which is true because the RHS term appears in the multinomial expansion of $(p_1+p_2+\ldots+p_k)^{n}$

Longer proof (basically equivalent with the shorter) :

Let $f(x)=\frac{x^x}{x!}$ with $x \in \mathbb{N}$ .

We need to prove that $$f(p_1)f(p_2)\ldots f(p_k) < f(n)$$

So it suffices to prove it for two numbers :

$$f(x)f(y) < f(x+y)$$ and then we can repeatedly apply this to get the general case :

$$f(p_1)f(p_2)\ldots f(p_k) < f(p_1+p_2)f(p_3)\ldots f(p_k) < \ldots <f(p_1+p_2+\ldots +p_k)=f(n)$$

All we need to prove is thus :

$$\frac{x^x y^y}{x! y!} < \frac{(x+y)^{x+y}}{(x+y)!}$$

$$\binom{x+y}{y}x^xy^y <(x+y)^{x+y}$$ which is true because $\binom{x+y}{y}x^xy^y $ is one of the terms in the binomial expansion of $(x+y)^{x+y}$.

Answer 2

Taking logarithms and reshuffling terms turns your inequality into the equivalent

$$\ln(n^n/n!) ~>~ \sum_{i=1}^k \ln(p_i^{p_i}/p_i!)$$ where $\sum_{i=1}^k p_i=n$ and $k\ge2$.

Hence it will be sufficient to show that $f(x)=\ln(x^x/x!)$ is super-linear; that is, that $f$ satisfies $f(a+b)>f(a)+f(b)$.