Question: Each employee has an employee number which is a string of five digits, in which no digit occurs more than once. Thus, 82176 is a valid employee number, whereas 84640 is not valid. What is the minimum number of employees such that we can guarantee that at least two of them have the same employee number?
a) 1 + 10^5
b) 1 + 5^10
c) 1 + 10!/5!
d) 1 + 5!/10!
Attempt: I'm assuming the pigeonhole principle applies here, but I'm not sure how exactly it does. I know each digit has 10 possible choices and 5 digits. So, I thought it would be 5^10 + 1. Don't know why the answer is C though. Like why use factorials.
the cardinality of the feasible employee numbers would be $\frac{10!}{5!}$ since order matters. Think of it as the first position has $10$ choices, the next has $9$ choices to avoid repetition and so on. By this reasoning we have $\prod_{i=0}^4 (10-i)=\frac{10!}{5!}$
By pigeonhole principle, we need $\frac{10!}{5!}+1$ to ensure there is a sharing of employee number.
$5^{10}$ means you are making $5$ choices each time for $10$ times, which is not the case here.