Kemungkinan bahwa pengaturan Secret Santa akan menghasilkan pasangan sempurna

Jadi, kami punya Secret Santa di kantor.

Kami 8 orang. Kami masing-masing bergiliran dan menarik selembar kertas kecil dari mangkuk dengan nama di atasnya. Satu-satunya aturan: Jika Anda menarik nama Anda, Anda harus meletakkan kembali kertas itu di mangkuk dan coba lagi.

Sebut saja orang-orang A, B, C, D, E, F, G, H, yang juga merupakan urutan di mana mereka mengambil kertas mereka.

Kami melakukan pertukaran hadiah tadi malam.

A adalah santa rahasia F.
B adalah santa rahasia E.
C adalah santa rahasia D.
D adalah santa rahasia C.
E adalah santa rahasia B.
F adalah santa rahasia A.
G adalah santa rahasia H.
H adalah santa rahasia G.

Lihat apa yang terjadi? Kami membuat pasangan.

A dan F adalah santa rahasia masing-masing.
B dan E adalah santa rahasia masing-masing.
C dan D adalah santa rahasia masing-masing.
G dan H adalah santa rahasia masing-masing.

Berapa probabilitas hal ini terjadi dan bagaimana Anda menghitungnya?

$2n$

Jika mereka sesuai dengan pasangan sempurna, maka mereka adalah produk dari transposisi terpisah . Ini menyiratkan struktur siklus mereka adalah dari bentuk

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

pasangan seperti itu.

Karena semua pasangan sempurna seperti itu adalah kekacauan, dan semua kekacauan sama-sama mungkin, kesempatannya sama

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

Untuk mengecek, Rsimulasi ini menarik sejuta permutasi acak dari delapan objek, hanya mempertahankan yang merupakan gangguan, dan menghitung yang merupakan pasangan sempurna. Ini menghasilkan estimasi, kesalahan standar estimasi, dan skor-Z untuk membandingkannya dengan nilai teoritis. Outputnya adalah

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

Saya cukup terkesan dengan keanggunan jawaban @whuber. Sejujurnya saya harus banyak berkenalan dengan konsep-konsep baru untuk mengikuti langkah-langkah dalam solusinya. Setelah menghabiskan banyak waktu untuk itu, saya memutuskan untuk memposting apa yang saya dapatkan. Jadi yang berikut adalah catatan eksegetis terhadap tanggapannya yang sudah diterima. Dengan cara ini tidak ada upaya orisinalitas, dan satu-satunya tujuan saya adalah memberikan beberapa poin penahan tambahan untuk mengikuti beberapa langkah yang terlibat.

Jadi begini ...

$2n$

2. Bisakah kita menurunkan formula untuk kekacauan?

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

Sekarang memperhatikan paralelisme antara LHS dari persamaan ini dan bagian pada RHS dalam kurung kita dapat melanjutkan secara rekursif:

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

Bekerja mundur:

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

Jadi secara umum,

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

Untuk Rsimulasi:

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.k.paired <- sum(i.good & i.paired) ada untuk mengecualikan permutasi berpasangan seperti yang di atas dalam diagram, yang bukan gangguan:

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.