TAOCP 1.2.10 Exercise 8

Section 1.2.10: Analysis of an Algorithm

Exercise 8. [M20] Suppose that each $X[k]$ is taken at random from a set of $M$ distinct elements, so that each of the $M^n$ possible choices for $X[1],X[2],\ldots,X[n]$ is considered equally likely. What is the probability that all the $X[k]$ will be distinct?

Verified: yes
Solve time: 4m36s

Solution

Let $E$ be the event that all of the values $X[1],X[2],\ldots,X[n]$ are distinct.

Each $X[k]$ is chosen independently from a set of $M$ distinct elements, and all $M^n$ sequences are equally likely. Hence

$$ \Pr(E) = \frac{\text{number of sequences with all entries distinct}}{M^n}. $$

To count the favorable sequences, choose the values successively.

There are $M$ choices for $X[1]$.

After $X[1]$ has been chosen, there are $M-1$ choices for $X[2]$ if it is to differ from $X[1]$.

After $X[1],X[2]$ have been chosen distinctly, there are $M-2$ choices for $X[3]$.

Continuing in this way, there are $M-(n-1)$ choices for $X[n]$.

Therefore, when $n\le M$, the number of sequences having all entries distinct is

$$ M(M-1)(M-2)\cdots(M-n+1). $$

Hence

$$ \Pr(E) = \frac{M(M-1)\cdots(M-n+1)}{M^n}. $$

Equivalently,

$$ \Pr(E) = \prod_{k=0}^{n-1}\left(1-\frac{k}{M}\right). $$

If $n>M$, it is impossible for $n$ positions to contain distinct values chosen from only $M$ elements. Thus

$$ \Pr(E)=0. $$

The required probability is therefore

$$ \boxed{ \Pr{X[1],X[2],\ldots,X[n]\ \text{all distinct}} = \begin{cases} \dfrac{M(M-1)\cdots(M-n+1)}{M^n}, & n\le M,\[2ex] 0, & n>M. \end{cases} } $$