# Overlap among binary sequences

Suppose we have $$K$$ elements to form sets with unique elements (null set not included). For example, for $$K = 2$$, we can have three sets possible sets as $$\lbrace 1 \rbrace$$, $$\lbrace 2 \rbrace$$, and $$\lbrace 1, 2 \rbrace$$. So for any $$K \in \mathbb{Z}^{+}$$, there are total $$2^K -1$$ possible sets.

Now a person, say Adam, wishes to choose one of these $$2^K -1$$ sets at random, i.e., each set is chosen with probability $$\frac{1}{2^K -1}$$. Then, other person, say Bob, chooses his set from these $$2^K -1$$ sets at random.

What is the probability that the set chosen by Bob has $$n$$ (with $$n \in \lbrace 0, 1, 2, \dotsc, K\rbrace$$) elements in common with Adam's chosen set? For example, for $$K = 3$$, let us say Adam chooses the set $$\lbrace 2, 3 \rbrace$$ and Bob chooses $$\lbrace 1, 2, 3 \rbrace$$. Then their chosen sets have $$n = 2$$ elements common. If Bob chooses $$\lbrace 1, 3 \rbrace$$, their chosen sets have $$n = 1$$ element common.

My attempt: I tried to represent the sets as binary sequences of length $$K$$. I set $$k$$th position to $$1$$ if the element $$k$$ is present in the chosen set, otherwise to $$0$$. For example, for $$K = 3$$ where Adam chooses the set $$\lbrace 2, 3 \rbrace$$ and Bob chooses $$\lbrace 1, 3 \rbrace$$ , it is equivalent to say that Adam has chosen the binary sequence ($$011$$) and Bob has chosen ($$101$$). But I am unable to calculate the probability for any general values of $$K \in \mathbb{Z}^{+}$$ and $$n$$.

Well, first we choose the overlap. Since the overlap is $$n$$, there are $$\binom{k}{n}$$ ways to do so. Now for each of the remaining elements, either Adam owns it, Bob owns it, or neither owns it. Three choices each, so $$3^{k-n}$$ ways to do this. Thus in total the answer is $$\binom{k}{n}3^{k-n}$$ ways, or a chance of $$\frac{\binom{k}{n}3^{k-n}}{(2^k-1)^2}$$ as long as $$n\neq0$$. For $$n=0$$, there is one possibility that needs to be ruled out, that of a zero-element set being chosen. We simply count how many ways there are for this to happen ($$2^{k+1}-1$$) and subtract from the total number of ways, thus giving us a probability of $$\frac{3^k-2^{k+1}+1}{(2^k-1)^2}$$