Inequality involving factorial of sum

Question

I noticed the following inequality involving factorials as a consequence of a statistics exercise: $$ (x_1+\cdots+x_n)!\leq n^{x_1+\cdots +x_n}\,x_1!\,\cdot\cdots\cdot\,x_n!\,, $$ where $x_1,\ldots,x_n$ are nonnegative integers. I thought such a clean inequality would have a name, but wasn't able to find anything on the internet. Can someone provide an elementary proof of it, or at least one that feels more natural than mine?

How I arrived at it: Let $X=(X_1,\ldots,X_n)$ be a random sample from the Poisson($\lambda$) distribution. Consider the statistic $T=X_1+\,\cdots\,X_n\,$. By the superposition property of independent Poisson random variables, $T$ has a Poisson($n\lambda$) distribution. Denoting $t(x)=x_1+\cdots+x_n\,$, the following line shows that $T$ is a sufficient statistic for $\lambda\,$; $$ P\big(X=x\,\big|\,T=t(x)\big)=\frac{P(X=x)}{P\big(T=t(x)\big)}=\frac{\prod_1^nP(X_i=x_i)}{P\big(T=t(x)\big)}=\frac{\big(e^{-\lambda}\big)^n\,\frac{\lambda^{t(x)}}{x_1!\,\cdots \,x_n!}}{e^{-n\lambda}\,\frac{(n\lambda)^{t(x)}}{t(x)!}}=\frac{t(x)!}{n^{t(x)}x_1!\cdots x_n!}\,. $$ As the probability of any event cannot be bigger than one, we must have $t(x)!\leq n^{t(x)}x_1!\cdots x_n!\,$.

Answer 1

Combinatorially, $$\frac{(x_1+\dots+x_n)!}{x_1!\cdots x_n!}$$ is a multinomial coefficient that counts the number of ways to partition a set of size $x_1+\dots+x_n$ into sets of sizes $x_1,\dots,x_n$. On the other hand, $$n^{x_1+x_2+\dots+x_n}$$ counts the number of functions from a set of size $x_1+\dots+x_n$ to a set of size $n$, or equivalently (considering the fibers of such a function) the number of partitions of a set of size $x_1+\dots+x_n$ into $n$ (ordered) subsets. Thus $$\frac{(x_1+\dots+x_n)!}{x_1!\cdots x_n!}\leq n^{x_1+x_2+\dots+x_n}$$ and your inequality follows. This also shows the inequality is strict unless $n=1$ or $x_i=0$ for all $i$, since otherwise there will exist partitions into $n$ subsets where the subsets do not have sizes $x_1,\dots,x_n$.

Answer 2

Imagine you have $n$ labeled boxes and $x_1+x_2+\cdots+x_n$ labeled objects. The multinomial

$$(x_1+x_2+\cdots+x_n)!\over x_1!x_2!\cdots x_n!$$

counts the number of ways you can place $x_k$ objects into box $k$ for $1\le k\le n$, while

$$n^{x_1+x_2+\cdots+x_n}$$

counts the number of ways you can assign a box to each object, which is equivalent to putting objects into boxes with no restriction on the number of objects that go into any of the boxes. With these interpretations, it's clear that

$${(x_1+x_2+\cdots+x_n)!\over x_1!x_2!\cdots x_n!}\le n^{x_1+x_2+\cdots+x_n}$$

with equality only in trivial cases.