Let the random variable be the number of dice rolls performed before all faces have occurred. The subpower is defined a^{\{b\}}=a!\left\{{b\atop a}\right\}, where \left\{{b\atop a}\right\} is a
Stirling number of the second kind. Sequences of k die rolls are functions k\rightarrow n counted by n^k, while surjections (that land on each face at least once) are counted by n^{\{k\}}, so the probability that all faces were landed on within the -th throw is P(X\le k)=\frac{n^{\{k\}}}{n^k}. By the recurrence relation of the Stirling numbers, the probability that exactly rolls are needed is P(X=k)=\frac{n^{\{k\}}}{n^k}-\frac{n^{\{k-1\}}}{n^{k-1}}=\frac{(n-1)^{\{k-1\}}}{n^{k-1}}
Generating functions Replacing z with 1+z in the
probability generating function produces the o.g.f. for E\left[{X\choose k}\right]. Using the partial fraction decomposition {\frac1x-1\choose n}^{-1}=\sum_{k=0}^n{n\choose k}\frac{(-1)^{n-k}}{1-kx}, we can take the expansion :\begin{aligned}&{\frac n{x+1}\choose n}^{-1}\\ =&\sum_{i=0}^n{n\choose i}\frac{(-1)^{n-i}}{1-i(1-\frac n{x+1+n})}\\ =&\sum_{i=0}^n{n\choose i}(-1)^{n-i}\left(\frac{1+n}{1+n-i}+in\sum_{k=1}^\infty\frac{(i-1)^{k-1}}{(n+1-i)^{k+1}}x^k\right)\end{aligned} revealing that for k>0, :E\left[{X\choose k}\right]=n\sum_{i=0}^n{n\choose i}(-1)^{n-i}i\frac{(i-1)^{k-1}}{(n+1-i)^{k+1}} Given an o.g.f. , since \left(\frac x{1-x}\right)^i=\sum_{n=0}^\infty{k-1\choose i-1}x^k, a variation of the
binomial transform is [x^k]f\left(\frac x{1+x}\right)=\sum_{i=0}^k{k-1\choose i-1}(-1)^{k-i}[x^i]f(x). (Specifically, if {\frac n{x+1}\choose n}^{-1}=f\left(\frac x{1+x}\right), f(x)={n-nx\choose n}^{-1}.) Rewriting the binomial coefficient via the
gamma function and expanding as the \exp of the
polygamma series (in terms of
generalised harmonic numbers), we find \left[\frac{x^i}{i!}\right]{n-x\choose n}^{-1}=\sum_{P\in\mathrm{perms}(i)}\prod_{c\in P}H^{(|c|)}_n, so :E\left[{X\choose k}\right]=\sum_{i=0}^k{k-1\choose i-1}(-1)^{k-i}\frac{n^i}{i!}\sum_{P\in\mathrm{perms}(i)}\prod_{c\in P}H^{(|c|)}_n which can also be written with the
falling factorial and
Lah numbers as :E[x^\underline k]=\sum_{i=0}^kL(k,i)(-1)^{k-i}n^i\sum_{P\in\mathrm{perms}(i)}\prod_{c\in P}H^{(|c|)}_n The
raw moments of the distribution can be obtained from the falling moments via a
Stirling transform; due to the identity \left\{{K\atop i}\right\}(-1)^K=\sum_{k=0}^K\left\{{K\atop k}\right\}L(k,i)(-1)^k, this provides :E[x^k]=\sum_{i=0}^k\left\{{k\atop i}\right\}(-1)^{k-i}n^i\!\!\sum_{P\in\mathrm{perms}(i)}\prod_{c\in P}H^{(|c|)}_n ==Tail estimates==