Lethal russian roulette (modifed)

$21$ players stand in the circle. Every player chooses aim for the shot - another player. No one can shoot themselves or into the air.

What the probability that there are at least $2$ players that have taken aim at each other?

-
I think the problem is about the aiming, not the shooting/hitting/missing/killing part. – Hagen von Eitzen Oct 30 '12 at 21:06
Yes, everyone kills with the same probability. – Xxx Oct 30 '12 at 21:09
It's the same - aiming, shooting, killing etc – Xxx Oct 30 '12 at 21:09
The question is still unclear to me. Does each player have a gun and all turns are taken simultaneously, or is there a single gun being passed around the circle? – Austin Mohr Oct 30 '12 at 21:32
everyone has a gun. To clearify let's think we stop the game when everyone aims simultaneously and noone shoots. – Xxx Oct 30 '12 at 21:40

The solution is

$$1+\sum_{s=1}^{\lfloor n/1 \rfloor}(-1)^s\frac{n!}{2^ss!(n-2s)!(n-1)^{2s}}$$

with $n=21$

The problem is explained in

http://msor.victoria.ac.nz/twiki/pub/Courses/MATH214_2009T1/Enumeration/214_2009_notes3.pdf

page 20, where it is called Zen stares.

Credits go to the people from www.wiskundeforum.nl (a Dutch math forum).

-
are you sure the solution is written wright? – Xxx Nov 1 '12 at 14:30
There was a small mistake. I think it is correct now. – wnvl Nov 1 '12 at 16:19

The problem amounts to counting the permutations of $n=21$ elements that have no fixed point (these are the legal configurations, since no one can aim at themselves), and counting how many of these have no $2$-cycle. Each of these numbers can be calculated by a simple recurrence.

First, consider permutations of $n$ elements with no fixed point (that is, derangements). Let $A_{n}$ be the number of derangements of order $n$. Each derangement of $n-1$ elements can be used to produce $n-1$ distinct derangements of $n$ elements, by inserting (in the cycle representation) the $n$-th element in any of $n-1$ locations. In addition, each permutation of $n-1$ elements with exactly one fixed point can be used to produce a unique derangement of $n$ elements (by pairing the new element with the existing fixed point). But the number of permutations of $n$ elements with exactly one fixed point is just $nA_{n-1}$: you must choose the fixed point, then form a derangement of the remaining elements. The result is $$\begin{eqnarray} A_{n} &=& (n-1)A_{n-1} + (n-1)A_{n-2} \\ &=& (n-1)\left(A_{n-1} + A_{n-2}\right), \end{eqnarray}$$ where $A_{0}=1$. This sequence starts with $1,0,1,2,9,44,265...$ (OEIS:A000166) and $A_{21}=18795307255050944540 \approx (21!)/e$.

The same reasoning can be used to count permutations without fixed points or $2$-cycles. Let $B_{n}$ be the number of these of order $n$. Again, we can produce $n-1$ such permutations of order $n$ from each of order $n-1$; and we can also produce $2$ such permutations of order $n$ from each permutation of order $n-1$ with exactly one $2$-cycle (and no fixed points). The number of permutations of $n$ elements with no fixed points and exactly one $2$-cycle is $\frac{1}{2}n(n-1)B_{n-2}$: you must choose the pair involved in the $2$-cycle, then permute the remaining elements with no $2$-cycles or fixed points. The result here is $$\begin{eqnarray} B_{n} &=& (n-1)B_{n-1} + (n-1)(n-2)B_{n-3} \\ &=& (n-1)\left(B_{n-1} + \left(n-2\right)B_{n-3}\right), \end{eqnarray}$$ where $B_0=1$. This sequence starts with $1,0,0,2,6,24,160,1140,...$ (OEIS:A038205), and $B_{21}=11399930109077490560\approx A_{21}/\sqrt{e} \approx (21!)/e^{3/2}$.

The probability that no two players are aiming at each other is therefore $$\frac{B_{21}}{A_{21}} \approx \frac{1}{\sqrt{e}} = 0.60653...,$$ as it is for all reasonably large $n$.

-