How to prove that ${l \choose a_1,...,a_n}\le n^{l-1} $ , when $a_1+...+a_n=l$.

Question

In the proof of (Corollary 8 chap. 3 ) in the book "Sobolev Spaces on Domains" by Burenkov the following inequality is used : given $a_1,...,a_n \in \mathbb{N}$ such that $a_1+...+a_n=l$, then $${l \choose a_1,...,a_n}\le n^{l-1} $$ where $${l \choose a_1,...,a_n}=\frac{l!}{a_1!a_2!\cdots a_n!}$$ is the multinomial coefficient. How can one prove this fact? I was able to prove using multinomial theorem that $${l \choose a_1,...,a_n}\le n^{l}$$ but I couldn't prove the sharper inequality.

Answer 1

Assuming that $a_1,\ldots,a_n$ are distinct integers, $$n\binom{l}{a_1,\ldots,a_n}\\=\binom{l}{a_1,a_2,\ldots,a_{n-1},a_n}+\binom{l}{a_2,a_3\ldots,a_{n},a_1}+\ldots+\binom{l}{a_n,a_1,\ldots,a_{n-2},a_{n-1}}$$ but the last sum is less than the sum of any multinomial coefficient $\binom{l}{x_1,x_2,\ldots,x_{n-1},x_n}$ with $x_1+x_2+\ldots+x_{n-1}+x_n=n$, hence it is less than $n^l$. The same argument gives the stronger: $$\binom{l}{a_1,\ldots,a_n} \leq \frac{n^l}{n!}.$$ We may deal with the cases in which $a_i=a_j$ by inclusion-exclusion.