# Sitting around a round table in circular permuations

If $3$ people are selected at random from $15$ people sitting at a round table, then what is the probability that no two of them are adjacent to each other?

If no-one can sit next to someone else, then three seats are blocked every time someone sits down. However, some of these may have been blocked already, by previous sitters. So, the first person to sit down has $15$ choices, and leaves twelve choices. The next person to sit down has $12$ choices; in two of these cases, he leaves ten choices; in the other ten cases, he leaves nine. The final person to sit down has either $10$ or $9$ choices, depending on what the second person did. The result is $$N=15\cdot(2\cdot10+10\cdot9)=1650$$ ways for three (distinguishable) people to sit down. The probability, then, is $$p=\frac{N}{15\cdot14\cdot13}=\frac{1650}{2730}=\frac{55}{91}.$$

This can be generalized to x people in y seats. As Andre noted, you can use symmetry, but I will assume seat 0 is open.

Let's have "O" refer to an open seat and "F" refer to a filled seat. Then every table combination can be expressed as a combination of (O) and (F) strings, and every legal table combination with seat 0 open can be expressed by a combination of (O) and (OF) strings.

Any seating combination, legal or not, is made up of x (F) and y-x (O) strings. But since it must start with an (O), that leaves y-x-1 (O) and x (F) in the last y-1 slots, so you have ${ y-1 \choose x}$ total combinations.

Any legal seating combination will contain x (OF) and y-2x (O) strings. That means you have ${ y-x \choose x }$ legal combinations.

That makes ${ \frac{y-x \choose x}{y-1 \choose x}}$ our more general answer. I don't think the combinations can be reduced to something simpler, though

${ \frac{(y-2x+1) * ... * (y-x-1)}{(y-x-1) * ... * (y-1)} }$ might help to visualize this. This assumes x > 1, which is okay, since x=0 or 1 is trivial.

Hint: By symmetry, without loss of generality we can assume that Alicia is chosen. Now how many ways are there to choose $2$ people from the $14$ remaining ones to accompany Alicia? How many ways are there to choose $2$ people so they are not next to Alicia or to each other?

Added: Since we have already done it in comments, we might as well add more detail. For the numerator, the $2$ people (seats) next to Alicia are forbidden, so we are choosing $2$ from the remaining $12$. But some of these choices are forbidden, the choices in which we have a pair of neighbouring seats. A little play will show that of the $\binom{12}{2}$ ways to choose $2$ people who are not next to Alicia, $11$ are forbidden.

• We can select any $3$ out of $15$ is $\displaystyle =\binom{15}{3}$ ways – juantheron Jan 29 '13 at 17:58
• What if there are $k$ tables? – alancalvitti Jan 29 '13 at 18:06
• actually i did not understand would you like to explain me completely thanks – juantheron Jan 29 '13 at 18:09
• For the numerator, there are $12$ seats (people) left to choose from, since Alicia's is taken and the two next to her are forbidden. From these $12$, we choose $2$ not next to each other. There are $\binom{12}{2}$ ways to choose $2$ seats from $12$. But $11$ of these choices are forbidden, since they give an adjacent pair. You should end up with numerator $55$, denominator $105$. – André Nicolas Jan 29 '13 at 18:31
• @AndréNicolas: The denominator had better be ${{14}\choose{2}}=91$, since you've already chosen Alicia. – mjqxxxx Jan 29 '13 at 19:02