arrange k identical robots in 15 chairs, with limitations I ran into this question, want to challenge you.
in how many ways can you arrange a number of identical robots on $15$ chairs?
limitations:
1) $2$ robots cannot sit next to each other.
2) each empty chair has at least one neighbour with a robot.
what i got so far: i know that it has something to do with $\sum_{5}^{8}$ because the minimum amount of robots is $5$ and maximum is $8$.
i'm not sure how to proceed from here though.
Thank you very much in advance,
Yaron
 A: Consider $xRExRExRExRExRx$.  The $R$'s stand for robots, the $E$'s stand for empty chairs.  All the $x$'s can be zero or one empty chairs.   However there are 15 chairs altogether, so in fact each $x$ must be one empty chair.
Consider now one more robot.  $xRExRExRExRExRExRx$.  We have six robots and five empty chairs accounted for, of 15 chairs.  That means there are four empty chairs to distribute among the seven possible $x$'s, which can be done in ${7\choose 4}$ ways.
I leave the cases of 7 or 8 robots for you to consider.
A: Hint:  Think about a recurrence.  Let $R(n)$ be then number of acceptable strings of length $n$ ending in $R, E(n)$ be the number of acceptable strings of length $n$ ending in $RE$, and $EE(n)$ the number of acceptable strings of length $n$ ending in $EE$.  We have $R(1)=1, E(1)=0, EE(0)=0, R(n)=EE(n-1)+E(n-1), E(n)=R(n-1), EE(n)=E(n-1)$  Can you see why?
For small $n$, a spreadsheet makes this easy.  For larger $n$, making a matrix and diagonalizing will solve it.
