Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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 –  Vixen May 12 at 13:44
2  
See oeis.org/A007060 –  Byron Schmuland May 12 at 19:47
    
This isn't DRAM, is it? –  The Masked Avenger May 12 at 22:00

5 Answers 5

up vote 7 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
Via the thread linked in the other answer: the sequence ((2n)! - a_n)/(2n)! appears as oeis.org/A007060 –  Laszlo Kozma May 13 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).

share|improve this answer
    
You mean 13824, not 13834. –  Byron Schmuland May 12 at 19:46
    
thanks, corrected –  Aaron Meyerowitz May 14 at 8:18
    
There is one more 13834 to fix :) –  Byron Schmuland May 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)}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.