Counting Nearest Neighbors that Stay Nearest Neighbors after Random Rearrangements 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.
 A: 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.
