-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.

  • 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
    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