9
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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 $\endgroup$ May 12, 2014 at 13:44
  • 2
    $\begingroup$ See oeis.org/A007060 $\endgroup$
    – user6096
    May 12, 2014 at 19:47
  • $\begingroup$ This isn't DRAM, is it? $\endgroup$ May 12, 2014 at 22:00

5 Answers 5

7
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Via the thread linked in the other answer: the sequence ((2n)! - a_n)/(2n)! appears as oeis.org/A007060 $\endgroup$ May 13, 2014 at 3:29
4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ You mean 13824, not 13834. $\endgroup$
    – user6096
    May 12, 2014 at 19:46
  • 1
    $\begingroup$ There is one more 13834 to fix :) $\endgroup$
    – user6096
    May 14, 2014 at 11:08
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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