what is the probability of drawing each element at least once from set $\{1,2,3,\dots, n\}$ , drawing with replacements at most $k$ times ($k>n$)

Question

what is the probability of drawing each element at least once from set $\{1,2,3,\dots, n\}$, drawing with replacements at most $k_0$ times ($k_0>n$)

my take:

$$\left(\prod_{i=1}^{n} \frac{i}{n}\right)\left(\sum_{j=1}^{n}\left(\frac{j}{n}\sum_{k=1}^j\left(\frac{k}{n}\sum_{l=1}^k\frac{l}{n}\dots [k_0-n \text{ times this construction}]\right)\right)\right)$$

and if this is correct I don't see a way to simplify this and I would ask for help simplifying this expression

how I derived this: first part is probability of obtaining all elements, and then you need to account for "failed" rounds.

i.e. for rolling dice once a day for a week: \begin{align} P(\text{rolling each side of dice in 7 throws}) &=\left(\prod_{i=1}^{6}\frac{i}{6}\right)\sum_{i=1}^{6}\frac{i}{6} \end{align}

---

best solution I have so far is function that have complexity $O(n*k_0)$

from math import prod

def coupon_collector_in_k_draws(n, k):
    denominator_count = n
    res = prod(range(1, n+1))
    n_sq = n**5
    while res > n_sq:
        res /= n
        denominator_count -= 1
    k1 = k-n
    tab = [1] * (k1+1)
    den_count = [0] * (k1+1)
    for nn in range(2, n+1):
        for k in range(k1)[::-1]:
            tab[k] += nn*tab[k+1]/(n**(den_count[k] - den_count[k+1]))
            while tab[k] > n_sq and den_count[k] < k1:
                tab[k] /= n
                den_count[k] += 1
    rs = tab[0]
    for j in range(k1 - den_count[0]):
        rs /= n
    res *= rs
    while denominator_count:
        res /= n
        denominator_count -= 1
    return res

Answer 1

Let me put $k_{\,0} = m$.

Then your problem is equivalent to that of throwing $m$ labelled balls ( = position in the extraction sequence) into $n$ bins ( = extraction result), in such a way that no bin is left empty.
It is also equivalent to the number of ways to compose a set of $m$ elements into a list (order counts) of $n$ non-empty subsets which is given by $n!$ times the Stirling Number of 2nd kind $$ N(m,n) = n!\left\{ \matrix{ m \cr n \cr} \right\} $$ The total number of ways of throwing the balls is clearly $n^m$, which in fact equals $$ n^{\,m} = \sum\limits_{0\, \le \,k\,\left( { \le \,n} \right)} {\left\{ \matrix{ m \cr k \cr} \right\}\,n^{\,\underline {\,k\,} } } \; = \sum\limits_{0\, \le \,k\,\left( { \le \,n} \right)} {k!\left\{ \matrix{ m \cr k \cr} \right\}\, \left( \matrix{ n \cr k \cr} \right)} $$ where $x^{\,\underline {\,k\,} }$ represents the Falling Factorial.

Regarding your approach, consider that an alternative definition of the Stirling N. 2nd kind is $$ \eqalign{ & \left\{ \matrix{ m \cr n \cr} \right\}\quad = {1 \over {n!}}\sum\limits_{\left\{ {\matrix{ {1\, \le \,k_{\,j} \,\left( { \le \,m} \right)} \cr {k_{\,1} + k_{\,2} + \, \cdots + k_{\,n} \, = \,m} \cr } } \right.\;} {\left( \matrix{ m \cr k_{\,1} ,k_{\,2} , \cdots k_{\,n} \cr} \right)} = \cr & = {{m!} \over {n!}}\sum\limits_{\left\{ {\matrix{ {0\, \le \,l_{\,j} \,\left( { \le \,m - n} \right)} \cr {l_{\,1} + l_{\,2} + \, \cdots + l_{\,n} \, = \,m - n} \cr } } \right.\;} {{1 \over {\left( {l_{\,1} + 1} \right)!\left( {l_{\,2} + 1} \right)!\, \cdots \left( {l_{\,n} + 1} \right)!}}} = \cr & = \left( \matrix{ m \cr n \cr} \right)\sum\limits_{\left\{ {\matrix{ {0\, \le \,l_{\,j} \,\left( { \le \,m - n} \right)} \cr {l_{\,1} + l_{\,2} + \, \cdots + l_{\,n} \, = \,m - n} \cr } } \right.\;} {{1 \over {\left( {l_{\,1} + 1} \right)\left( {l_{\,2} + 1} \right)\, \cdots \left( {l_{\,n} + 1} \right)}} \left( \matrix{ m - n \cr l_{\,1} ,l_{\,2} ,\, \cdots ,l_{\,n} \cr} \right)} \cr} $$ and that the multinomial can be written as $$ \eqalign{ & \left( \matrix{ m \cr k_{\,1} ,k_{\,2} , \cdots k_{\,n} \cr} \right) \quad \left| {\;k_{\,1} + k_{\,2} + \, \cdots + k_{\,n} \, = \,m} \right.\quad = \cr & = {{m!} \over {k_{\,1} !k_{\,2} ! \cdots k_{\,n} !}} = {{m^{\,\underline {\,k_{\,1} + k_{\,2} + \, \cdots + k_{\,n} \,} } } \over {k_{\,1} !k_{\,2} ! \cdots k_{\,n} !}} = \cr & = {{m^{\,\underline {\,k_{\,1} \,} } } \over {k_{\,1} !}} {{\left( {m - k_{\,1} } \right)^{\,\underline {\,k_{\,2} \,} } } \over {k_{\,2} !}} {{\left( {m - k_{\,1} - k_{\,2} } \right)^{\,\underline {\,k_{\,3} \,} } } \over {k_{\,3} !}}\, \cdots \; {{\left( {m - \left( {m - k_{\,n} } \right)} \right)^{\,\underline {\,k_{\,n} \,} } } \over {k_{\,n} !}} \cr} $$