Multinomial coefficient bounded above by its entropy exponential

A multinomial coefficient never exceeds the exponential of its entropy.

Let $R$ be a nonempty finite index set, $w : R \to \mathbb N$ strictly positive, $W = \sum_i w_i$, and $m \in \mathbb N$. Write $p_i = w_i / W$ for the normalised weight vector and $H(p)$ for its Shannon entropy in bits. Then

This is the elementary half of the type-counting estimate: a single type class is no larger than the exponential of its entropy. It is the exact counterpart of the platform's mme_dwz_multinomial_entropy_polynomial_lower, which supplies the matching lower bound at the cost of a polynomial factor, and together the two pin the multinomial to within a polynomial of $2^{N H}$.

The pair is what one needs to compare two multinomial coefficients on the same total, for instance two joint histograms with the same marginals, at exponential rate: the ratio is $2^{N(H_1 - H_2)}$ up to a polynomial factor.

Formalization note. The proof is the classical one and uses no Stirling estimate. By the multinomial theorem, $1 = (\sum_i p_i)^{Wm}$ expands as a sum of non-negative terms $\binom{Wm}{k} \prod_i p_i^{k_i}$ over all compositions $k$ of $Wm$; keeping only the term at $k_i = w_i m$ gives $\binom{Wm}{wm} \prod_i p_i^{w_i m} \le 1$, and $\prod_i p_i^{w_i m} = \exp\bigl(-m W \ln 2\, H(p)\bigr)$ by definition of the entropy. Strict positivity of $w$ keeps every logarithm finite.