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 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 coefficients 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. The 21 multinomial coefficients in this set can be visualized below

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_] := 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]