# Rolling dice problems

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}$?

-
Could you clarify via an example exactly what you are looking for? Say, $m = 6, n = 10, k = 3$. Then you want the probability that all $10$ rolls of a fair die resulted in outcomes from $\{1, 2, 3\}$? (so that $1112111213$ is acceptable as is $1112111211$ but $1112111214$ is not) or the subset of these outcomes in which each of $1$, $2$, and $3$ occurred at least once on the $10$ rolls? (so that $1112111211$ is not acceptable because $3$ did not occur at all?) Which is it? –  Dilip Sarwate Dec 16 '11 at 15:04
The key word in the first question, @Dilip, is "all". $1112111211$ is not acceptable for $k=3$ because not all of $\{1,2,3\}$ appear in it. –  whuber Dec 16 '11 at 15:41
Eric, your first two questions are answered by suitable multiples of Stirling numbers of the second kind. The connection is made apparent by considering that each $j$, $1\le j\le k$, determines a subset of the rolls and any two subsets (for different $j$) are disjoint. Given such a partition (the number of which are counted by the Stirling numbers), it remains only to assign a unique element of $\{1,\ldots,m\}$ to each subset in it, which can be done in $m \cdot (m-1) \cdots (m-k+1)$ distinct ways. –  whuber Dec 16 '11 at 15:58
@whuber Thanks for the clarification. I didn't fully understand the wording, and wanted to make sure that the easier problem was not intended. Your answer to the first two questions is very astute but I wonder if "it remains only to assign a unique element of $\{1\ldots,m\}$ to each subset" should say "unique element of $\{1\ldots,k\}$" instead since the OP says "all and only indices from $1$ through $k$" –  Dilip Sarwate Dec 16 '11 at 16:24
For largish $m$ (exceeding $5$ or so) you will find that $k^*(m,n)$ equals the ceiling of $m(1-\exp(-n/m))$ (this is never less than $m/2$); from that you can obtain some insight into the critical $n$ in the last question. –  whuber Dec 16 '11 at 16:28
show 2 more comments