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.

-
AMM, not MAA. Anyway I think you are looking for the Stirling numbers of the 2nd kind: en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind – darij grinberg Sep 26 '11 at 3:59