# 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?

-
I assume you mean if you put them in a straight line. For added complexity, consider "not next to each other" in a square layout – Viktor Mellgren May 12 '14 at 13:44
– Byron Schmuland May 12 '14 at 19:47
This isn't DRAM, is it? – The Masked Avenger May 12 '14 at 22:00

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$.

-

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.

-

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.

-
Via the thread linked in the other answer: the sequence ((2n)! - a_n)/(2n)! appears as oeis.org/A007060 – László Kozma May 13 '14 at 3:29

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).

-
You mean 13824, not 13834. – Byron Schmuland May 12 '14 at 19:46
thanks, corrected – Aaron Meyerowitz May 14 '14 at 8:18
There is one more 13834 to fix :) – Byron Schmuland May 14 '14 at 11:08

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)}.$$

-