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 $N$ with two concerns:

(1) the possibility that this $N$ length string containing all $k$ symbols is very high.

(2) the length of this string $N$ is very short.

The first concern requires me to find the probability that

$\textrm{Pr}(N) = \dfrac{\sum\limits_{\forall i \in [0,1,...,k-1], n_i\geq 1}^{n_0+n_1+\cdots + n_{k-1} = N} \binom{N!}{n_0!n_1!\cdots n_k!}} {k^N}$

basically, this is the multinormial coefficient sum without unhappen events.

Since these two concerns push $N$ to two opposite directions, I guess I may get a bell shape curve $f$and find an optimized $N$ with the balance to both concerns, if I set $f:N\rightarrow\\textrm{Pr}(N)/N$ . However, I really donot know how to calculate $\textrm{Pr}(N)$ in this case.

Any comments are appreciated.

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.

Any comments are appreciated.