Probability of picking elements randomly without frequent repeats If I have a set S that has n unique elements, and I pick from it such that each element has an equal probability of being chosen, how many elements should S be so that the probability of seeing any elements repeated within a small subset of drawn elements (let's say, 5) is low (like less than .5)? To put it another way, if I am using a random number generator to pick 5 or so integers from 1 to n, how large should n be to ensure the probability of seeing the same number come up twice is less than .5? Sorry if my phrasing is confusing, I'm not a mathematician. I'm interested in this because it will simplify some code I'm working on by a lot.
 A: Selecting $k$ from $n$ the probability of no collisions (all $k$ are distinct) is
$ (1) (1 - 1/n) (1-2/n) \dots (1- (k-1)/n)$.
For $n$ large relative to $k$ this is approximately $1 - (1/n + 2/n + \dots (k-1)/n) = 1 - k(k-1)/2n$.  
In other words, if $n$ is comparable to $k^2$ there will be some non-negligible positive probability of a collision and if $n \gg k^2$ the probability will be low.
This is close to the "Birthday Problem". 
(addition: ) To rigorously bound the probability $p$ of a collision, note that the expected number of collisions is $k(k-1)/2n$ and this quantity is larger than $p$.  To guarantee that $p$ is less than $\epsilon$, taking $n > k(k-1)/2\epsilon$ is sufficient.  This is not as good an estimate as the Poisson approximation which is asymptotically optimal.  To find the minimum possible $n$ for given $p$ and $k$ one can use the formula for the probability of a collision and "solve for $n$" with a polynomial root-finder. 
A: The Poisson approximation says that,
choosing $k$ times from the set $\{1,2\,\dots n\}$, 
the probability of no collisions is about $\exp(-{k\choose 2}/n)$.
You may want this probability to be some value $p$.
Setting the Poisson approximation to $p$ and solving for 
$n$ gives the formula
$$n\approx {k(k-1)\over 2\ln(1/p)}.$$
For example with $k=5$ and $p=1/2$ we get 
$$n\approx {10\over\ln(2)}= 14.4269$$
which I'd round up to $n=15$.  
