Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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
This answer adresses a similar but a little bit different problem, namely how many times can all the guests leave the round table, come back and take other seats such that they don't get the same neighbor neither to the right nor left as they had in the previous sitting. I assume we are not interested in seating sequences that just involves rotation or reflection so the sitting in a circle can be made linear by having the n guests sit in a straight line with guest 1 (the host) always sitting in the first seat and having his double sitting in a phantom n+1 st. seat at the end. This linear arrangement implies we only have to consider any guests right hand neighbor since the left hand neighbor has him as is right hand neighbor. Further it makes things easier to always start with the seating sequence 1 ,2, 3,....,n, 1 and we define right and left as 3 being to the right of 2 and vice versa,. Let us start with an example. Obviously a party with only 2,3 or 4 guests can not be seated more than 1 way without having at least 1 neighbor being the same. In the case of 5 guests we have the 2 following valid sample sequences, where the end seat is the phantom 1. In other words they can not find a valid sitting if they come back a third time.
1 2 3 4 5 1
1 3 5 2 4 1
Now suppose we add one more guest to the sample above. He can then sit anywhere but this will not give an extra sequence unless all the other guests shuffle around. But they can't do this because it would disrupt the original 2 possibilities so then at least one guest would invariably get the same neighbor as before. However, if not 1 but 2 more guests are added, then they can choose among several seats in the shown sequences and the guests can shuffle in such a way that the 2 extra guests can be seated to separate 2 guests that would otherwise have been previous neighbors thus getting 1 more valid seating sequence as illustrated below for 7 people
1 2 3 4 5 6 7 1
1 3 5 7 4 2 6 1
1 4 6 3 7 2 5 1
From this we conclude, that an extra new valid seating sequence can only be constructed by adding 2 more guests. Hence the basic valid seating sequences must comprise 5, 7, 9, 11, ..., people. We can thus proceed with considering only an uneven number of people n = 2m+1. Now all subsequent valid seating sequences after the first must require guest 1 to have guest 3, 4..., m as his right hand neighbor and guests number m+1, m+2, n-1 must have the phantom guest 1 as their right hand neighbor - or vice versa (which would not give a new valid sequence). Thus in order for the real guest 1 and the phantom guest 1 to have the same number of right hand neighbors (which is the same as requiring the real guest 1 in a circle to have an equal number of different left and right hand neighbors) there must be an uneven number of real guests, which confirms our first assumption of only having to consider uneven numbers. The total number of possible valid re-seating sequences can thus not exceed the integer m = [(n-1)/2] and by further considerations this limit also turns out to be the answer to the question of how many ways n people can return to be seated without ever having the same left or right hand neighbor as before. For reference, examples of valid re-seating arrangements for 9 and 11 persons are shown below.
1 2 3 4 5 6 7 8 9 1
1 3 5 7 2 4 9 6 8 1
1 4 8 5 9 2 6 3 7 1
1 5 2 8 3 9 7 4 6 1
1 2 3 4 5 6 7 8 9 10 11 1
1 3 5 7 2 10 4 9 6 11 8 1
1 4 8 10 5 9 11 2 6 3 7 1
1 5 2 8 3 9 7 11 4 6 10 1
1 6 8 5 11 3 10 7 4 2 9 1
