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. 



Restriction sum of multinomial coefficients
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.$$


