Recurrence relation question - check my answers! Basic questions.

Question

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.

My answers:

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.

Answer 1

Part 1) sounds good.

For part 2) we have to be careful about the "last" person, because there may be $(m-1)$ or $(m-2)$ possibilities depending on whether friend $1$ and friend $n-1$ have chosen the same meal or not.

So what we could do is the following:

• Let $f_m(n)$ denote the number of ways $n$ friends can order $m$ meals with no coinciding adjacent meals on a bench.
• Let $g_m(n)$ denote the same number for a circular table.
• We cut the circle and obtain a bench at a fixed position. Every combination of meals on the circle also works on the bench.
• However, a combination of meals on the bench can be rearranged to the circular table if and only if the first and the last person do not have the same meal.
• If they have the same meal, we can push the last person off the bank. Then there are $n-1$ friends left and the first and the last have different meals.

• Hence, these friends can be rearranged on a table with $n-1$ seats.

• Conclusion:

  The number of combinations of meals on a circular table with $n$ seats is the number of combinations of meals on a bench with $n$ seats minus the number of combinations on a circular table with $n-1$ seats. That is $$g_m(n)=f_m(n)-g_{m}(n-1)$$