Rearrangement of balls in boxes $28$ balls are placed in $28$ empty boxes, all in a row. Someone removes all the balls and then places them again either in the same box or to an adjacent of the initial box. In how many different ways can he do this if there is only one ball in each box?
Is it $2*3*3*3*2$? Probably not...
 A: Let $a_n$ be the number of ways we can fill $n$ boxes.  
Observe that $a_1 = 1$ since there is only one way to fill one box with the ball that was originally in it.
Also, $a_2 = 2$ since we must either place the balls in their original boxes or switch them.  
Suppose $n > 2$.  
We can extend any permissible arrangement of length $n - 1$ to one of length $n$ by placing the $n$th ball in the $n$th box.  Conversely, given a permissible arrangement of length $n$ in which the $n$th box contains the $n$th ball, we can reduce it to a permissible arrangement of length $n - 1$ by removing the $n$th box.  Hence, the number of permissible arrangements in which the $n$th box is filled with the $n$th ball is $a_{n - 1}$.
If the $n$th ball is not placed in the $n$th box, it must be placed in the $(n - 1)$st position, with the $(n - 1)$st ball placed in the $n$th box.  Thus, any permissible arrangement in which the $n$th ball is not placed in the $n$th box can be reduced to a permissible arrangement of length $n - 2$ by removing the last two boxes.  Conversely, any permissible arrangement of length $n - 2$ can be extended to a permissible arrangement of length $n$ by adding the last two boxes with the $n$th ball placed in the $(n - 1)$st box and the $(n - 1)$st ball placed in the $n$th box.  Hence, the number of permissible arrangements in which the $n$th ball is not in the $n$th box is $a_{n - 2}$.
Therefore, we have the recurrence relation
\begin{align*}
a_1 & = 1\\
a_2 & = 2\\
a_n & = a_{n - 1} + a_{n - 2}
\end{align*}
Notice that $a_n = F_{n + 1}$, where $F_n$ is the $n$th Fibonacci number, so the number you seek is $F_{29}$.
A: If you're allowed to have two or more balls in the same box then it is $2\times3\times3\times...\times3\times2=4\times 3^{26}$, as you say: the number of choices for each ball in turn is $2,3,3,...,3,2$ and all choices are independent.
If you're only allowed to have one ball in each box then the choices are not independent. Say there are $u_n$ ways to do this with $n$ boxes. You have to end up with exactly one ball in each box (because there's exactly the same number of balls as boxes). Some ball must go in the leftmost box: either the ball which was originally there stays there, or the first two balls swap. For each of these options, how many ways are there to arrange the remaining balls?
