When does the following hold?

$\sum_{(i_1,\ldots,i_k)\in E} \frac{n!}{i_1! \ldots i_k!} \le \exp(n H^*)$

Where

$H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{i_k}{n}\log \frac{i_k}{n})$ and E is some subset of {$ \{( i_1,\ldots,i_k):i_1+\ldots+i_k=n \}$}

Motivation: this is a generalization of Chernoff's bound to n tosses of fair k-sided dice where E represents the hypothesis we make about that sample. Another motivation is reconciling tight special-case Chernoff bound with looser but more general bound given by Sanov's theorem

Examples: when k=2, it can be proven to hold for sets of coefficients where first component of the coefficient is less than n/2 (ie here).

When k=3, it seems (empirically) to hold for sets of coefficients where sum of first two components is ≤n/2. For instance, for n=10, highest entropy term gives upper bound of (2/3)^3 *10^5 whereas exact sum is 12585. Since k=3 multinomial coefficients lie in a 2-simplex, the 21 multinomial coefficients in this set can be visualized below. Top vertex represents coefficient (0,0,10)

For higher k, we can look at similar sets, ie corners of the (k-1) simplex. I tried few values and it seems to hold for coefficients where sum of first k-1 components is below n/(k-1)

Here's how you'd check it in Mathematica

getit[n_, k_, c_] := (
   all = Select[Tuples[Range[0, n], k], Total[#] == n &];
   e = Select[all, Total[Most[#]] <= c &];
   hterm[x_] := If[0 < x < 1, x Log[x], 0];
   H[event_] := -Total[hterm /@ (event/n)];
   exact = Total[Multinomial @@@ e];
   upper = Exp[n Max[H /@ e]];
   exact < upper
);
(* Check bound for k=3, n=10, with i1+i2<=5 *)
getit[10, 3, 5]

Update 8/18 Leandro gives a bound on a single multinomial coefficient which gives Sanov's theorem if we consider that there's at most $(n+1)^k$ multinomial coefficients in any set E. It seems that to generalize the proof of the tighter binomial bound to, say, trinomial coefficients, one would need to prove the following inequality first

$$q_1^{i_1}q_2^{i_2} (1-q_1-q_2)^{n-i_1-i_2}\ge \exp -n H(q_1,q_2)$$ for $n i_1 < q_1, n i_2 < q_2$