Prawdopodobieństwo, że ustawienie Sekretnego Świętego Mikołaja doprowadzi do idealnych par

Więc mieliśmy Tajnego Świętego Mikołaja w pracy.

Jesteśmy 8 osobami. Każdy z nas na zmianę wyciągał z miski kawałek papieru z nazwą. Jedyna zasada: jeśli wyciągniesz swoje imię, musisz włożyć kawałek papieru z powrotem do miski i spróbować ponownie.

Nazwijmy ludzi A, B, C, D, E, F, G, H, w takiej kolejności, w jakiej wybrali kawałek papieru.

Ostatniej nocy dokonaliśmy wymiany prezentów.

A był sekretnym Mikołajem F.
B był sekretnym Mikołajem E.
C był sekretnym Mikołajem D.
D był tajemniczym Mikołajem C.
E był sekretnym Mikołajem B.
F był sekretnym Mikołajem A.
G był tajemniczym Mikołajem Świętego Mikołaja.
H był sekretnym Mikołajem G.

Widzisz co się stało? Zrobiliśmy pary.

A i F były dla siebie sekretnym Mikołajem.
B i E byli dla siebie sekretnym Mikołajem.
C i D byli dla siebie sekretnym Mikołajem.
G i H byli dla siebie sekretnym Mikołajem.

Jakie jest prawdopodobieństwo takiego zdarzenia i jak go obliczyć?

Łączna liczba zadań wśród osób, do których nikt nie jest przypisany, wynosi d ( 2 n ) = ( 2 n ) ! ( 1 / 2 - 1 / 6 + ⋯ + ( - 1 ) k / k ! + ⋯ + 1 / ( 2 N ) ! ) . (Są to tak zwane odstępstwa ). Wartość jest bardzo zbliżona do $2n$

Jeśli odpowiadają idealnym parom, to są wynikiem rozłącznych transpozycji . Oznacza to, że ich struktura cyklu ma formę

$2n$$n!$$2^n n!$

takie pary.

Ponieważ wszystkie takie idealne parowania są odstępstwami, a wszystkie odstępstwa są jednakowo prawdopodobne, szansa jest równa

$2n=8$$15/2119 \approx 0.00707881$$e/(2^4\, 4!) \approx 0.00707886$

Aby to sprawdzić, ta Rsymulacja rysuje milion losowych permutacji ośmiu obiektów, zachowuje tylko te, które są wykroczeniami, i zlicza te, które są idealnymi parami. Wyprowadza swoje oszacowanie, błąd standardowy oszacowania i wynik Z, aby porównać go z wartością teoretyczną. Jego wydajność to

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

$0.0066$$0.0073$

paired <- function(x) crossprod(x[x] - 1:length(x))==0
good <- function(x) sum(x==1:length(x)) == 0

n <- 8
set.seed(17)
x <- replicate(1e6, sample(1:n, n))
i.good <- apply(x, 2, good)
i.paired <- apply(x, 2, paired)

n.deranged <- sum(i.good)
k.paired <- sum(i.good & i.paired)
p.hat <- k.paired / n.deranged
se <- sqrt(p.hat * (1-p.hat) / n.deranged)
(c(p.hat=p.hat, se=se, Z=(p.hat - 15/2119)/se))

Byłem pod wrażeniem elegancji w odpowiedzi na @whuber. Szczerze mówiąc musiałem dużo zapoznać się z nowymi koncepcjami, aby podążać za krokami w jego rozwiązaniu. Po spędzeniu dużo czasu postanowiłem opublikować to, co dostałem. Poniżej znajduje się egzegetyczna notatka do jego już zaakceptowanej odpowiedzi. W ten sposób nie ma próby oryginalności, a moim jedynym celem jest zapewnienie dodatkowych punktów zakotwiczenia, które pozwolą wykonać niektóre z tych czynności.

No i proszę…

$2n$

2. Czy możemy wyprowadzić wzór na odstępstwa?

$n$

$d(n)=(n-1)[d(n-2) + d(n-1)]=$

$=n\,d(n-2)-d(n-2)+n\,d(n-1)-d(n-1)$

$d(n) - n\,d(n-1) = -[d(n-1)-(n-1)\,d(n-2)]$

Zauważając teraz paralelność między LHS tego równania i częścią RHS w nawiasach, możemy kontynuować rekurencyjnie:

$d(n) - n\,d(n-1)=-[d(n-1)-(n-1)\,d(n-2)] =$

$=(-1)^2\,[d(n-2)-(n-2)\,d(n-3)]=\cdots=(-1)^{n-2}\,d(2)-2\,d(1)$

$d(n) = n\,d(n-1)+(-1)^n$

Praca wstecz:

$d(2)=1$

$d(3)= 3\,d(2)-1 =3*1\,-1$

$d(4)= 4\,d(3)+1 =4*3*1\,-4\,\,+1$

$d(5)= 5\,d(4)-1 =5*4*3*1\,-5*4\,+5\,\,-1$

$d(6)= 6\,d(5)+1 = 6*5*4*3*1\,-6*5*4\,+6*5\,-6\,+1=$

$=6!\left(\frac{1}{2}- \frac{1}{3*2}+\frac{1}{4*3*2}-\frac{1}{5*4*3*2}+\frac{1}{6!}\right)=$

$=6!\left(\frac{1}{6!}-\frac{1}{5!}+\frac{1}{4!}-\frac{1}{3!}+\frac{1}{2!}-\frac{1}{1!}+1\right)$

Więc ogólnie

$d(n)=n!\left(1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\cdots+\frac{1}{n!}\right)$

$e^x$$x=-1$

$d(n)\approx\frac{n!}{e}$

${a,b,c,d,e,f}$${b,d,a,c,f,e}$a -> b -> d -> c after which it returns to ae -> f$(\text {a b d c})(\text{e f})$

$4$

$(2n)!$$2n$$2^n$$n!$$p(2n) = \frac{(2n)!}{2^n n!}$

Do Rsymulacji:

1. paired <- function(x) crossprod(x[x] - 1:length(x))==0

x[x]$8$Paul -> MariaMaria -> PaulMax -> JohnJohn -> MaxMax -> MariaMaria -> MaxPaul -> JohnJohn -> Paul

i $1$

2) good <- function(x) sum(x==1:length(x)) == 0

$x$$(1,2,3,4,5,6,7,8)$

3. Czyk.paired <- sum(i.good & i.paired) istnieje wykluczenie sparowanych permutacji, takich jak powyższe na schemacie, które nie są odstępstwami:

v <- c(1,2,3,4,5,6,7,8)
w <- c(1,2,3,5,4,6,7,8)

(c("is v paired?" = paired(v), "is w paired?" = paired(w),
   "is v a derang?" = good(w), "is w a derang?" = good(w)))

# not all paired permutations are derangements.