-1
$\begingroup$

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
    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.2012-10-02
  • 0
    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.2012-10-03
  • 0
    http://math.stackexchange.com/questions/206016/circular-permutation-of-k-types-of-items-on-n-places-with-no-two-adjacent-it2012-10-03
  • 0
    http://math.stackexchange.com/questions/205486/in-how-many-ways-we-can-put-r-distinct-objects-into-n-baskets2012-10-03
  • 0
    http://math.stackexchange.com/questions/205890/how-to-find-the-circular-permutation-with-repetition2012-10-03
  • 0
    -1 for failure to cite the source of the question.2012-10-10
  • 0
    this is a competition question...http://www.codechef.com/OCT12/problems/NEWSCH/2012-10-10

1 Answers 1

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$

  • 0
    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.2012-10-03
  • 0
    I have understood what is wrong with my approach as pointed out by Christopher A. Wong.Could you just suggest me some study material.2012-10-03