교란순열 (derangement)

수학노트
둘러보기로 가기 검색하러 가기
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

개요

  • 고정점을 갖지 않는 순열을 교란순열이라 함 (permutation of n points without fixed points)
  • n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않는 경우의 수 \(D_n\)
  • 목욕탕에 n명의 사람이 있다. 몇 사람씩 그룹을 만들어 동그랗게 서서, 서로 등을 밀어주는 경우의 수 \(D_n\)은 얼마인가? 혼자서 자기 등을 밀 수는 없다.
  • 이 수열 \(D_n\)에는 (arrangement의 반대 개념으로) derangement 라는 이름이 붙어 있음\[D_0=1,D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265,\cdots\]
  • 일반항\[D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}\]



\(D_4\)의 경우

예를 들어 1,2,3,4 네 사람이 있는 경우를 생각해 보자. 말을 줄이기 위해, 기호를 하나 정의한다. (abc…d) 라는 것은 a는 b의 등을 밀고, b는 c의 등을 밀고, … , d는 a의 등을 미는 것을 뜻한다. 1,2,3,4 네 명이서 서로 등을 밀어 주는 경우의 수는 다음과 같이 셀 수 있다.

(1234), (1243), (1324), (1342), (1423), (1432), (12)(34), (13)(24), (14)(23)

따라서 모두 9가지 경우가 있다. 즉 \(D_4=9\)



점화식

  • \(D_n=(n-1)(D_{n-1}+D_{n-2})\)
  • \(D_n-nD_{n-1}=-(D_{n-1}-(n-1)D_{n-2})\)
  • \(D_n-nD_{n-1}=(-1)^n\)



생성함수

  • 지수생성함수는 다음과 같다\[f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n=\frac{e^{-x}}{1-x}\]

(증명)

위에서 얻은 점화식을 사용하면,

\(\sum_{n=0}^{\infty}\frac{D_n-nD_{n-1}}{n!}x^n=\sum_{n=0}^{\infty}\frac{(-1)^n}{n!}x^n=e^{-x}\)

좌변을 정리하면,

\(\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n-\sum_{n=0}^{\infty}\frac{nD_{n-1}}{n!}x^n=f(x)-\sum_{n=1}^{\infty}\frac{D_{n-1}}{(n-1)!}x^n=f(x)-xf(x)\)

따라서,

\(f(x)=\frac{e^{-x}}{1-x}=(1+x+x^2+x^3+\cdots)(1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots)\) ■



수열의 일반항

  • 위에서 얻은 생성함수로부터 수열의 일반항을 구할 수 있다\[\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\]\[D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}\]




포함과 배제의 원리의 응용

  • 집합 \(\{1,2,\cdots,n\}\)의 permutation 들의 집합을 A, i->i 인 permutation 들의 집합을 \(A_i\) 이라 하자



자연상수와의 관계

이 식으로부터 다음과 같은 결론을 얻을 수 있다.


(n이 충분히 클 때) n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않을 확률은 \(\frac{1}{e}\)에 가깝다.



역사



메모

관련된 항목들



수학용어번역



사전 형태의 자료


블로그


관련논문

  • Miska, Piotr. “Arithmetic Properties of the Sequence of Derangements and Its Generalizations.” arXiv:1508.01987 [math], August 9, 2015. http://arxiv.org/abs/1508.01987.

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LEMMA': 'derangement'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=교란순열_(derangement)&oldid=52124"