Probability of a pair of memory cards ending up as neighbors I am trying to compute the probability that after a perfect shuffling of a deck of memory cards (n pairs) none of the pairs end up with the two members next to each other.
I get into a messy inclusion-exclusion which I guess I could work through, but I wonder if there is a simpler argument I am missing.
A numerical simulation shows that the value seems to converge to around 0.36 ~ 1/e, which hints that there should be an easier argument.
Alternatively: what is the probability that a random permutation of [2n] has two neighbors with difference n?
 A: It's unlikely that there is an exact answer simpler than the inclusion-exclusion sum. One can also use much the same calculations to show that the number of matched pairs adjacent to each other is asymptotically a Poisson distribution with mean 1, so the limit probability is indeed $e^{-1}$.  To prove the Poisson limit, show that for any fixed $k$, the expected number of ordered $k$-tuples of adjacent matched pairs approaches 1 as $n\to\infty$.
A: Let $a_n$ be the number of permutations of $[2n]$ where (at least) two neighbors have difference $n$.
Then $a_n$ can be computed with the following Mathematica code:
a[n_]:=Length@Select[Permutations[Range[2 n]],MemberQ[Abs[Differences[#]], n] &];

The series $a_1,a_2,\dots$ starts as $2, 16, 480, 26496, 2365440$
and do not yield a hit in the OEIS, although, $\frac{(2n)!-a_n}{(2n)!}$ seem to approach $1/e$ from below.
A: later a mistyped digit made me miss the appropriate entry in the OEIS but, as long as this answer is here, I've revised it a bit.
The desired numbers $1,0,8,240,13824,1263360,\cdots$ satisfy the recurrence $$a_n=2n\left((2n-1)a_{n-1}+(2n-2)a_{n-2}\right).$$ Also, $a_n$ is a multiple of $2^nn!$, (explanation below)


*

*if we break $2n!$ into the number of permutations having $0,1,\cdots,n$ such pairs we get

*

*$1$

*$0,2$

*$8,8,8$

*$240, 288, 144, 48$

*$13824, 15744, 8064, 2304, 384$

*$1263360,1401600,710400,211200,38400,3840$



The final number in each list is $2^nn!$ and in fact every entry in the nth row is a multiple of $n!2^n$ because swapping the positions of $i,i+n$ does not affect the number of pairs nor does any permutation of $1\cdots n$ extended to send $i+n$ to $j+n$ when $i$ goes to $j$.
The first entries $1,0,8,240,13824,1263360$ are the desired ones. 
It might be worth examining the number which do not have any pair $i,i+n$  and/or the number of circular permutations with no pair differing by $n$ (exactly or in absolute value).
Since the terms  $1,0,8,240,13824,1263360$ grow like $\frac{2n!}{e}$. I wonder if this sequence (also) lurks in the OEIS as the even position terms of a sequence which grows like $\frac{n!}{e}$ (as do derangement, scrambles and other pattern avoiding permutation counts). Perhaps something like permutations of $1,2,\cdots,m$ where no adjacent pair has difference $\lfloor\frac{m}{2}\rfloor$ (or maybe  $\lceil\frac{m}{2}\rceil$.) Perhaps in the odd case $m=2n-1$ one should also forbid $n$ from being at the start ( or start and end).
A: The inclusion-exclusion answer can be written in a way that makes it obvious that the answer is $e^{-1}$. The probability is
$$1 - 1 \frac{(2n-1)}{(2n-1)} + \frac{1}{2} \cdot \frac{(2n-1)(2n-2)}{(2n-1)(2n-3)} - \frac{1}{3!} \cdot \frac{(2n-1)(2n-2)(2n-3)}{(2n-1)(2n-3)(2n-5)} +$$
$$\cdots + (-1)^k \frac{1}{k!} \cdot \frac{(2n-1)(2n-2) \cdots (2n-k)}{(2n-1)(2n-3) \cdots (2n-2k+1)} + \cdots.$$
Here terms of the form $0/0$ are interpreted as $0$.
As $n \to \infty$, the $k$-th term approaches $(-1)^k/k!$ (and it wouldn't be hard to establish uniform convergence).
Specifically, choose a specific $k$-element subset $(d_1, d_2, \ldots, d_k)$ of $\{ 1,2, \ldots, n \}$. The probability that each of the $d_i$ pairs will wind up consecutive is
$$\frac{(2n-1)(2n-2) \cdots (2n-k)}{(2n)(2n-1)(2n-2)(2n-3) \cdots (2n-2k+1)/2^k} \quad (\ast).$$
The numerator of $(\ast)$ is the number of ways to choose consecutive positions in which to place the $(d_i, d_i)$ pairs, and the denominator is all ways to choose $2k$ elements out of $2n$ and pair them off.
To get the final probability, multiply $(\ast)$ by $\binom{n}{k}$ (because there are $\binom{n}{k}$ choices for $(d_1, \ldots, d_k)$) and take the alternating sum. A bit of algebra turns
$$\frac{n(n-1)\cdots (n-k+1)}{k!} \cdot \frac{(2n-1)(2n-2) \cdots (2n-k)}{(2n)(2n-1) \cdots (2n-2k+1)/2^k}$$
into
$$\frac{1}{k!} \cdot \frac{(2n-1)(2n-2) \cdots (2n-k)}{(2n-1)(2n-3) \cdots (2n-2k+1)}.$$
A: There is an explicit integral formula for your probability, as well. Using 
ideas from algebraic combinatorics, you can write the probability as 
$${1\over (2n)!}\int_0^\infty (x^2-2x)^n \exp(-x)\,dx. $$
I learned this from Jair Taylor's MSE answer here.
