Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
    
    
    
show 2 more comments

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 1 down vote accepted

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$

share|improve this answer
    
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. –  g4ur4v Oct 3 '12 at 6:19
    
I have understood what is wrong with my approach as pointed out by Christopher A. Wong.Could you just suggest me some study material. –  g4ur4v Oct 3 '12 at 6:32
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.