# Probability of an exact number of duplicate pairs when choosing X from Y.

Here is the problem I'm faced with, as best as I can describe it.

There is a set of 256 values (a byte), and 108 values are chosen from this set. Each choice may be any value from 0 to 255. What is the probability that once the values are chosen, there will be six distinct pairs of duplicate values, and all other 96 values will be unique?

• What's the relevance of having 256 values to pick from? Without knowing what they are I don't see what the question is really asking. Unless you're saying that you're generating 108 uniformly distributed integers between 0 and 255 inclusive, in which case this should be worded more clearly. – Robert Mastragostino Jun 20 '12 at 20:22
• Are all $256^{108}$ choices equally likely? – John Engbers Jun 20 '12 at 20:30
• Sorry, you're right in phrasing that I'm generating 108 uniformly distributed integers between 0 and 255 inclusive. – Mak Kolybabi Jun 20 '12 at 20:55
• Just out of curiosity, did you change the question shortly after positing it or am I going mad? – Henry Jun 20 '12 at 21:16

First let us compute the number of choices in a canonical order. We list the pairs first in increasing order, then the single numbers. There are $\binom {256}{6}$ ways to pick the pairs and $\binom {250}{96}$ ways to pick the singles. Given a set of numbers, they can be ordered in $\frac {108!}{2^6}$ ways, as interchanging any of the pairs is equivalent. The total probability is then $\frac {\binom {256}{6}\binom {250}{96}108!}{256^{108}2^6}\approx 6.5E-6$

You have $6+96+154=256$ and $6\times 2 + 96 \times 1 + 154 \times 0 = 108$ so the probability you are looking for is

$$\frac{\frac{256!}{6!\;96!\;154!} \times \frac{108!}{(2!)^6\;(1!)^{96}\;(0!)^{154}}}{256^{108}}$$

Some more background on this approach can be found at https://math.stackexchange.com/a/23282/6460 and https://math.stackexchange.com/a/23696/6460

The numerical calculation may stretch some calculators. I make it about $6.54 \times 10^{-6}$.

To solve the problem, we need to make some assumptions about the process of choosing. We assume that $108$ numbers are chosen "at random," one at a time, with replacement, from a set of $256$ numbers.

Imagine writing down the chosen numbers as a sequence of length $108$. There are $256^{108}$ such sequences, all equally likely. This number will be the denominator of our probability.

Now we calculate the number of "good" sequences, that is, sequences that have exactly $6$ distinct pairs, and $96$ singles. The types of the pairs can be chosen in $\binom{256}{6}$ ways. Once we have settled on our $6$ types, imagine ranking the chosen types in some arbitrary way, say numerical, but it doesn't matter.

Decide on the locations of the two numbers of the highest ranked type. This can be done in $\binom{108}{2}$ ways. For each of these ways, the locations of the two numbers of the next highest ranked type can be chosen in $\binom{106}{2}$ ways, and for each of these the locations of the two numbers of the next type can be chosen in $\binom{104}{2}$ ways, and so on. So the full task of dealing with pairs can be done in $$D=\binom{256}{6}\binom{108}{2}\binom{106}{2}\binom{104}{2}\binom{102}{2}\binom{100}{2}\binom{98}{2}$$ ways.

Now we have $96$ empty slots left. The first can be filled in $250$ ways. For each of these ways, the second empty slot can be filled in $249$ ways, and so on. Finally, the $96$th empty slot can be filled in $250-96+1$ ways. So our task of filling the $96$ slots can be done in $$S=(250)(249)(248)\cdots(156)(155)$$ ways.

So the number of ways we can have $6$ distinct pairs and the rest singles is $DS$. For the probability, divide $DS$ by $256^{108}$.

First I choose 102 distinct numbers, which can be done $256 \cdot 255 \cdot 254 \cdots 155 = \frac{256!}{154!}$ ways. Than I choose 6 numbers from these 102 previously choosen. Each of these 6 numbers will be paired with the same number. So I think the probability is $\frac{\binom{102}{6} \frac{256!}{154!}} {256^{108}}$.

• I don't think your pairing works properly. You have not selected where the second element of the pairs go in the series. Also by your argument, the 108 should be 102. – Ross Millikan Jun 20 '12 at 21:40
• You are right, I will try to modify my solution. – mcihak Jun 20 '12 at 21:55