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 <a href="http://en.wikipedia.org/wiki/Chernoff_bound#Theorem_for_additive_form_.28absolute_error.29">Chernoff bound</a> with looser but more general bound given by <a href="http://yaroslavvb.com/upload/sanovs.png">Sanov's theorem</a>

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 <a href="http://yaroslavvb.com/upload/binomial.png">here</a>).

When k=3, it seems (empirically) to hold for sets of coefficients where sum of first two components is &le;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)

<img src="http://yaroslavvb.com/upload/multinomials.png">

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

<b>Update 8/18</b>
Leandro gives a bound on a single multinomial coefficient which gives <a href="http://yaroslavvb.com/upload/sanovs.png">Sanov's theorem</a> if we consider that there's at most $(n+1)^k$ multinomial coefficients in any set E. It seems that to generalize the <a href="http://yaroslavvb.com/upload/binomial.png">proof</a> 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$