5
$\begingroup$

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.

  • 0
    I guess you mean "there is at least one vacant point" instead of "there are more than one vacant point".2011-01-09

2 Answers 2

4

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!}$

  • 0
    @Tretwick Marian: I wasn't the only one! But I think I've fixed my answer now -- it assumes that friendly guests will be present, but the final result doesn't depend on them.2011-01-09
1

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

  • 0
    No friendly guests are there,please read my question. :-)2011-01-09