완전순열 (부분계승) 계산기

완전순열 부분계승 계산기에 오신 것을 환영합니다. 이 도구는 n개 요소의 집합에 대한 완전순열의 수를 계산하는 종합적인 조합론 도구입니다. 완전순열(교란순열)은 어떤 원소도 원래 위치에 나타나지 않는 순열을 말하며, !n 또는 D(n)으로 표기합니다. 조합론 공부, 고전적인 모자 확인 문제 풀이, 확률론 탐구 등 어떤 목적으로든 이 계산기는 대화형 시각화와 함께 상세한 단계별 솔루션을 제공합니다.

완전순열이란 무엇인가요?

완전순열(또는 부분계승)은 집합의 원소들을 재배열할 때 어떤 원소도 원래 자리에 있지 않은 경우를 말합니다. n개 요소의 완전순열 수는 !n(n 앞에 느낌표를 붙임) 또는 D(n)으로 씁니다.

예를 들어, {1, 2, 3} 위치에 있는 세 가지 항목을 생각해 봅시다. 총 3! = 6개의 순열이 있지만, 그중 완전순열은 단 2개뿐입니다:

• (2, 3, 1) — 1번 항목은 2번 위치로, 2번 항목은 3번 위치로, 3번 항목은 1번 위치로 이동
• (3, 1, 2) — 1번 항목은 3번 위치로, 2번 항목은 1번 위치로, 3번 항목은 2번 위치로 이동

따라서 !3 = 2입니다.

완전순열 공식

포함-배제 공식

가장 근본적인 공식은 포함-배제의 원리에서 유도됩니다:

재귀 공식

완전순열은 재귀적으로 계산할 수도 있습니다:

기본값: !0 = 1, !1 = 0.

가장 가까운 정수 공식

\(n \geq 1\)일 때, 부분계승은 \(n!/e\)에 가장 가까운 정수와 같습니다:

모자 확인 문제 (The Hat-Check Problem)

완전순열의 가장 유명한 응용 사례는 모자 확인 문제(problème des rencontres)입니다. n명의 손님이 모자를 맡기고 무작위로 돌려받았을 때, 자신의 모자를 받는 손님이 한 명도 없을 확률은 얼마일까요?

정답은 \(!n / n!\)이며, 이는 \(1/e \approx 0.3679\)로 매우 빠르게 수렴합니다. 즉, 항목의 수에 관계없이 모든 무작위 순열의 약 36.8%가 완전순열임을 의미합니다.

이 계산기 사용 방법

1. n 입력: 요소의 수(0~170)를 입력합니다. 퀵 예제 버튼을 사용하여 일반적인 값을 사용해 볼 수 있습니다.
2. 계산: "!n 계산하기"를 클릭하여 완전순열 수를 계산합니다.
3. 결과 확인: !n, n!, 완전순열 확률, 그리고 1/e에 대한 비율을 확인합니다.
4. 애니메이션 탐색: 작은 n의 경우, 시각적 애니메이션을 통해 완전순열이 어떻게 작동하는지 확인합니다.
5. 단계 학습: 상세한 포함-배제 내역 및 완전순열 테이블을 검토합니다.

처음 15개의 완전순열 수

완전순열의 응용

시크릿 산타 / 선물 교환

시크릿 산타 선물 교환을 조직할 때, 각 참가자는 이름을 뽑습니다. 아무도 자기 자신의 이름을 뽑지 않는 성공적인 추첨이 바로 완전순열입니다. 10명 규모의 그룹에서는 총 3,628,800개의 경우 중 1,334,961개의 유효한 배열이 있습니다.

암호학 및 부호 이론

완전순열은 치환 암호 및 오류 정정 부호 분석에 등장합니다. "고정점이 없음"이라는 개념은 암호의 강도와 순열 기반 암호화를 이해하는 데 근본적입니다.

카드 셔플 및 게임

카드 게임에서 완전순열은 셔플 후 어떤 카드도 원래 위치로 돌아오지 않을 확률을 측정합니다. 이는 셔플 품질과 게임의 공정성을 분석하는 데 유용합니다.

확률론

완전순열은 포함-배제의 원리를 보여주는 우아한 예시이며, 확률이 어떻게 단순한 한계값(이 경우 1/e)으로 수렴할 수 있는지 잘 보여줍니다.

주요 특징

• 비율 \(!n/n!\)은 \(n \to \infty\)일 때 \(1/e \approx 0.367879\)로 수렴합니다.
• 수렴 속도가 매우 빠릅니다. n = 10일 때 이미 소수점 6자리까지 정확합니다.
• \(!n\)은 점화식 \(!n = n \cdot !(n-1) + (-1)^n\)을 만족합니다.
• 지수 생성 함수는 \(e^{-x}/(1-x)\)입니다.
• \(!0 = 1\) (공집합의 순열은 공허하게 완전순열로 간주됩니다).

자주 묻는 질문

완전순열이란 무엇인가요?

완전순열은 집합의 어떤 원소도 원래 위치에 나타나지 않는 순열입니다. 예를 들어, 항목이 {1, 2, 3}으로 표시된 경우, 순열 (2, 3, 1)은 어떤 항목도 제자리에 있지 않으므로 완전순열입니다. n개 항목의 완전순열 수는 !n(부분계승 n)으로 표기합니다.

부분계승 !n의 공식은 무엇인가요?

부분계승 !n은 포함-배제 공식을 사용하여 계산할 수 있습니다: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). 또한 !n = (n-1)(!(n-1) + !(n-2)) (단, !0 = 1, !1 = 0)과 같이 재귀적으로 계산할 수 있습니다. 또 다른 공식은 \(n \geq 1\)일 때 \(!n = \text{round}(n! / e)\)입니다.

무작위 순열이 완전순열일 확률은 얼마인가요?

무작위 순열이 완전순열일 확률은 n이 커짐에 따라 \(1/e \approx 0.3679\)에 수렴합니다. n = 5인 경우 실제 확률은 44/120 ≈ 0.3667로 이미 1/e에 매우 근접합니다.

모자 확인 문제란 무엇인가요?

모자 확인 문제는 n명의 사람이 모자를 맡기고 무작위로 돌려받았을 때, 아무도 자신의 모자를 받지 못할 확률을 묻는 고전적인 문제입니다. 정답은 !n/n!이며, 약 \(36.79\%\)입니다.

완전순열과 계승의 관계는 무엇인가요?

완전순열(!n)과 계승(n!)은 \(!n = n! \times \sum(-1)^k/k!\) 공식을 통해 연결됩니다. !n/n! 비율은 1/e로 수렴하며, !n은 \(n!/e\)에 가장 가까운 정수입니다.

추가 리소스

• 포함-배제의 원리 - Wikipedia