Permutation and combinations prob there are $k$ different things and the task is to arrange them at $n$ places such that no adjacent things are of the same type and first and last things are of the same type.
An example for: $k=3,n=4$
1 , 2 ,3 ,1
2 ,3 ,1 ,2
3 ,1 ,2 ,3
so on
as one can notice, the first and last are of the same type and there can be multiple occurrences of a number, with adjacent numbers being different. 
What is the total number such possible arrangements ?
Any help is appreciated.
 A: Hint: Let's recast the problem as making an $n-1$ place word from an alphabet of $k$ characters such that no adjacent characters are the same and 
the last one is not the same as the first (why is this equivalent?).
Then define $A(p-1)$ as the number of these strings of length $p$ and $B(p-1)$ as the number of strings of length $p-1$ with no neighboring characters matching, but the first and last are the same.  Can you write two coupled recurrences?
You want $A(n-1)$
Added:  Start with the number of length 2 strings.  For $A(2)$ we can start with $k$ for the first letter.  Then we have $k-1$ choices for the second.  This gives $A(2)=k(k-1)$ corresponding to strings of the pattern aba.  $B(2)=0$ because the two characters would have to match.  How many ways are there to extend an $A$ string by 1 character?  To extend a B string by one character to make an A string?  You should wind up with two equations $A(n)=()A(n-1)+()B(n-1)$ and $B(n)=()A(n-1)$ where there is no second term in $B(n)$ because you can't extend a $B$ string into a $B$ string (why?)
