Number of ways to select k people from a round table of n people so that no two selected people sit next to each other.
I tried the followings.
k = 1, Number of ways = n
k = 2, Number of ways = n * (n-3)
k = 3, for the first person, we have n choices
for the second person:
Case 1: we can select the person sitting next next to the first person, so we have 2 choices for the second person, and the third person we have n-5 choices.
Case 2: we select the remaining people other than those in case 1, so we have n-5 choices for the second person, and the third person we have n-6 choices.
Then, the number of ways = Case 1 + Case 2 = n*2*(n-5) + n*(n-5)*(n-6)
For k >= 4, it seems that there are many cases for each step, so is there any better way to generalize the formula to select k people?
Best Answer
The following extra information is useful in solving the problem: One of the people at the table is Alicia.
We count the number of selections that do not contain Alicia, and the selections that contain Alicia.
For the selections that do not contain Alicia, we need to choose $k$ people from the remaining $n-1$. It is easiest to view the situation as occurring on a line, and to change language a bit. Also, for concreteness, we use specific numbers.
Let $n-1=13$ and $k=4$. There are $9$ adults and $4$ children. We want to seat them in a row so that no two kids are next to each other. Line up the adults this way. $$A\qquad A\qquad A\qquad A\qquad A\qquad A\qquad A\qquad A\qquad A$$ Now the $4$ children choose $4$ "gaps" to sit in. There are $8$ interadult gaps, and $2$ endgaps, for a total of $10$. So the number of choices is $\binom{10}{4}$.
Precisely the same reasoning shows that the number of choices that do not include Alicia is $\binom{n-k}{k}$.
For the choices that include Alicia, we need to choose $k-1$ people from the $n-3$ allowed choices, since we cannot use Alicia's neighbours. The number of choices is $\binom{n-k-1}{k-1}$.
That gives a total of $\binom{n-k}{k}+\binom{n-k-1}{k-1}$.