6 cans are placed on a shelf in a circular arrangement. After tidying and cleaning the kitchen, the cans are placed again in new, random positions around a circle. What is the probability that none of the cans are in their initial positions or their adjacent?
Isn't it $(\frac{3}{6})^6$?
If you think it is $(\frac{3}{6})^6$ because you assume these are all independent events ... then you are making a wrong assumption. For example, if the first can is put in the place of where the second can was, then the probability that the second can gets put in a place other than its initial or adjacent position is $\frac{3}{5}$, rather than $\frac{3}{6}$
In general, the placement of cans effects the placement of other cans, making the outcomes of these events dependent on each other.
The combinatorial problem is (relatively) too complicated, and writing some code is (really) too simple, so here is the code and the count:
S = SymmetricGroup(6)
R = Zmod(6)
cansPermutations = \
[ s for s in S
if not {R(0), R(1), R(-1)}.intersection(
{R(s(k)-1) - R(k-1) for k in [1..6]}) ]
(This is "all the code".)
Then we ask for the variables.
sage: len(cansPermutations)
20
sage: cansPermutations
[(1,5,3)(2,6,4),
(1,4)(2,5)(3,6),
(1,3,5)(2,4,6),
(1,5,2,4)(3,6),
(1,3,6,4)(2,5),
(1,4,6,3)(2,5),
(1,5,2,4,6,3),
(1,3)(2,5)(4,6),
(1,3,5,2,6,4),
(1,4)(2,6,3,5),
(1,4,2,5)(3,6),
(1,5)(2,4)(3,6),
(1,3,6,4,2,5),
(1,3,5)(2,6,4),
(1,4,2,6,3,5),
(1,4)(2,5,3,6),
(1,5,3,6,2,4),
(1,4,6,2,5,3),
(1,5,3)(2,4,6),
(1,4)(2,6)(3,5)]
There are $20$ "good permutations".
The question does not make it clear, if we need to compute the probability, or only to show it is not $(3/6)^6$. Here, i will compute explicitly the set of the "good" permutations of the cans. (I.e. of those that move each can $k\in R=\Bbb Z/6$ to some place which is not among $k$ and $k\pm 1$.)
Note that each permutation can be uniquely written as a product of disjoint cycles. We do this with each of the good permutations. No element is fixed, so the lengths of the cycles that appear are at least $2$. We have only the following possibilities to split the total length $6$ in pieces $\ge 2$: $$ \begin{aligned} 6 &= 2+2+2\\ &=2+4\\ &=3+3\\ &=6\ . \end{aligned} $$ Now we count for each split the number of the possibilities to fill in the places.
For the type $2+2+2$ we search for permutations of the shape $(1a)(bc)(de)$. If we map $1\to 3$, i.e. $a=3$, then for $5$ we have only the possibility $2$, and there is only one case, $(13)(25)(46)$. Symmetrically, if we decide to map $1\to 5$, then there is only one possibility for the $3$, we get the only case $(15)(36)(24)$. For $1\to 4$ we have after some chase of possibilities only $(14)(25)(36)$ and $(14)(26)(35)$. We have thus $1+1+2=4$ cases in this shape. This combinatorial problem was simple.
For the case $3+3$ we have still an easy count. A good permutation of the shape $(1bc)(def)$ must have odd values for $b,c$, else the $4$ is either $b$ or $c$. But the neighbors of $1,4$ cover all possible remaining values, so there is no "good place" for $c$. So $1,b,c$ are the numbers $1,3,5$ in some order (for $3,5$), the remaining $2,e,f$ are $2,4,6$ in some order (of $4,6$). We have thus $2\times 2=4$ cases in this shape. Again a simple case.
The next case is $2+4$. Let $(ab)(cdef)$ be such a good permutation, $a<b$. We are conjugating it cyclically, i.e. permute cyclically the letters till $a$ becomes $1$. In this was it is enough to study the good permutations of the shape $(1B)(CDEF)$, then produce all conjugates of it, taking care to not repeat solutions. Since $B\ne 2$, the $2$ is among $C,D,E,F$, and we can and do assume $C=2$. Also, $5$ is among $D,E,F$. The first observation is that $B=4$. Else we may assume (by changing the orientation of the circle) $B=3$, then $2,D,E,F$ are $2,4,5,6$ in some order. So $5\to 2$, but then which number goes to $5$, we have only neighbors left, contradiction. Our permutation is thus $(14)(2DEF)$, and a quick chase validates only $(14)(2536)$ and its invers $(14)(2635)$. Now back to $(ab)(cdef)$. It is clear that $(ab)$ may be only among $(14)$, and/or $(25)$ and/or $(36)$ and in each case we obtain two solutions. So there are $3\times 2$ solutions of this shape.
It remains to get the good permutations of shape $6$, i.e. looking like $(1bcdef)$. Maybe the simplest way to proceed is to fix the possible place of the $4$. It cannot be $c$ (and symmetrically in the cycle $e$) because we have no good option for the letter in between, $b$ (and respctively $f$). We can place thus the $4$ on $b$, getting finally only the cases $(142635)$ and $(146253)$, the reversed cycles in the pattern $(1bcde4)$, and two more solutions for the pattern $(1bc4ef)$, which are $(152463)$ and its inverse $(136425)$. So we have $2+2+2$ more solutions.
Totally, there are $4+4+6+6=20$ solutions.
