Return to Answer

added 5 characters in body

Source Link

edited Apr 2, 2012 at 0:14

Jesse W. Collins

161
8

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.

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.

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.

Source Link

created Apr 2, 2012 at 0:07

Jesse W. Collins

161
8

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.