Selection in Circular Table 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?
 A: 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}$.
A: HINT: Imagine that you open up the circular seating arrangement into a single row. Everyone except the two people on the ends of the row still have the same neighbors. We want to choose $k$ of these people so that no two are adjacent and we don’t choose both of the people on the ends.
The $k$ chosen people potentially break the line up into $k+1$ segments, one to the left of the first chosen person, one between each pair of adjacent chosen people, and one to the right of the last chosen person. Now we insert the other $n-k$ people into these segments. We must insert at least one person into each of the $k-1$ middle segments, and we must insert at least one person into at least one of the end segments. Break it into three cases: someone in the left end segment but not the right, someone in the right end segment but not the left, and people in both end segments. Each case is a stars-and-bars problem.
That should at least get you started: if you get stuck, feel free to leave a comment.
