How large a barcode library should be to ensure uniqueness Thanks for any help one can give with this…  
I need a general equation for the following problem, and I am sure it’s a special case of Poisson or binomial or Bernoulli or something, but I can’t seem to rearrange the equations to get the answer I need.
I have:


*

*N objects where:

*A pool of barcodes of size X, where the barcode is assigned randomly for each object from a range of 1 to X barcodes.

*There is no “memory” of what barcodes were last assigned, and there is no depleting of barcodes, so the pool of barcodes is “replenished” for each assignment of a barcode to an object.

*Each object gets only one barcode.


The question:
What is the range size of barcodes (1 to X) that ensures that there is a given confidence that no two or more objects are tagged with the SAME barcodes ?
My objective is to make the library of barcodes as SMALL as possible to ensure I don’t repeat barcodes on objects with a given confidence.
 A: You can't ensure uniqueness, but you can make the probability of a collision as small as you like.
For $n$ objects, if you want to reduce the probability of a collision to only $p$, 
you need to select from this many different barcode numbers: 1 and $$-n^2 \over 2 \log (1-p)$$ where as usual $p$ is between 0 and 1.
For example, suppose you have $n=64$ and you want a one-in-twenty ($p=0.05$) chance of a collision, so you get ${-64^2 \over 2 \log 0.95 } = 39,927$; call it 40,000. To reduce the chance of a collision to one in a million, take $p=0.000001$, and the formula gives $2,047,998,976$, so a bar code of ten random decimal digits is plenty. To handle ten times as many objects, use one hundred times as many barcode numbers.  (That is, make the barcodes two digits longer.)
With $n=23$ and a $p=\frac12$ chance of a collision, we get 381, which accords well with the usual statement of the birthday paradox—in that example we are usually selecting numbers between 1 and 365 (or 366) and we find that there is around a 50% chance of collision with 23 people.
(The logarithm here is to the base $e$. If the minus sign in the formula is puzzling you, note that $\log(1-p)$ is always negative.)
Ross Millikan already referred you to the relevant wikipedia article, but it is somewhat long, so you may want to pay special attention to the section titled "Cast as a collision problem".
A: As a rough heuristic, you have $\frac {N^2}2$ pairs of barcodes that might match.  You need somewhat more than that to likely avoid collision.  For more information, you might see Wikipedia on the generalized birthday problem.  But in most applications of this, you have a rough idea of $N$, so factors of $e$ don't matter.
