Suppose that $n$ people are each randomly assigned a number from $1$ to $m$ with replacement. What is the probability that exactly one number is assigned to more than one person?
What I have tried:
Defining the event $A$ to be 'exactly one number is assigned to more than one person', I can see that the probability of $A$ is $0$ when $m=n$ and $1$ when $m<n$.
For $m>n$, the sample space would be $m^n$. I have written out the sample space for $n=3$ and $m=4$. In this case, $P(A)=40/64=5/8$. However, I cannot see how to compute the number of sample points in the general case.
Best Answer
The sample space is \begin{align} \Omega = \{(N_1, N_2, \ldots, N_n): N_i \in \{1, \ldots, m\}, 1 \leq i \leq n\}. \end{align} Clearly, $|\Omega| = m^n$.
To determine the probability of interest $P(A) = |A|/|\Omega|$, it suffices to count $|A|$. Suppose $m \geq n$. Note that if $k \in \{1, \ldots, m\}$ is the "exactly one number" that is assigned to more than one person, then $k$ can be assigned to $2, 3, \ldots, n$ people. In view of this, $|A|$ can be then determined by applying the rule of product and the rule of sum.
In detail, there are $\binom{m}{1}$ ways of choosing $k$ that will be assigned to $j$ ($2 \leq j \leq n$) people. Once $k$ is chosen, there are $\binom{n}{j}$ ways to assign it to $j$ people picked randomly from a cohort of $n$ people, and $\binom{m - 1}{n - j} \times (n - j)!$ ways of assigning the remaining $n - j$ people each a distinct number. It then follows by the rule of product that the number of ways of assigning exactly one number to $j$ people ($2 \leq j \leq n$) is: \begin{align} \binom{m}{1} \times \binom{n}{j} \times \binom{m - 1}{n - j} \times (n - j)!. \end{align}
By the rule of sum: \begin{align} |A| = \binom{m}{1}\sum_{j = 2}^n \binom{n}{j}\binom{m - 1}{n - j}(n - j)!. \end{align}
I am not sure though, if $|A|$ can be further simplified.