Combinatorics of the coupon collector's problem I have a set of N numbers. How many possible M-combinations - with M > N - of the N numbers are there which contain every number at least once? 

Example:
Numbers {1,2} and hence N = 2 and M be 3.
Possible 3-combinations:
1,1,1 (no)
1,1,2 (yes)
1,2,1 (yes)
1,2,2 (yes)
2,1,1 (yes)
2,1,2 (yes)
2,2,1 (yes)
2,2,2 (no)

Answer would be 6.
 A: I'll use the more standard terminology of using lowercase letters, so $n$ will denote your $N$, the number of numbers (which I'll call letters from here on to avoid confusion) available to use in your string, and $m$ will denote your $M$, the length of your string.  You can do an inclusion-exclusion sieve.  There are $n^m$ total strings of length $m$ from an alphabet with $n$ letters.  That's an overcount, so subtract, for each of the $n$ letters, the amount $(n-1)^m$, which equals the total number of strings of length $m$ not using the chosen letter, so there are now $n^m - n (n-1)^m$ such strings.  But this is an undercount, because we subtracted strings that are missing at least two letters too many times.  So we need to add in, for each ${n \choose 2}$ pairs of letters, the amount $(n-2)^m$.  But now this is an overcount again, and so it goes.  Thus, we get that the number of strings of length $m$ using each of the $n$ letters at least once is
$$
n^m - {n \choose 1} (n-1)^m + {n \choose 2} (n-2)^m - {n \choose 3} (n-3)^m + \cdots = \sum_{k=0}^{n} (-1)^k {n \choose k} (n-k)^m.
$$
Your number is equal to $n!$ times $S(m,n)$, where $S(m,n)$ stands for a Stirling number of the second kind.
