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. 

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_] := Module[{},
   all = Select[Tuples[Range[0, n], k], Total[#] == n &];
   e = Select[all, Total[Most[#]] <= c &];
   hterm[x_] := If[x <= 0 || x >= 1, 0, x Log[x]];
   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]
</pre>