# No of ways of allotting 4 dishes to n days [duplicate]

Possible Duplicate:
In how many ways can we colour $n$ baskets with $r$ colours?

There are n days and 4 types of dishes.Any 1 of 4 dishes is alloted to each day. And dishes of the consecutive days must be different.The dish of the first day and the dish of the last day must be different too.In how many ways can this be done.

For example,if n=2,then total number of ways is 4*3=12

if n=3,then total number of ways is 4*3*2=24

similarly for n=5,total number of ways should be 4*3*3*3*2=216 but 216 is not the correct answer,the correct answer is 240.What am I missing out here ? Please help.

-

## marked as duplicate by joriki, Arkamis, Phira, Cameron Buie, nbubisNov 5 '12 at 18:28

For the last day, you gave that there are 2 possibilities, but that is not necessarily the case. What if the Day 1 Dish was the same as the Day 4 dish? Then the Day 5 dish has three possibilities. – Christopher A. Wong Oct 2 '12 at 21:51
Another verbal variant of a question asked several times in the last couple of days. If you look through posts, you will find some solutions of this problem. One was given by joriki. – André Nicolas Oct 3 '12 at 0:09

Let's call $T(n)$ the total number of ways of arranging the dishes without considering the restriction of the last-first dishes. Let $R(n)$ the same number having the last and first dishes different, and $S(n)$ having the same first-last dish.
Then, $T(n)= S(n)+R(n) = 4 \, 3^{n-1}$ for $n\ge 2$
And $S(n) = R(n-1)$, hence $R(n) = T(n) - R(n-1) = 4 \, ( 3^{n-1} - 3 ^{n-2} + \cdots)$
This is a geometric sum, and the result is $R(n) = 3^n +3(-1)^n$, so $R(2)=12$, $R(5)=240$