Is there a closed form formula for this function of two positive integers?

64 Views Asked by At

Let $n$ and $k$ be positive integers. Suppose there are $n$ cards in a deck, and you want to collect at least $k$ of each card. A store sells these cards, but here is the catch: It is random which card you will get. So, for example, if $n = 3$ and $k = 1$, then if you buy $4$ cards, it is possible you get two each of the first two cards, but none of the third card. If you keep buying enough cards, then with probability $1$ you will eventually get at least $k$ of each card. Let $f(n,k)$ be the expected value of the number of cards you have to buy to get at least $k$ of each of the $n$ cards. What is a closed-form formula, if there is any, for $f(n,k)$? Of course, if $n = 1$, then you just have to buy exactly $k$ cards. Also, I believe this problem has been studied for the special case of $k = 1$. I am generalizing it to the case of all positive integer $k$, not just $1$.