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.



What is the probability that you roll a dice with s sides for n times and t sides appeared once?
This is a variation of the combinatorial problem considered in section 5 of [Some new aspects of the coupon collector’s problem](http://www.brynmawr.edu/math/people/anmyers/PAPERS/Coupons.pdf) (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$$


