Combinatorics - Check my answer, sitting order, round table.

Question

$n$ people are sitting at a round table with $n$ seats at a restaurant.

The restaurant has only 2 dishes, steak and salad. How many ways are there for the diners to choose a dish, such that no 2 adjacent diners have steak?

Here's what I did:

I tried to solve it with recurrence relation. Let's number the seats $1,...,n$, such that the guy in chair 1 orders first and so on. let $f(n)$ be the number of different valid orders.

The guy in the first chair can order whatever he wants. Let's suppose he orders the salad.

In that case, the guy in the second chair can order whatever he wants (since the guy next to him didnt order steak). so you could say that if the guy in chair $1$ ordered salad, there are $f(n-1)$ options for the other guys.

Now, if the guy in chair $1$ orders steak, then that means the guy in chair $2$ must order a salad, and then the guys in chairs $3,...,n-1$ can order whatever they want (that's $f(n-3)$ options) and then the guy in chair $n$ must order salad as well. so thats $f(n-3)$ options.

Overall we get $f(n)=f(n-1)+f(n-3)$ and now we just solve the recurrence relation.

Would this work?

Answer 1

As Hoda has pointed out in his comment your counting has a flaw.

To simplify matters we start by counting words of length $n$ over the alphabet $\{S,M\}$ ($S$ for "salad", $M$ for "meat") containing no two successive $M$'s. Denote by $f_{SS}(n)$ the number of such words beginning and ending with $S$, and define $f_{SM}(n)$, $f_{MS}(n)$, $f_{MM}(n)$ analogously. Then $$f_{SS}(1)=f_{MM}(1)=1,\qquad f_{SM}(1)=f_{MS}(1)=0\ .\tag{1}$$ The $f_{XY}$ satisfy the following recursion: For both $X=S$ and $X=M$ one has $$f_{XS}(n+1)=f_{XS}(n)+f_{XM}(n),\qquad f_{XM}(n+1)=f_{XS}(n)\qquad(n\geq1)\ .\tag{2}$$ From $(2)$ it follows that $$f_{XS}(n+2)=f_{XS}(n+1)+f_{XS}(n)\ ,\tag{3}$$ which implies that the $f_{XS}$ are related to the Fibonacci numbers $$(F_k)_{k\geq0}=(0,1,1,2,3,5,8,\ldots)\ ,$$ and the same will be true for the $f_{XM}$ according to the second formula in $(2)$. From $(1)$ and $(2)$ we deduce $$f_{SS}(2)=1,\qquad f_{SM}(2)=1,\qquad f_{MS}(2)=1,\qquad f_{MM}(2)=0\ .$$ Using $(3)$ and the same recursion for $f_{XM}(n)$ we therefore deduce that $$f_{SS}(n)=F_n,\quad f_{SM}(n)=F_{n-1},\quad f_{MS}(n)=F_{n-1},\quad f_{MM}(n)=F_{n-2}\qquad(n\geq2)\ .$$ All words not beginning and ending with $M$ can be used for the cyclic seating of $n$ people. It follows that the number $N(n)$ we are after is given by $$N(n)=f_{SS}(n)+f_{SM}(n)+f_{MS}(n)=F_n+2F_{n-1}\qquad(n\geq2)\ .$$

Answer 2

I am not sure if this is an answer, It's an answer to the problem but not your method and it's too long for a comment.

But I've calculated it by brute force with the following program testing all possible orders and I got the answer 322.

---

#include <stdio.h>

const int test[] ={
        0x0C00,  /* 1100 0000 0000 */
        0x0600,  /* 0110 0000 0000 */
        0x0300,  /* 0011 0000 0000 */
        0x0180,  /* 0001 1000 0000 */
        0x00C0,  /* 0000 1100 0000 */
        0x0060,  /* 0000 0110 0000 */
        0x0030,  /* 0000 0011 0000 */
        0x0018,  /* 0000 0001 1000 */
        0x000C,  /* 0000 0000 1100 */
        0x0006,  /* 0000 0000 0110 */
        0x0003,  /* 0000 0000 0011 */
        0x0801   /* 1000 0000 0001 */
};

int main (void){
    int count, ok = 0, i, pass = 0;

    /* A 1 in a bit for count represents someone ondering stake, a zero salad */

    for (count = 0; count < 4096; count++){
        ok = 1;
        for (i = 0; i < (sizeof (test)/sizeof(int)); i++){
            if ((count & test[i]) == test[i] ){
                ok = 0;
            }
        }
        if (ok != 0){
            pass++;
        }
    }
    printf("There are %d ways they can order \r\n", pass);
    return(0);
}