"교란순열 (derangement)"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
(피타고라스님이 이 페이지의 위치를 <a href="/pages/4759871">조합수학</a>페이지로 이동하였습니다.)
1번째 줄: 1번째 줄:
 +
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">이 항목의 스프링노트 원문주소</h5>
  
 +
* [[derangement]]
 +
 +
 
 +
 +
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">간단한 소개</h5>
 +
 +
문제 : 목욕탕에 n명의 사람이 있다. 몇 사람씩 그룹을 만들어 동그랗게 서서, 서로 등을 밀어주는 경우의 수 <math>D_n</math>은 얼마인가? 혼자서 자기 등을 밀 수는 없다.
 +
 +
 
 +
 +
예를 들어 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가지 경우가 있다. (수학과 학부생쯤 되면, 이러한 기호를 통해 문제가 묻는 것이 number of permutations of n points without fixed points 라는 것을 눈치챌 수 있다)
 +
 +
 
 +
 +
똑같은 문제로 다음과 같은 상황을 들 수 있다.
 +
 +
 
 +
 +
n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않는 경우의 수 <math>D_n</math>은?
 +
 +
 
 +
 +
이렇게 표현하는 것이 아무래도 목욕탕 문제보다는 좀더 품위가 있고 쉽게 느껴질 것 같다.
 +
 +
 
 +
 +
이 수열 <math>D_n</math>에는 (arrangement의 반대 개념으로) [http://en.wikipedia.org/wiki/Derangement derangement] 라는 이름이 붙어 있다.
 +
 +
 
 +
 +
<blockquote>
 +
<math>D_0=1, D_1=0, D_2=1, D_3=2, D_4=9, D_5=44, D_6=265, \cdots</math>
 +
</blockquote>
 +
 +
 
 +
 +
<math>D_n</math>은 다음 점화식을 만족시킨다.
 +
 +
 
 +
 +
<blockquote>
 +
<math>D_n=(n-1)(D_{n-1}+D_{n-2})</math>
 +
</blockquote>
 +
 +
 
 +
 +
심심할 때 각자 생각해 보기에 참 좋은 문제인 것 같다. (요즘 쥔장이 약간 귀차니즘에 빠져있다.)
 +
 +
 
 +
 +
이 점화식을 변형하면 다음을 얻을 수 있다.
 +
 +
 
 +
 +
<blockquote>
 +
<math>D_n-nD_{n-1}=-(D_{n-1}-(n-1)D_{n-2})</math>
 +
</blockquote>
 +
 +
 
 +
 +
따라서,
 +
 +
 
 +
 +
<blockquote>
 +
<math>D_n-nD_{n-1}=(-1)^n</math>
 +
</blockquote>
 +
 +
 
 +
 +
이제 이 수열에 대하여 지수생성함수를 계산해 보자. 지수생성함수는 다음과 같이 정의된다.
 +
 +
 
 +
 +
<blockquote>
 +
<math>f(x)=\sum_{n=0}^{\infty} \frac{D_n}{n!}x^n</math>
 +
</blockquote>
 +
 +
 
 +
 +
위에서 얻은 점화식을 사용하면,
 +
 +
 
 +
 +
<blockquote>
 +
<math>\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}</math>
 +
</blockquote>
 +
 +
 
 +
 +
좌변을 계산하면,
 +
 +
 
 +
 +
<blockquote>
 +
<math>\text{LHS} =\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)</math>
 +
</blockquote>
 +
 +
 
 +
 +
따라서,
 +
 +
 
 +
 +
<blockquote>
 +
<math>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)</math>
 +
</blockquote>
 +
 +
 
 +
 +
그러므로 <math>D_n</math>의 일반항은 다음과 같이 주어진다.
 +
 +
 
 +
 +
<blockquote>
 +
<math>\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1)^n\frac{1}{n!}</math>
 +
</blockquote>
 +
 +
 
 +
 +
이 식으로부터 다음과 같은 결론을 얻을 수 있다.
 +
 +
 
 +
 +
<blockquote>
 +
(n이 충분히 클 때) n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않을 확률은 <math>\frac{1}{e}</math>에 가깝다.
 +
</blockquote>
 +
 +
 
 +
 +
<h5>재미있는 사실</h5>
 +
 +
 
 +
 +
