# Probability that subsets intersect

Given a set $N$ I would like to calculate the probability that two arbitrarily chosen and equally likely subsets $K\subseteq N$ and $J\subseteq N$ both of fixed size intersect. Let's say $n=\#N$, $k=\#K$, and $j=\#J$ denote the number of elements of the respective sets. The probability should be called $\rho(p,j,k)$ and so far I think I have two formulas which do the job.

The first is recursively defined as:

$$\rho(p,j,k)=\begin{cases}\frac{k}{n}+\frac{n-k}{n}\cdot\rho(j-1,k,n) & \text{if j>0},\\ 0 & \text{otherwise}.\end{cases}$$

The idea is that taking the first element of $J$ there is a chance of $\frac{k}{n}$ that it will be an element of $K$. If not, i.e. with a probability of $1-\frac{k}{n}=\frac{n-k}{n}$ there might be the probability that the next element will be in $K$ and so on.

I have an explicit formula as well:

$$\rho(p,j,k)=\frac{k}{n}+\frac{k(k-1)}{n^2}+\cdots+\frac{k(k-1)\cdots(k-j+1)}{n^j}$$

The idea here is that either one element of $J$ is in $K$ (Probability: $\frac{k}{n}$) or two elements of $J$ are in $K$ (Probability: $\frac{k(k-1)}{n^2}$) and so on...

Now I have two questions:

• First, I think I need to assume that $j\le k$ and I would like to not put any restrictions on the sizes of the sets.

• Second, the problem seems very general so I wonder whether there is some known obvious result to it which I am overlooking.

I suppose that $k=\#K$ and $j=\#J$ are given. The number of all $J$'s is $\binom{n}{j}$, the number of those $J$'s that don't intersect $K$ is $\binom{n-k}{j}$, so the probability that $K$ and $J$ don't intersect is $\binom{n-k}{j}/\binom{n}{j}$.
• I think I did not know the answer. My formulas assume that $j\le k$ whereas your equation is symmetric with respect to $j$ and $k$. – Rupert Jones May 14 '13 at 9:29