# Restriction sum of multinomial coefficients

Hi all,

I am encountering a problem in calculating the sum of multinomial coefficients. The original problem is about a signal source with $k$ symbols under uniform distribution, i.e.

$p_0=p_1=\cdots=p_{k-1}= \dfrac{1}{k}$.

My problem is to find an appropriate string length $N$ with two concerns:

• The probability that a string of length $N$ contains all $k$ symbols is very high.

• The length of this string $N$ is very short.

The first concern requires me to find the probability that

$$\textrm{Pr}(N) = \frac{1}{k^{N}} \sum_{\substack{n_i\geq 1 \\\ n_0+n_1+\cdots + n_{k-1} = N}} \binom{N}{n_0~n_1~\cdots ~n_k}$$

The sum is of the multinomial coefficients without omitted symbols.

Since these two concerns push $N$ in opposite directions, I suggest maximizing $\textrm{Pr}(N)/N$ which goes to $0$ as $N \to \infty$ or $N\to 0$. However, I really don't know how to calculate $\textrm{Pr}(N)$ despite the above expression as a sum.

• Your term is a chimera between a multinomial coefficient written as a fraction and a multinomial coefficient written as a, well, multinomial coefficient. Or is it really a multinomial coefficient made out of factorials? – darij grinberg Sep 26 '11 at 2:00
• You need to read what you wrote carefully and edit it to make more sense. As well as the problem darij noted, your paragraph about $f$ has no clear meaning. It might be better to omit commentary and just state the problem precisely. – Brendan McKay Sep 26 '11 at 2:56
• I edited the question to try to fix and clarify it. I hadn't understood the Pr(N)/N part before. – Douglas Zare Sep 28 '11 at 2:54

The probability that a sequence does not contain all symbols is bounded above by the expected number of symbols omitted, $k (\frac{k-1}{k})^N \approx k \exp (\frac{-N}{k})$. You can ensure this is small by choosing $N$ to be large relative to $k \log k$.

You can get an exact probability easily using inclusion-exclusion since it is easy to count the sequences which omit a particular subset.

$$\sum_{i=0} (-1)^i {k \choose i} \bigg(\frac{k-i}{k}\bigg)^N.$$

Here is how to estimate $$Q(n,t) = \sum \binom{n}{k_1,\ldots,k_t}$$ with the sum over $k_1,\ldots,k_t\ge 1$ such that $k_1+\cdots+k_t=n$. Let $X_1,\ldots,X_t$ be independent random variables with truncated Poisson distribution $$Pr(X_i=q) = (e^{\lambda}-1)^{-1}\frac{\lambda^q}{q!},~~~q\ge 1.$$ Define $X=\sum_{i=1}^t X_i$. Then $$Q(n,t) = n!~ \lambda^{-n} (e^\lambda-1)^t Pr(X=n).$$ This is true for any $\lambda>0$. Now adjust $\lambda$ until $n$ is the mean of $X$ (requires solving some equation which might not have a closed form solution) and apply the central limit theorem. Since each $X_i$ is log-concave, $X$ is log-concave too, so the CLT applies in a local sense. So $Pr(X=n)$ is asymptotic to $1/\sqrt{2\pi\sigma^2}$ where $\sigma^2$ is the variance of $X$ (which is of course $t$ times the variance of $X_i$).

Thanks for Dr. Kao and Dr. Zetterberg's paper

An Identity for the Sum of Multinomial Coefficients

# it is published on MAA, Feb 1957.

The solution to my question is reached in a different way.