Probabilidade de que o arranjo do Papai Noel Secreto resulte em pares perfeitos

Então, nós tivemos o Papai Noel Secreto no trabalho.

Somos 8 pessoas. Cada um de nós se revezou e puxou um pequeno pedaço de papel de uma tigela com um nome. A única regra: se você digitar seu nome, precisará colocar o pedaço de papel de volta na tigela e tentar novamente.

Vamos chamar as pessoas de A, B, C, D, E, F, G, H, que também é a ordem na qual eles pegaram seu pedaço de papel.

Fizemos a troca de presentes ontem à noite.

A era o Papai Noel secreto de F.
B era o Papai Noel secreto de E.
C era o Papai Noel secreto de D.
D era o Papai Noel secreto de C.
E era o Papai Noel secreto de B.
F era o Papai Noel secreto de A.
G era o Papai Noel secreto de H.
Ele era o Papai Noel secreto de G.

Veja o que aconteceu? Nós fizemos casais.

A e F eram o Papai Noel secreto um do outro.
B e E eram o Papai Noel secreto um do outro.
C e D eram o Papai Noel secreto um do outro.
G e H eram o Papai Noel secreto um do outro.

Qual é a probabilidade disso acontecer e como você o calcula?

O número total de tarefas entre pessoas, onde ninguém é designado para si, é d ( 2 n ) = ( 2 n ) ! ( 1 / 2 - 1 / 6 + ⋯ + ( - 1 ) k / k ! + ⋯ + 1 / ( 2 N ) ! ) . (Estes são chamados de desarranjos .) O valor está muito próximo de $2n$

Se eles correspondem a pares perfeitos, então são um produto de transposições disjuntas . Isso implica que sua estrutura de ciclo é da forma

O número de padrões distintos é a ordem do grupo de todas as permutações dos nomes divididos pela ordem do estabilizador do padrão. Um elemento estabilizador pode trocar qualquer número de pares e também pode permutar n ! pares, de onde existem 2 n n ! elementos estabilizadores. Portanto, existem$2n$$n!$$2^n n!$

esses pares.

Como todos esses pares perfeitos são desarranjos, e todos os desarranjos são igualmente prováveis, a chance é igual a

Para pessoas, por conseguinte, a resposta exacta é 15 / 2119 ≈ 0,00707881 enquanto que a aproximação é de e / ( 2 $2n=8$$15/2119 \approx 0.00707881$ : eles concordam com cinco números significativos.$e/(2^4\, 4!) \approx 0.00707886$

Para verificar, esta Rsimulação desenha um milhão de permutações aleatórias de oito objetos, retém apenas aqueles que são desarranjos e conta aqueles que são pares perfeitos. Ele gera sua estimativa, o erro padrão da estimativa e um escore Z para compará-lo ao valor teórico. Sua saída é

       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))

Fiquei bastante impressionado com a elegância na resposta @whuber. Para ser sincero, tive que me familiarizar com novos conceitos para seguir as etapas de sua solução. Depois de gastar muito tempo nisso, decidi postar o que consegui. Então, o que se segue é uma nota exegética à sua resposta já aceita. Dessa forma, não há tentativa de originalidade, e meu único objetivo é fornecer alguns pontos de ancoragem adicionais para seguir algumas das etapas envolvidas.

Então aqui vai ...

$2n$

2. Podemos derivar a fórmula para desarranjos?

$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)]$

Agora, observando o paralelismo entre o LHS dessa equação e a parte do RHS entre parênteses, podemos continuar recursivamente:

$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$

Trabalhando para trás:

$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)$

Então, em geral,

$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!}$

Para a Rsimulação:

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

x[x]$8$ vetor de elementos representando as atribuições atuais e determinar se ele é composto de loops de 2 elementos, como no problema do Papai Noel. Enquanto as permutações corresponderem a elementos de transposição, de modo que, se Paulo deveria dar um presente a Maria ( Paul -> Mariae vice-versa Maria -> Paul) e Max a John ( Max -> John/ John -> Max) inicialmente, a transposição resultante resultaria em um novo emparelhamento perfeito ( Max -> Maria/ Maria -> Maxe Paul -> John/ John -> Paul) estamos cumprindo a condição inicial de emparelhamento perfeito:

Em outras palavras, se voltarmos ao exemplo dos chapéus em i $1$

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

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

3.k.paired <- sum(i.good & i.paired) existe para excluir permutações emparelhadas como a acima no diagrama, que não são perturbações:

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.