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.

$\endgroup$
8
  • $\begingroup$ Up to rotation or not? If not, try fixing K and seeing if you can write down a recurrence in terms of N. $\endgroup$ Jan 8, 2011 at 13:46
  • 2
    $\begingroup$ @ Qiaochu Yuan: Please rephrase, I don't understand what you meant by "Up to rotation or not". $\endgroup$
    – Quixotic
    Jan 8, 2011 at 13:48
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Jan 8, 2011 at 14:38
  • $\begingroup$ @hardmath: I am not sure whether the clock-wise or anticlockwise solution are treated different of not. $\endgroup$
    – Quixotic
    Jan 8, 2011 at 14:45
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Jan 8, 2011 at 15:13

2 Answers 2

4
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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". $\endgroup$
    – leonbloy
    Jan 9, 2011 at 0:13
  • $\begingroup$ @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. $\endgroup$
    – TonyK
    Jan 9, 2011 at 0:22
  • $\begingroup$ 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. $\endgroup$ Jan 9, 2011 at 11:59
  • $\begingroup$ Let $N = 4$ and $K = 2$ we get $F = 2$ then your formula is giving $2 \times N = 8$ but given answer is $2$. $\endgroup$
    – Quixotic
    Jan 9, 2011 at 12:28
  • $\begingroup$ @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. $\endgroup$
    – TonyK
    Jan 9, 2011 at 12:29
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 :-) $\endgroup$
    – TonyK
    Jan 8, 2011 at 20:02
  • $\begingroup$ @TonyK: you're right $\endgroup$
    – leonbloy
    Jan 9, 2011 at 0:00
  • $\begingroup$ No friendly guests are there,please read my question. :-) $\endgroup$
    – Quixotic
    Jan 9, 2011 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .