# N People Picking

In *Pick a Number - Level 2* we calculated the probability of a group of 20 people all picking different numbers between 1 and 100. Here we derive a general algebraic approximation.

Suppose $N$ people pick a number at random between 1 and $T$. Imagine them in a line picking numbers one at a time (without consulting each other). Let the probability that they all pick different numbers be $p(N,T)$. For this event to occur, the second picks a different number from the first, the third picks a different number from the first 2, and so on, so

$$p(N,T) = \left(1-\frac{1}{T}\right)\left(1-\frac{2}{T}\right)....\left(1-\frac{N-1}{T}\right),$$

which may be easily calculated.

Now provided $N$ is reasonably small compared to $T$, then $\left(1-\frac{k}{N}\right) \approx e^{-k/T}$ for $k =

1,2,...,N-1$, and so the probability they all choose different numbers is

$$ p(N,T) = e^{-\frac{1}{T}[1+2+...+(N-1)]} = e^{-\frac{1}{T}N(N-1)/2}$$

using the fact that the sum of the first $N-1$ integers is $N(N-1)/2$. For reasonably large $N$ this can be approximated by $e^{-\frac{N^2}{2T}}$. So we can complete the Table:

$T$ | $N^2T/2$ = expected number of matches | $p(N,T)$ | % chance that all different |
---|---|---|---|

$N^2/2$ | $1$ | $e^{-1}$ | 37% |

$N^2/4$ | $2$ | $e^{-2}$ | 13% |

$N^2/6$ | $3$ | $e^{-3}$ | 5% |

$N^2/8$ | $4$ | $e^{-4}$ | 2% |

$N^2/10$ | $5$ | $e^{-5}$ | 1% |