Consider the following little problem:
Roll an $m$-sided die $n$ times. What is the probability that all and only indices from $1$ through $k$ appear? ($k\leq n,m$)
Here's my thought (you can check if it's correct). I want to know if there's a simpler approach available (which doesn't invoke recursive formulae, for example):
Given any $i$ indices from $1$ to $k$, let $w(i)$ be the number of outcomes in our $n$ trials in which all and only those $i$ indices appear. Then we have $w(1)=1$, and $w(i)={i}^{n}-\sum_{j=1}^{i-1}{i \choose j}w(j)$.
By this definition, there are exactly ${k \choose i}w(i)$ outcomes in which exactly $i$ different indices from $1$ to $k$ appear.
Hence the required probability $p(m,n,k)=\left({k}^{n}-\sum_{i=1}^{k-1}{k \choose i}w(i)\right)/{m}^{n}$.
A little modification of the original question: Roll an $m$-sided die $n$ times. What is the probability that exactly $k$ ($k\leq n,m$) different indices appear? By the above analysis, this probability should be $q(m,n,k)={m \choose k}p(m,n,k)$.
Now Let ${k}^{*}(m,n)={\text{argmax}}_{(k)}\ q(m,n,k)$ be the most probable number of different indices in the $n$ trials. I'm interested in the distribution of ${k}^{*}(m,n)$. For instance, in general, can we have a clear expression for the value of ${k}^{*}(m,m)$? ${k}^{*}(m,m)>m/2$ or $<m/2$ for large $m$? Given $m$, what is the critical (smallest) $n$ such that ${k}^{*}(m,n)=m$? These questions seem difficult to answer given my formation so far, although they are all easy to imagine conceptually. Are they intrinsically difficult?
EDIT: By writing $w(i)$ as $w(i,n) = \sum_{j=0}^{i-1} (-1)^j(i-j)^n{i \choose j}$ I notice that, say, $w(3,2)=w(4,3)=w(4,2)=0$. Is it true that $w(i,n)=0$ if $i>n$? By the die model there's 0 ways you can have $i$ different numbers in $n$ rolls if $i>n$. So $w(i,n)$ gives consistent result for the die model even if $i>n$. But clearly the case for $i>n$ doesn't have an interpretation using $w(i,n)$, in the sense of the die model, as the case for $i\leq n$ does. What's the reason $w(i,n)=0$ for $i>n$? Is there a model interpretation for it, too?
Furthermore, define ${f}_{i}(x) = \sum_{j=0}^{i-1} (-1)^j(i-j)^x{i \choose j}$ where $i=1,2,3,...$ and $x \in \mathbb{R}$. Is it true that $x=1,2,...,i-1$ are the only zeros of ${f}_{i}$?