* 네이버 지식인 http://kin.search.naver.com/search.naver?where=kin_qna&query=
 +
 +
 
 +
 +
 
 +
 +
<h5>역사</h5>
 +
 +
* [[수학사연표 (역사)|수학사연표]]
 +
 +
 
 +
 +
 
 +
 +
<h5>메모</h5>
 +
 +
 
 +
 +
 
 +
 +
<h5>관련된 항목들</h5>
 +
 +
* [[생성함수]]
 +
* [[자연상수 e]]
 +
 +
 
 +
 +
 
 +
 +
<h5 style="margin: 0px; line-height: 3.428em; color: rgb(34, 61, 103); font-family: 'malgun gothic',dotum,gulim,sans-serif; font-size: 1.166em; background-position: 0px 100%;">수학용어번역</h5>
 +
 +
* http://www.google.com/dictionary?langpair=en|ko&q=
 +
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]<br>
 +
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
 +
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
 +
 +
 
 +
 +
 
 +
 +
<h5>사전 형태의 자료</h5>
 +
 +
* http://ko.wikipedia.org/wiki/
 +
* http://en.wikipedia.org/wiki/
 +
* http://www.wolframalpha.com/input/?i=
 +
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
 +
* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]<br>
 +
** http://www.research.att.com/~njas/sequences/?q=
 +
 +
 
 +
 +
 
 +
 +
<h5>관련논문</h5>
 +
 +
* http://www.jstor.org/action/doBasicSearch?Query=
 +
* http://dx.doi.org/
 +
 +
 
 +
 +
<h5>관련도서 및 추천도서</h5>
 +
 +
*  도서내검색<br>
 +
** http://books.google.com/books?q=
 +
** http://book.daum.net/search/contentSearch.do?query=
 +
*  도서검색<br>
 +
** http://books.google.com/books?q=
 +
** http://book.daum.net/search/mainSearch.do?query=
 +
** http://book.daum.net/search/mainSearch.do?query=
 +
 +
 
 +
 +
 
 +
 +
<h5>관련기사</h5>
 +
 +
*  네이버 뉴스 검색 (키워드 수정)<br>
 +
** http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
 +
** http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
 +
** http://news.search.naver.com/search.naver?where=news&x=0&y=0&sm=tab_hty&query=
 +
 +
 
 +
 +
 
 +
 +
<h5>블로그</h5>
 +
 +
* [http://bomber0.byus.net/index.php/2008/07/26/696 derangement : 목욕탕에서 서로 등을 밀어주는 경우의 수와 자연상수]<br>
 +
** 피타고라스의 창, 2008-7-26
 +
* 구글 블로그 검색 http://blogsearch.google.com/blogsearch?q=
 +
* [http://navercast.naver.com/science/list 네이버 오늘의과학]
 +
* [http://math.dongascience.com/ 수학동아]
 +
* [http://www.ams.org/mathmoments/ Mathematical Moments from the AMS]
 +
* [http://betterexplained.com/ BetterExplained]

2009년 12월 24일 (목) 07:06 판

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

 

간단한 소개

문제 : 목욕탕에 n명의 사람이 있다. 몇 사람씩 그룹을 만들어 동그랗게 서서, 서로 등을 밀어주는 경우의 수 \(D_n\)은 얼마인가? 혼자서 자기 등을 밀 수는 없다.

 

예를 들어 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가지 경우가 있다. (수학과 학부생쯤 되면, 이러한 기호를 통해 문제가 묻는 것이 number of permutations of n points without fixed points 라는 것을 눈치챌 수 있다)

 

똑같은 문제로 다음과 같은 상황을 들 수 있다.

 

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\)은 다음 점화식을 만족시킨다.

 

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

 

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

 

\(\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}\)

 

좌변을 계산하면,

 

\(\text{LHS} =\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)\)

 

그러므로 \(D_n\)의 일반항은 다음과 같이 주어진다.

 

\(\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1)^n\frac{1}{n!}\)

 

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

 

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

 

재미있는 사실

 

 

 

역사

 

 

메모

 

 

관련된 항목들

 

 

수학용어번역

 

 

사전 형태의 자료

 

 

관련논문

 

관련도서 및 추천도서

 

 

관련기사

 

 

블로그
원본 주소 "https://wiki.mathnt.net/index.php?title=교란순열_(derangement)&oldid=1820"