"교란순열 (derangement)"의 두 판 사이의 차이
| 35번째 줄: | 35번째 줄: | ||
| − | 이 | + | 이 수열 <math>D_n</math>에는 (arrangement의 반대 개념으로) [http://en.wikipedia.org/wiki/Derangement derangement] 라는 이름이 붙어 있다. |
| − | + | <math>D_0=1,D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265,\cdots</math> | |
| − | <math>D_0=1, D_1=0, D_2=1, D_3=2, D_4=9, D_5=44, D_6=265, \cdots</math | ||
| − | |||
| + | |||
| + | <h5>점화식</h5> | ||
<math>D_n</math>은 다음 점화식을 만족시킨다. | <math>D_n</math>은 다음 점화식을 만족시킨다. | ||
| − | |||
| − | |||
| − | |||
<math>D_n=(n-1)(D_{n-1}+D_{n-2})</math> | <math>D_n=(n-1)(D_{n-1}+D_{n-2})</math> | ||
| − | |||
| 60번째 줄: | 56번째 줄: | ||
이 점화식을 변형하면 다음을 얻을 수 있다. | 이 점화식을 변형하면 다음을 얻을 수 있다. | ||
| + | |||
| + | <math>D_n-nD_{n-1}=-(D_{n-1}-(n-1)D_{n-2})</math> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| 71번째 줄: | 65번째 줄: | ||
따라서, | 따라서, | ||
| − | |||
| − | |||
| − | |||
<math>D_n-nD_{n-1}=(-1)^n</math> | <math>D_n-nD_{n-1}=(-1)^n</math> | ||
| − | |||
| + | |||
| + | <h5>생성함수</h5> | ||
이제 이 수열에 대하여 지수생성함수를 계산해 보자. 지수생성함수는 다음과 같이 정의된다. | 이제 이 수열에 대하여 지수생성함수를 계산해 보자. 지수생성함수는 다음과 같이 정의된다. | ||
| 83번째 줄: | 75번째 줄: | ||
| − | + | <math>f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n</math> | |
| − | <math>f(x)=\sum_{n=0}^{\infty} \frac{D_n}{n!}x^n</math | ||
| − | |||
| 91번째 줄: | 81번째 줄: | ||
위에서 얻은 점화식을 사용하면, | 위에서 얻은 점화식을 사용하면, | ||
| − | + | <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> | |
| − | |||
| − | |||
| − | <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 | ||
| − | |||
| 103번째 줄: | 89번째 줄: | ||
| − | + | <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> | |
| − | <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 | ||
| − | |||
| 113번째 줄: | 97번째 줄: | ||
| − | |||
<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> | <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> | ||
| − | |||
| 123번째 줄: | 105번째 줄: | ||
| − | + | <math>\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots%20+(-1)^n\frac{1}{n!}</math> | |
| − | <math>\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1)^n\frac{1}{n!}</math | ||
| − | |||
2009년 12월 24일 (목) 07:11 판
이 항목의 스프링노트 원문주소
간단한 소개
문제 : 목욕탕에 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%20+(-1)^n\frac{1}{n!}\)
이 식으로부터 다음과 같은 결론을 얻을 수 있다.
(n이 충분히 클 때) n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않을 확률은 \(\frac{1}{e}\)에 가깝다.
재미있는 사실
역사
메모
관련된 항목들
수학용어번역
사전 형태의 자료
- http://ko.wikipedia.org/wiki/
- http://en.wikipedia.org/wiki/
- http://www.wolframalpha.com/input/?i=
- NIST Digital Library of Mathematical Functions
- The On-Line Encyclopedia of Integer Sequences
관련논문
관련도서 및 추천도서
- 도서내검색
- 도서검색
관련기사
- 네이버 뉴스 검색 (키워드 수정)