Assume I have $2n$ unique members of a set. Now assume that each element of that set is assigned an integer $\in (0,n]$, such that each integer is used twice. So for example if you have a set of 4 elements which we label $\{A,B,C,D\}$, then two elements will be labeled with 1 and two will be labeled 2, e.g. you might get the labeled set: $\{(A,1),(B,1),(C,2),(D,2)\}.$
Now assume the labels of the $2n$ elements are completely randomized. My question is, what is the probability $p_n$ that no pair of elements that shared a label, both got that same label again (for arbitrary values of $n$)? To continue the example before (for $n=2$), the 6 distinct ways the 4 labels can be arranged are: $$\{(A,1),(B,1),(C,2),(D,2)\}\\ \{(A,1),(B,2),(C,1),(D,2)\}\\ \{(A,1),(B,2),(C,2),(D,1)\}\\ \{(A,2),(B,1),(C,1),(D,2)\}\\ \{(A,2),(B,1),(C,2),(D,1)\}\\ \{(A,2),(B,2),(C,1),(D,1)\}.$$ Because there is only one case where either $A$ and $B$ where both reassigned 1 and/or $C$ and $D$ where reassigned 2, the probability for $n=2$ is $p_2=5/6$.
Ideally I would like a closed form solution for $p_n$, but I'd also settle for a recursive formula (which could e.g. be used to numerically compute $p_n$ by say an iterated python script)
You want to avoid having any of the $n$ events which consist of each of the $n$ pairs repeating, we can get the probability of this with inclusion exclusion.
Let $f(n)$ be the number of labels on $2n$ elements, where $f(0) = 1, f(1) = 1, f(2) = 6$ etcetera.
The probability that a given subset of $k$ pairs repeats is $\frac{f(n-k)}{f(n)}$, because there are $f(n-k)$ ways to label the remaining $2(n-k)$ elements.
Hence via inclusion-exclusion the probability that no event happens is:
$1 + \sum\limits_{k=1}^n (-1)^k \binom{n}{k}\frac{f(n-k)}{f(n)}$.
Where $f(n)$ is $\frac{(2n)!}{2^n }$