2
$\begingroup$

Imagine we are making necklaces with $n$ beads, each bead is a different color from all others. Let's say we make one necklace. If we make another necklace with the same $n$ differently colored beads, choosing each bead at random, what is the chance that exactly $k$ of the $n$ nearest neighbor pairs of beads from the original necklace will also be nearest neighbors in the second necklace?

Similarly, consider $n$ people standing in a queue. How many pairs of people standing next to each other in the first queue will also stand next to each other in a second queue, if the placements are reordered completely randomly? What is the form of $A(n,k)$, the number of ways to arrange the people such that exactly $k$ of the original $n$ are still neighbors?

I am interested in counting the number of these pairs as a function of $n$ in $S_{n}$ and certain subgroups. A generating function giving the fraction of the permutations having $i={0,1,2,..n}$ shared adjacent pairs would be particularly interesting to me, but terminology, references or general guidance might be more helpful so I could pursue this further on my own.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ For the case of zero adjacent pairs, see OEIS A002464. Perhaps some of the references there will treat your more general question. $\endgroup$
    – Richard Stanley
    Commented Jan 24, 2012 at 14:42
  • $\begingroup$ Let me piggyback on this. mathoverflow.net/questions/31364/… has a couple of Shellsort analysis references which may provide you with good search terms. Further, if you find more on inversion density, I'd appreciate a comment to that effect. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 $\endgroup$
    – Gerhard Paseman
    Commented Jan 24, 2012 at 18:11
  • $\begingroup$ Thanks Richard, the reference there by D. P. Robbins, "The probability that neighbors remain neighbors after random rearrangements. Amer. Math. Monthly 87 (1980), 122-124." looks particularly helpful. $\endgroup$
    – Jesse W. Collins
    Commented Jan 24, 2012 at 19:28
  • $\begingroup$ I was going to delete this post and move the question to Mathematics Stack Exchange, but as long as I continue to receive helpful comments I will leave it here. $\endgroup$
    – Jesse W. Collins
    Commented Jan 24, 2012 at 19:29
  • 1
    $\begingroup$ You might add a reference-request tag, as that part of the question makes it (in my view) quite suitable for MathOverflow. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 $\endgroup$
    – Gerhard Paseman
    Commented Jan 24, 2012 at 19:35

1 Answer 1

Reset to default
4
$\begingroup$

An analytical solution to this question was given by David P Robbins in "The probability that neighbors remain neighbors after random rearrangements. Amer. Math. Monthly 87 (1980), 122-124." He uses an inclusion-exclusion argument to find an expression for $A(n,k)$, the number of random rearrangements that have exactly $k$ nearest neighbors from the original set of $n-1$ nearest neighbors if the objects are placed on a line such that the 1st and nth objects are not neighbors.

Bengt Aspvall and Frank Liang discuss the case in which the nth and 1st distinguishable things are nearest neighbors in "The Dinner Table Problem," Stanford Dept. of Computer Science Report, Dec. 1980. They do not report a closed-form solution for $A(n,k)$, but they do some analysis to argue that the limiting result in the case of large $n$ is the same as in the case discussed by Robbins. In either case, the limiting behavior is

$\lim_{n \to \infty}\frac{A(n,k)}{n!}=\frac{2^{k}}{k!}e^{-2}$

In other words, as $n$ goes to infinity the number of ways to rearrange the $n$ objects while preserving $k$ nearest neighbors falls on a Poisson distribution with a mean of k=2.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .