Given an American roulette wheel with $38$ possible outcomes ($0$-$36$ or $00$), what are the odds of landing on at least $m$ different numbers in $n$ spins?
Attempt: P(at least m different in n spins) = 1 - (P(exactly m same numbers) + P(exactly n-1 same numbers) + ... P(exactly n same numbers)
OR
P(at least m different in n spins) = P(exactly m different numbers) + P(exactly n-1 different numbers)+ ... + P(exactly n different numbers)
e.g. if m = 2 and n = 4 -> P(at least 2 different numbers in 4 spins) = $$\frac{38}{38}*\frac{37}{38}*\frac{2}{38}*\frac{2}{38} + \frac{38}{38}*\frac{37}{38}*\frac{36}{38}*\frac{3}{38} + \frac{38}{38}*\frac{37}{38}*\frac{36}{38}*\frac{35}{38}$$
which would be P(exactly 2 different 2 same) + P(exactly 3 different 1 same) + P(exactly 4 different) from left to right.
Could you please let me know how I should approach this problem in general? Do I have to use inclusion-exclusion principle?
Personally, I prefer recursion here.
I will express the probability as
$$\frac{N}{D} ~: ~D = (38)^n. \tag1 $$
So the question is reduced to computing $~N~$ by examining each of the $~(38)^n~$ equally likely results of the $~n~$ spins, and enumerating how many of them result in at least $~m~$ different numbers.
For $~b \in \Bbb{Z_{\geq 2}}, ~a \in \{1,2,\cdots,b\},~$
let $~f(a,b)~$ denote the number of sequences of length $~b,~$ which contain exactly $~a~$ distinct elements from the set $~~\{1,2,\cdots,38\}.$
Then, in (1) above, you have that
$$N = \sum_{a=m}^n f(a,n).$$
So, the problem is reduced to using recursion to provide a general formula for $~f(a,b).~$
$\underline{f(a,b) ~: ~b = 2}$
$$f(1,2) = \binom{38}{1}.$$
$$f(2,2) = 2 \times \binom{38}{2}.$$
$\underline{f(a,b) ~: ~b = 3}$
$$f(1,3) = \binom{38}{1}.$$
There are two ways of forming a sequence of length $~3~$ such that exactly $~2~$ elements from $~\{1,2,\cdots,38\},~$ are used:
You start with a sequence of $~2~$ characters that uses exactly $~1~$ distinct element, and append one of the unused elements to this sequence. This can be done in
$\displaystyle f(1,2) \times (38 - 1) = 38 \times 37 = 2 \times \binom{38}{2}~$ ways.
You start with a sequence of $~2~$ characters that uses exactly $~2~$ distinct elements, and append one of the already used elements to this sequence. This can be done in
$\displaystyle f(2,2) \times 2 = 2 \times \binom{38}{2} \times 2~$ ways.
Therefore,
$$f(2,3) = 3! \times \binom{38}{2}.$$
There is exactly one way of forming a sequence of length $~3~$ such that exactly $~3~$ elements from $~\{1,2,\cdots,38\},~$ are used:
$\displaystyle f(2,2) \times (38-2) = 2 \times \binom{38}{2} \times (38 - 2) = 3! \times \binom{38}{3}~$ ways.
$$f(3,3) = 3! \times \binom{38}{3}.$$
$\underline{\text{Detection of a pattern}}$
At this point, there is a clear pattern.
$f(a,b)~$ will equal $~\displaystyle scalar \times \binom{38}{a},~$
with $~\displaystyle f(1,b) = 1! \times \binom{38}{1},~$ and $~\displaystyle f(b,b) = b! \times \binom{38}{b}.~$
So, the challenge is to determine a pattern in the scalars, when $~2 \leq a \leq b-1.$
$\underline{f(a,b) ~: ~b = 4}$
Using methods similar to those used when computing $~f(a,3),~$ you have that
$$f(1,4) = \binom{38}{1}.$$
$$f(2,4) = [2 + (2 \times 3!)] \times \binom{38}{2} = 14 \times \binom{38}{2}.$$
$$f(3,4) = [(3 + 3) \times 3!] \times \binom{38}{3} = 36 \times \binom{38}{3}.$$
$$f(4,4) = 4! \times \binom{38}{4}.$$
$\underline{f(a,b) ~: ~b > 4}$
Personally, after exploring $~f(a,b) ~: ~b \leq 4,~$ I see no discernible pattern in the scalars. So, apparently, the best that I can offer is
$$f(1,b) = \binom{38}{1}.$$
$$f(b,b) = b! \times \binom{38}{b}.$$
For $~2 \leq a \leq (b-1),$
$$f(a,b) = [f(a-1,b-1) \times (39-a)] + [f(a,b-1) \times a].$$
$\underline{\text{Final Computation}}$
$$f(1,b) = \binom{38}{1}.$$
$$f(b,b) = b! \times \binom{38}{b}.$$
For $~b > 2, ~2 \leq a \leq (b-1),$
$$f(a,b) = [f(a-1,b-1) \times (39-a)] + [f(a,b-1) \times a].$$
Then, the desired probability is
$$\frac{N}{D} ~: ~D = (38)^n,$$
and
$$N = \sum_{a=m}^n f(a,n).$$