Probability of getting k different coupons in a set of S coupons, from an infinite set of N different types of coupons.

Question

This is my slight modification to a question in the book "Introduction to Probability and Statistics for Engineers and Scientists" by Sheldon M Ross.

Suppose there are N different types of coupons and suppose that each time
one obtains a coupon it is equally likely to be any one of the types. 
Compute the probability that you get exactly k different types of coupons in a set of S coupons.
N>0, k<=S<N.

I tried to create the probability mass function but I am not able to come up with the correct one.

Here is mine.

Choosing k coupons from N coupons can be done in
Combination(N,k) ways.  -- (1)

---

k places (1 for each coupon) in a set of S can be chosen in Combination(S,k) ways  -- (2)

this is to satisfy the atleast one coupon of each type criteria.

These k coupons can arrange themselves in k! ways.  --(3)

The remaining (S-k) places can be filled by any of the k coupons. Coupons are replaced as per the question.

So it becomes k^(S-k)     --(4)

---

Finally the probability to choose one coupon is 1/N (equal for all types) and thus for a set of S coupons it becomes (1/N)^S --(5)

So my answer for the question becomes (1) * (2) * (3) * (4) * (5) But my answer probability mass function does not sum up to 1. And so I am doing a blunder somewhere. Am I thinking completely wrong?

Answer 1

In order to be consistent with standard notation, instead of picking $S$ coupons, we will pick $n$.

The number of ways to divide a set of $n$ elements into $k$ non-empty subsets is $S(n,k)$, where $S(n,k)$ is the Stirling Number of the Second Kind.

Thus the number of "favourables" is $\binom{N}{k}k!S(n,k)$, and the required probability is $\frac{\binom{N}{k}k!S(n,k)}{N^n}$.

Remark: An Inclusion/Exclusion argument shows that $$k!S(n,k)=\sum_{i=0}^k (-1)^{k-i} \binom{k}{i}i^n.$$ The first term $k^n$ counts the number of words of length $n$ that one can make from an alphabet of size $k$. The remaining terms are to make sure that we are only counting the words that have at least one of each of the $k$ letters.

There are a number of useful recurrences for the Stirling numbers of the second kind, but no closed form in terms, for example, of factorials.