교란순열 계산기

교란순열은 어떤 항목도 원래 위치에 오지 않도록 다시 배열하는 것입니다. 고전적인 모자 맡기기 문제나 아무도 자기 이름을 뽑지 않는 마니또 추첨이 그 예입니다. 이 계산기는 교란순열의 수 !n, 무작위로 섞은 결과가 교란순열일 확률, 몇 개의 항목이 제자리에 남는지에 대한 전체 분포를 보여 줍니다.

사용 방법

1. 항목의 수(사람, 편지, 모자, 좌석)를 입력합니다.
2. '원래 자리에 남는 항목의 수'를 0으로 두면 교란순열이고, k를 입력하면 정확히 k개가 처음 자리에 있는 배열의 수를 셉니다.
3. 경우의 수와 확률을 확인합니다. 표에는 가능한 모든 제자리 항목 수가 나옵니다.

계산식

!n = n! × Σ (−1)ᵏ / k! for k = 0 … n !n = (n − 1) × (!(n − 1) + !(n − 2)), with !0 = 1 and !1 = 0

첫 번째 공식은 제자리에 남는 항목에 대한 포함-배제 원리에서 나옵니다. n ≥ 1이면 !n은 n!/e를 가장 가까운 정수로 반올림한 값과도 같습니다. 정확히 k개가 제자리에 있는 배열(랑콩트르 수)은 C(n, k) × !(n − k)입니다. 제자리에 남을 k개를 고른 뒤 나머지를 교란시킵니다.

예시

4명이 선물을 교환하면 나누어 주는 방법은 4! = 24가지이고, 아무도 자기 선물을 받지 않는 경우는 !4 = 3 × (!3 + !2) = 3 × (2 + 1) = 9가지이므로 확률은 9/24 = 37.5%입니다. 정확히 한 명만 자기 선물을 받는 경우는 C(4, 1) × !3 = 4 × 2 = 8가지입니다. 8명이면 40,320가지 순서 중 !8 = 14,833가지로 약 36.79%입니다.