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.

  • 2
    $\begingroup$ 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. $\endgroup$ Oct 2, 2012 at 21:51
  • $\begingroup$ 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. $\endgroup$ Oct 3, 2012 at 0:09
  • $\begingroup$ math.stackexchange.com/questions/206016/… $\endgroup$
    – user940
    Oct 3, 2012 at 1:27
  • $\begingroup$ math.stackexchange.com/questions/205486/… $\endgroup$
    – user940
    Oct 3, 2012 at 1:27
  • $\begingroup$ math.stackexchange.com/questions/205890/… $\endgroup$
    – user940
    Oct 3, 2012 at 1:28

1 Answer 1


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$

  • $\begingroup$ Your solution is absolutely correct .But I am still not able to get what was wrong with my approach? What was I missing? Could you please tell any combination that I am not considering.Also I always get stuck on problems like this.Could you please suggest a book or link which I should study to improve. $\endgroup$
    – g4ur4v
    Oct 3, 2012 at 6:19
  • $\begingroup$ I have understood what is wrong with my approach as pointed out by Christopher A. Wong.Could you just suggest me some study material. $\endgroup$
    – g4ur4v
    Oct 3, 2012 at 6:32

Not the answer you're looking for? Browse other questions tagged .