7
$\begingroup$

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?

$\endgroup$
12
  • $\begingroup$ Its probably easier to start by thinking about one person. What's the probability that that person during dinner, does not sit next two either of the two people he/she sat next to during lunch? $\endgroup$ Jul 22, 2017 at 21:57
  • 1
    $\begingroup$ There are $10!$ ways of seating the ten people, but they can be divided into equivalent sets of $20$ by rotation or reflection. So the denominator of the probability must be $181440$ or a divisor of that, suggesting your simulation underestimated the probability $\endgroup$
    – Henry
    Jul 22, 2017 at 21:58
  • $\begingroup$ Place first person, now two of the remaining 7 must sit next to him because 2 are disqualified. Two of the remaining 7 must then sit next to them, but again two are disqualified, that leaves us with 5 people to choose from to sit at position 4 and 5. 6 and 7 we have 3 to choose from , but 8 and 9 will be only one left but two should be placed which we can't do, so maybe the numerator is 0 ( or I am being too tired to think straight ). $\endgroup$ Jul 22, 2017 at 22:07
  • $\begingroup$ @mathreadlern That reasoning doesn't work, since some of the earlier disqualified people may be seated at some later spot again. Indeed, there are ways to do this, e.g.1920364758 works. I don't think this is a nice function though, so brute forcing them by a computer may be the way to go on this one. $\endgroup$
    – Bram28
    Jul 22, 2017 at 22:16
  • $\begingroup$ there's a lot of cases to consider, but you could consider, how many arrangements have the same two people next to a single chosen person . etc. $\endgroup$
    – user451844
    Jul 22, 2017 at 22:29

2 Answers 2

1
$\begingroup$

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
$\endgroup$
4
  • $\begingroup$ I am still confused. I understand that the total number of ways 10 people can be seated around a circular table is 9!. $\endgroup$
    – northcity4
    Jul 25, 2017 at 20:19
  • $\begingroup$ Sorry, please ignore previous comment (pressed enter by error). Why divide the 29926 by 2? $\endgroup$
    – northcity4
    Jul 25, 2017 at 20:34
  • $\begingroup$ @northcity4 I believe he is dividing by 2 since he is considering two arrangements which are reflections of each other as being the same; and this is why he also divided 9! by 2. $\endgroup$
    – user84413
    Jul 25, 2017 at 21:29
  • $\begingroup$ @Henry Literally just found the error in my code. I will accept Henry's answer considering all the help he did give. Although I would, outside of this thread, like to continue some more questions regarding this problem and some of your methods mentioned here. $\endgroup$
    – northcity4
    Jul 26, 2017 at 0:48
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .