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.

Solution 1:

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.