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 <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 spaces, ie the corner of (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+i3<=5 *)
getit[10, 3, 5]