교란순열 (derangement)

이 항목의 스프링노트 원문주소

• derangement

 

 

개요

• 고정점을 갖지 않는 순열의 개수(number of permutations 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}\)에 가깝다.

 

 

역사

• 수학사연표

 

 

 

 

관련된 항목들

• 생성함수
• 자연상수 e

 

 

수학용어번역

• 난순열, 완전순열 등의 용어가 활용되고 있음
• http://www.google.com/dictionary?langpair=en|ko&q=derangement
• 대한수학회 수학 학술 용어집
  
  • http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=derangement
• 대한수학회 수학용어한글화 게시판

 

 

사전 형태의 자료

• http://ko.wikipedia.org/wiki/완전순열
• http://ko.wikipedia.org/wiki/포함-배제의_원리
• http://en.wikipedia.org/wiki/derangement
• http://www.wolframalpha.com/input/?i=
• NIST Digital Library of Mathematical Functions
• The On-Line Encyclopedia of Integer Sequences
  
  • http://www.research.att.com/~njas/sequences/?q=

 

 

관련논문

• http://www.jstor.org/action/doBasicSearch?Query=
• http://dx.doi.org/

 

 

 

 

 

블로그

• derangement : 목욕탕에서 서로 등을 밀어주는 경우의 수와 자연상수
  
  • 피타고라스의 창, 2008-7-26
• 구글 블로그 검색 http://blogsearch.google.com/blogsearch?q=
• 네이버 오늘의과학
• 수학동아
• Mathematical Moments from the AMS
• BetterExplained