Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You have a circular table with $N$ seats.$K$ bellicose guests are going visit your house of-course you don't want them to sit beside each other.As the host, you want to find out how many ways there are to choose $K$ seats such that none of them is adjacent to each other.

I noticed that there is a solution other than $0$ if ($N \ge 2K $) but I am not sure how to approach for the rest.

EDIT: Only $K$ bellicose guests are visiting,no friendly guest are there the remaining $N-K$ seats will be vacant.

A possible mathematical translation of this problem: Choosing $K$ candidate points from a circle of $N$ indistinguishable points such that there are more than one vacant point between adjacent candidate points.

share|improve this question
    
Up to rotation or not? If not, try fixing K and seeing if you can write down a recurrence in terms of N. –  Qiaochu Yuan Jan 8 '11 at 13:46
2  
@ Qiaochu Yuan: Please rephrase, I don't understand what you meant by "Up to rotation or not". –  Quixotic Jan 8 '11 at 13:48
    
Qiaochu is asking (since the table is circular) whether your count of solutions should treat a rotation of a solution as another solution (or just count rotationally equivalent solutions as one). Also notice that you've misstated the inequality: should be $N \ge 2K$ to get solutions. –  hardmath Jan 8 '11 at 14:38
    
@hardmath: I am not sure whether the clock-wise or anticlockwise solution are treated different of not. –  Quixotic Jan 8 '11 at 14:45
    
Right, I'd assume those (reflections) are counted differently, although of course "who sits next to whom" will be the same. A reflection is never a rotation except for the trivial case N=2, so there's not really a conflict in saying we want to identify rotationally equivalent solutions but distinguish reflections. –  hardmath Jan 8 '11 at 15:13
show 3 more comments

2 Answers

up vote 4 down vote accepted

Choose a seat $S$, and a bellicose guest $B$. Sit $B$ in $S$, and tell them not to move, whether they like it or not. That done, there are $(K-1)!$ ways of ordering the remaining bellicose guests clockwise around the table, and $F!$ ways of ordering the friendly guests (here I am using leonbloy's notation $F = N - K$). For each such ordering, we have to choose a pattern of the form $f...b...f...b...f$. This pattern:
1. starts and ends with $f$ (so that $B$ is isolated);
2. contains $(K-1)$ $b$'s and $F$ $f$'s; and
3. contains no two adjacent $b$'s.

But the number of such patterns is the same as the number of patterns that
1. start with $f$; and
2. contain $(K-1)$ $b$'s and $(F-K+1)$ $f$'s.

(To see this, just replace each instance of $bf$ in the original pattern by $b$.) The number of such patterns is the binomial coefficient $\binom{F-1}{K-1}$. So we end up with:

$(K-1)!F!\binom{F-1}{K-1} = \frac{F!(F-1)!}{(F-K)!}$

This is the number of seating arrangements with guest $B$ in seat $S$. Multiply by $N$ to get the total number.

Edit Reading the question more carefully, it asks for the number of (what I call here) patterns, not the number of seatings. For each pattern, there are $K!F!$ seatings, so the answer is

$N\frac{F!(F-1)!}{(F-K)!}/(K!F!) = \frac{N(F-1)!}{(F-K)!K!}$

share|improve this answer
    
Seems right to me. Just to clarify: "This is the number of seating arrangements with guest B in seat S" means: with "a particular B guest (say b1) in seat S", not "with some belicose guest in seat S". –  leonbloy Jan 9 '11 at 0:13
    
@leonbloy: I suggest that my answer was perfectly clear on that point. I think you must have forgotten the first two sentences by the time you reached the last two. –  TonyK Jan 9 '11 at 0:22
    
In TonyK's counting the seats have name tags. If you only distinguish between white and black seats you have a different problem, see my former comment on this question. Maybe the proposer should clarify this point. –  Christian Blatter Jan 9 '11 at 11:59
    
Let $N = 4$ and $K = 2$ we get $F = 2$ then your formula is giving $2 \times N = 8$ but given answer is $2$. –  Quixotic Jan 9 '11 at 12:28
    
@Christian Blatter: My first result is the number of seating arrangements with B in S, which is the same as the number of seating arrangements counting rotations (but not reflections) as identical. Now just multiply this by N to get the number of seating arrangements counting rorations as distinct. No special Polya theory is required. –  TonyK Jan 9 '11 at 12:29
show 5 more comments

Let's call $F=N-K$ number of "friendly" guests. And let's call $S(F,K)$ the count of seating ways assuming that seats and guests are distinguible (rotations are distinct solutions).

We know that $F \ge K$. For the limit case $F = K$ we have $S(F,K) = 2 K (K-1)! K! = 2 K!^2$.

Now, the recursion: we count the number of ways when adding a friendly guest:

$S(F+1,K) = (F+K+1) S(F,K)$

From this (if it's correct!) you can get an explicit solution.

Update: this is not correct. See TonyK's answer

share|improve this answer
    
I don't think your recursion is right. Adding a friendly guest between two bellicose guests can transform an invalid seating into a valid one. Also it doesn't agree with the formula in my answer :-) –  TonyK Jan 8 '11 at 20:02
    
@TonyK: you're right –  leonbloy Jan 9 '11 at 0:00
    
No friendly guests are there,please read my question. :-) –  Quixotic Jan 9 '11 at 15:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.