I had a chat with a friend about these questions (they are homework questions) , and we argued about the solution. I would just like an outside opinion about my answers:
1) $n \geq 2$ people are sitting on a bench at a restaurant. The menu has $m \geq 2$ items. Find a recursive function that finds the number of possible combinations of people ordering food, such that no 2 adjacent people have ordered the same meal.
For example, if Bob sits at chair 2, and John sits at chair 3, and they both order pizza, that combination is not valid.
2) Same question, but this time they are sitting at a round table.
1) let $f(n)$ be the number of valid combinations for a bench with length $n$. Look at the person that sits at the end of the bench. He has $m-1$ possible meals to order from (because the one next to him already ordered something, and they can't order the same thing). so overall: $f(k) = (m-1)f(k-1)$, $k \geq 3$ , $f(2) = m(m-1)$
2) Same logic but takes it another step. The person at the seat $n$ has $m-2$ options to order (he can't order what the guy in seat $1$ ordered and he can't order what the guy in seat $n-1$ ordered). The guy in seat $n-1$ had $m-1$ meals to choose from (he can't order what the guy in chair $n-2$ ordered, and the guy in chair $n$ didn't order yet so we don't need to pay him attention!) overall: $f(k)=(m-2)(m-1)f(k-2)$, $k \geq 4$, $f(2)=m(m-1)$, $f(3)=m(m-1)(m-2)$
The numbers seem to support my answers but I would like someone to verify, comment, and suggest ways to improve.