Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial coefficient corresponding to $i$'th tuple in $S$, ie

$$v_i=\frac{n!}{c_1!\cdots c_d!}$$

What can we say about the sum of smallest coefficients, ie, the value of the following?

$$s(B)=\sum_{v_i < B} v_i$$

Motivation: upper bounds on multinomial tails would allow to give non-asymptotic error bounds for various learning algorithms

**Update: 09/03**
Here are all the relevant theoretical results I found so far. Let $B=\frac{n!}{c_1!\cdots c_d}$, $C=\max_i v_i$, $k=\min_i c_i$. Then for even n and $d=2$ the following are known to hold

$$s(B)<\frac{B}{C} 2^n$$ Proof under Lemma 3.8.2 of Lovasz et al "Discrete Mathematics" (2003)

$$s(B)\le 2^n \exp(-\frac{(n/d-k)^2}{n-k})$$ Proof under Theorem 5.3.2 of Lovasz et al "Discrete Mathematics" (2003)

$$s(B)\le 2B(\frac{n-(k-1)}{n-(2k-1)}-1)$$ Michael Lugo gives outline of proof in another MO post

$$s(B)<2(\exp(n \log n - \sum_i c_i \log c_i)-B)$$
Proof under Lemma 16.19 of Flum et al *Parameterized Complexity Theory* (2006)

To be practically useful for my application, these bounds need to be tight for tails, ie, for sums that are less than $d^n/10$. Here's a plot of logarithm of bound/exact ratio for such sums. X-axis is monotonically related to B.

You can see that Michael Lugo's bound is by far the most accurate in that range.

Out of curiosity, I "plugged in" bounds above for sums of higher dimensional coefficients.

^{(source)}

^{(source)}

Mathematica notebook.