"교란순열 (derangement)"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
이 항목의 스프링노트 원문주소==
Pythagoras0 (토론 | 기여) 잔글 (찾아 바꾸기 – “<h5>” 문자열을 “==” 문자열로) |
Pythagoras0 (토론 | 기여) 잔글 (찾아 바꾸기 – “</h5>” 문자열을 “==” 문자열로) |
||
| 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 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%;">이 항목의 스프링노트 원문주소== |
* [[derangement]] | * [[derangement]] | ||
| 7번째 줄: | 7번째 줄: | ||
| − | <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 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%;">개요== |
* 고정점을 갖지 않는 순열의 개수(number of permutations of n points without fixed points) | * 고정점을 갖지 않는 순열의 개수(number of permutations of n points without fixed points) | ||
| 19번째 줄: | 19번째 줄: | ||
| − | ==<math>D_4</math>의 경우 | + | ==<math>D_4</math>의 경우== |
예를 들어 1,2,3,4 네 사람이 있는 경우를 생각해 보자. 말을 줄이기 위해, 기호를 하나 정의한다. (abc…d) 라는 것은 a는 b의 등을 밀고, b는 c의 등을 밀고, … , d는 a의 등을 미는 것을 뜻한다. 1,2,3,4 네 명이서 서로 등을 밀어 주는 경우의 수는 다음과 같이 셀 수 있다. | 예를 들어 1,2,3,4 네 사람이 있는 경우를 생각해 보자. 말을 줄이기 위해, 기호를 하나 정의한다. (abc…d) 라는 것은 a는 b의 등을 밀고, b는 c의 등을 밀고, … , d는 a의 등을 미는 것을 뜻한다. 1,2,3,4 네 명이서 서로 등을 밀어 주는 경우의 수는 다음과 같이 셀 수 있다. | ||
| 31번째 줄: | 31번째 줄: | ||
| − | ==점화식 | + | ==점화식== |
* <math>D_n=(n-1)(D_{n-1}+D_{n-2})</math> | * <math>D_n=(n-1)(D_{n-1}+D_{n-2})</math> | ||
| 41번째 줄: | 41번째 줄: | ||
| − | ==생성함수 | + | ==생성함수== |
* 지수생성함수는 다음과 같다<br><math>f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n=\frac{e^{-x}}{1-x}</math><br> | * 지수생성함수는 다음과 같다<br><math>f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n=\frac{e^{-x}}{1-x}</math><br> | ||
| 63번째 줄: | 63번째 줄: | ||
| − | ==수열의 일반항 | + | ==수열의 일반항== |
* 위에서 얻은 생성함수로부터 수열의 일반항을 구할 수 있다<br><math>\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}</math><br><math>D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}</math><br> | * 위에서 얻은 생성함수로부터 수열의 일반항을 구할 수 있다<br><math>\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}</math><br><math>D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}</math><br> | ||
| 73번째 줄: | 73번째 줄: | ||
| − | ==포함과 배제의 원리의 응용 | + | ==포함과 배제의 원리의 응용== |
* 집합 <math>\{1,2,\cdots,n\}</math>의 permutation 들의 집합을 A, i->i 인 permutation 들의 집합을 <math>A_i</math> 이라 하자 | * 집합 <math>\{1,2,\cdots,n\}</math>의 permutation 들의 집합을 A, i->i 인 permutation 들의 집합을 <math>A_i</math> 이라 하자 | ||
| 81번째 줄: | 81번째 줄: | ||
| − | ==자연상수와의 관계 | + | ==자연상수와의 관계== |
| 99번째 줄: | 99번째 줄: | ||
| − | ==역사 | + | ==역사== |
* [[수학사연표 (역사)|수학사연표]] | * [[수학사연표 (역사)|수학사연표]] | ||
| 107번째 줄: | 107번째 줄: | ||
| − | ==메모 | + | ==메모== |
| 113번째 줄: | 113번째 줄: | ||
| − | ==관련된 항목들 | + | ==관련된 항목들== |
* [[생성함수]] | * [[생성함수]] | ||
| 122번째 줄: | 122번째 줄: | ||
| − | <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 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%;">수학용어번역== |
* 난순열, 완전순열 등의 용어가 활용되고 있음 | * 난순열, 완전순열 등의 용어가 활용되고 있음 | ||
| 134번째 줄: | 134번째 줄: | ||
| − | ==사전 형태의 자료 | + | ==사전 형태의 자료== |
* [http://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4 http://ko.wikipedia.org/wiki/완전순열] | * [http://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4 http://ko.wikipedia.org/wiki/완전순열] | ||
| 148번째 줄: | 148번째 줄: | ||
| − | ==관련논문 | + | ==관련논문== |
* http://www.jstor.org/action/doBasicSearch?Query= | * http://www.jstor.org/action/doBasicSearch?Query= | ||
| 155번째 줄: | 155번째 줄: | ||
| − | ==관련도서 및 추천도서 | + | ==관련도서 및 추천도서== |
* 도서내검색<br> | * 도서내검색<br> | ||
| 169번째 줄: | 169번째 줄: | ||
| − | ==관련기사 | + | ==관련기사== |
* 네이버 뉴스 검색 (키워드 수정)<br> | * 네이버 뉴스 검색 (키워드 수정)<br> | ||
| 180번째 줄: | 180번째 줄: | ||
| − | ==블로그 | + | ==블로그== |
* [http://bomber0.byus.net/index.php/2008/07/26/696 derangement : 목욕탕에서 서로 등을 밀어주는 경우의 수와 자연상수]<br> | * [http://bomber0.byus.net/index.php/2008/07/26/696 derangement : 목욕탕에서 서로 등을 밀어주는 경우의 수와 자연상수]<br> | ||
2012년 11월 1일 (목) 08:37 판
이 항목의 스프링노트 원문주소==
개요==
- 고정점을 갖지 않는 순열의 개수(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}\)에 가깝다.
역사
메모
관련된 항목들
수학용어번역==
- 난순열, 완전순열 등의 용어가 활용되고 있음
- http://www.google.com/dictionary?langpair=en|ko&q=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
관련논문
관련도서 및 추천도서
- 도서내검색
- 도서검색
관련기사
- 네이버 뉴스 검색 (키워드 수정)
블로그
- 고정점을 갖지 않는 순열의 개수(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!}\)
\(f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n=\frac{e^{-x}}{1-x}\)
\(\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!}\)
(n이 충분히 클 때) n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않을 확률은 \(\frac{1}{e}\)에 가깝다.
- 난순열, 완전순열 등의 용어가 활용되고 있음
- http://www.google.com/dictionary?langpair=en|ko&q=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
관련논문
관련도서 및 추천도서
- 도서내검색
- 도서검색
관련기사
- 네이버 뉴스 검색 (키워드 수정)