4
$\begingroup$

You roll a dice with $s$ sides for $n$ times. What is the probability that $t$ sides appeared once?

Example with $s=2$, $n=3$: you roll a dice with 2 sides for 3 times. possible outcomes: '1' and '2'.

  • $p(t=0)$ is the probability that '1' appeared 0 times and '2' appeared 3 times + the probability that '2' appeared 0 times and '1' appeared 3 times, that is 1/4.
  • $p(t=1)$ is the probability that '1' appeared once and '2' appeared twice + the probability that '2' appeared once and '1' appeared twice, that is 3/4.
  • $p(t=2)=0$, because it is impossible that both '1' and '2' appear once.

If there is a formula for $p(s,n,t)$ it will be awesome, but also an algorithm is welcome.

$\endgroup$

1 Answer 1

3
$\begingroup$

This is a variation of the combinatorial problem considered in section 5 of Some new aspects of the coupon collector’s problem (2003).

The $t$ singleton sides (sides which appear once) can be chosen as an ordered sequence in $t! {s\choose t}$ ways; this sequence can appear among the $n$ rolls in ${n\choose t}$ ways and the remaining $n-t$ rolls constitute an ordered partition of $n-t$ elements into $s-t-k$ classes, $k=0,1,\ldots s-t-1$, no class having fewer than two elements, which can be chosen in $\sum_{k=0}^{s-t-1}(s-t-k)!{{s-t}\choose k}\begin{Bmatrix} n-t\\ s-t-k \end{Bmatrix}_2$ ways. (The integer $k$ counts the number of classes that do not appear at all.) Multiply these together and divide by $s^n$, the number of $n$ sequences, to obtain the desired probability

$$p=\frac{s!}{s^n} {n\choose t}\sum_{k=0}^{s-t-1}\frac{1}{k!}\begin{Bmatrix} n-t\\ s-t-k \end{Bmatrix}_2$$

The generating function for the coefficients $\begin{Bmatrix} n\\ k \end{Bmatrix}_2$ is $$\sum_{n\geq 0}\begin{Bmatrix} n\\ k \end{Bmatrix}_2\frac{x^n}{n!}=\frac{1}{k!}\left(e^x-1-x\right)^k$$

$\endgroup$
2
  • $\begingroup$ Thank you very much, but I don't know what is the meaning of the 2 in the matrix. Can you explain it? $\endgroup$
    – Marco Ieni
    Commented Jun 10, 2017 at 12:51
  • $\begingroup$ it's explained on page 12 in the cited paper, where they define this generalized Stirling coefficient with a subscript $h$ as the number of unordered partitions of an $n$-set into $k$ classes of at least $h$ elements each; here I need $h=2$. $\endgroup$ Commented Jun 10, 2017 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.