[Math] Probability that no two people sit next to each other

combinatoricsprobability

Assume there are 10 people sitting around a circular table for lunch and those same 10 people meet again during dinner. I am interested in the probability no one sits next to the same person (I interpret "sitting next to" as being on left or right of the person).

I ran a simulation and after 1 million randomizations comparing the lunch seating to the dinner seating, I got exactly 1 scenario that occurred where this happened. Is there a rigourous way to see if my simulation is correct?

Best Answer

You asked in comments how I got $181440$ or $14963$. The former is $9! / 2$ which is the number of possible arrangements at the second sitting, after taking into account rotations and reflections. Just taking into account rotations it would be $9! = 362880$

The number with no duplicated neighbours I got with the following R code, using the combinat package to generate all $362880$ possibilities with the person $1$ in the first place, and counting:

library(combinat)
seated <- 10
perms <- matrix(unlist(permn(seated-1)), ncol = seated-1, byrow = TRUE)
permsextended <- cbind(1, perms+1, 1) 
pairs <- 100 * permsextended[,-(seated+1)] + permsextended[,-1]
originalpairs <- c(100*(1:(seated-1)) + (2:seated), 100*seated + 1,
                   100*(2:seated) + (1:(seated-1)), 100*1 + seated)
dupes <- matrix(pairs %in% originalpairs, ncol=seated)
totaldupes <- rowSums(dupes)
nodupes <- permsextended[totaldupes==0, -(seated+1)]

That gives 

> nrow(nodupes)
[1] 29926
> nrow(nodupes) / factorial(seated-1)
[1] 0.08246803

and I divided $29926$ by $2$ to get $14963$.

These are the first few examples found

> head(nodupes)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    1    7    2    9    3   10    4    6    8     5
[2,]    1    7    2   10    3    9    4    6    8     5
[3,]    1    7    2    9    3    8    4    6   10     5
[4,]    1    7    2   10    3    8    4    6    9     5
[5,]    1    7    2    8    3   10    4    6    9     5
[6,]    1    7    2    8    3    9    4    6   10     5

There are further curiosities in the data. For example if you number the first sitting from $1$ to $10$, those with even numbers then are more likely to be sitting directly opposite person $1$ in the second sitting, i.e. in the sixth relative position: 

> table(nodupes[,6])
   2    3    4    5    6    7    8    9   10 
4318 2844 3186 3048 3134 3048 3186 2844 4318

If instead of a full count, I do a simulation (no longer constraining player $1$ in the second sitting), I get something similar with 

set.seed(1)
cases <- 1000000
seated <- 10 # should be less than 100
originalpairs <- c(100*(1:(seated-1)) + (2:seated), 100*seated + 1,
                   100*(2:seated) + (1:(seated-1)), 100*1 + seated)
runningcount <- 0
for (i in 1:cases){
    example <- sample(seated)
    examplextend <- c(example, example[1])
    examplepairs <- 100 * examplextend[-(seated+1)] + examplextend[-1]
    runningcount <- runningcount + (sum(examplepairs %in% originalpairs)==0)
    }

getting 

> runningcount / cases 
[1] 0.082199
Related Question