Skip to main content
4 of 8
deleted 462 characters in body

Counting Nearest Neighbors that Stay Nearest Neighbors after Random Rearrangements

Imagine $n$ people sit down in $n$ seats around circular table to have breakfast. They all sit down at the same table for lunch later in the day. If the place each sits is completely random, what is the chance that exactly $k$ of the $n$ nearest neighbors at breakfast will also be nearest neighbors at lunch?

What if instead of a circular table, the people are standing in a line? 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.