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

수학노트
둘러보기로 가기 검색하러 가기
잔글 (찾아 바꾸기 – “<h5 (.*)">” 문자열을 “==” 문자열로)
 
(같은 사용자의 중간 판 18개는 보이지 않습니다)
1번째 줄: 1번째 줄:
−
==이 항목의 스프링노트 원문주소==
 
−
 
−
* [[derangement]]
 
−
 
−
 
 
−
 
−
 
 
−
 
 
==개요==
 
==개요==
  
−
* 고정점을 갖지 않는 순열의 개수(number of permutations of n points without fixed points)
+
* 고정점을 갖지 않는 순열을 교란순열이라 함 (permutation of n points without fixed points)
−
* n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않는 경우의 수 <math>D_n</math><br>
+
* n명의 사람이 있고, 그들의 이름이 써진 명찰 n개가 있다. 명찰을 랜덤하게 나눠줬을 때, 단 한 사람도 자기 명찰을 받지 않는 경우의 수 <math>D_n</math>
−
*  목욕탕에 n명의 사람이 있다. 몇 사람씩 그룹을 만들어 동그랗게 서서, 서로 등을 밀어주는 경우의 수 <math>D_n</math>은 얼마인가? 혼자서 자기 등을 밀 수는 없다.<br>
+
*  목욕탕에 n명의 사람이 있다. 몇 사람씩 그룹을 만들어 동그랗게 서서, 서로 등을 밀어주는 경우의 수 <math>D_n</math>은 얼마인가? 혼자서 자기 등을 밀 수는 없다.
−
*  이 수열 <math>D_n</math>에는 (arrangement의 반대 개념으로) [http://en.wikipedia.org/wiki/Derangement derangement] 라는 이름이 붙어 있음<br><math>D_0=1,D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265,\cdots</math><br>
+
*  이 수열 <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>
−
*  일반항<br><math>D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}</math><br>
+
*  일반항:<math>D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}</math>
  
−
 
+
  
−
 
+
  
 
==<math>D_4</math>의 경우==
 
==<math>D_4</math>의 경우==
23번째 줄: 15번째 줄:
 
예를 들어 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 네 명이서 서로 등을 밀어 주는 경우의 수는 다음과 같이 셀 수 있다.
  
−
(1234), (1243), (1324), (1342), (1423), (1432), (12)(34), (13)(24), (14)(23)
+
(1234), (1243), (1324), (1342), (1423), (1432), (12)(34), (13)(24), (14)(23)
  
−
따라서 모두 9가지 경우가 있다. 즉 <math>D_4=9</math>
+
따라서 모두 9가지 경우가 있다. 즉 <math>D_4=9</math>
  
−
 
+
  
−
 
+
  
 
==점화식==
 
==점화식==
35번째 줄: 27번째 줄:
 
* <math>D_n=(n-1)(D_{n-1}+D_{n-2})</math>
 
* <math>D_n=(n-1)(D_{n-1}+D_{n-2})</math>
 
* <math>D_n-nD_{n-1}=-(D_{n-1}-(n-1)D_{n-2})</math>
 
* <math>D_n-nD_{n-1}=-(D_{n-1}-(n-1)D_{n-2})</math>
−
* <math>D_n-nD_{n-1}=(-1)^n</math><br>
+
* <math>D_n-nD_{n-1}=(-1)^n</math>
  
−
 
+
  
−
 
+
  
 
==생성함수==
 
==생성함수==
  
−
*  지수생성함수는 다음과 같다<br><math>f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n=\frac{e^{-x}}{1-x}</math><br>
+
*  지수생성함수는 다음과 같다:<math>f(x)=\sum_{n=0}^{\infty}\frac{D_n}{n!}x^n=\frac{e^{-x}}{1-x}</math>
  
 
(증명)
 
(증명)
57번째 줄: 49번째 줄:
 
따라서,
 
따라서,
  
−
<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> ■
  
−
 
+
  
−
 
+
  
 
==수열의 일반항==
 
==수열의 일반항==
  
−
*  위에서 얻은 생성함수로부터 수열의 일반항을 구할 수 있다<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>
+
*  위에서 얻은 생성함수로부터 수열의 일반항을 구할 수 있다:<math>\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}</math>:<math>D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}</math>
  
−
 
+
  
−
 
+
  
−
 
+
  
 
==포함과 배제의 원리의 응용==
 
==포함과 배제의 원리의 응용==
  
−
* 집합 <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> 이라 하자
  
−
 
+
  
−
 
+
  
 
==자연상수와의 관계==
 
==자연상수와의 관계==
  
−
 
+
  
−
 
+
  
 
이 식으로부터 다음과 같은 결론을 얻을 수 있다.
 
이 식으로부터 다음과 같은 결론을 얻을 수 있다.
  
−
 
+
  
 
<blockquote>
 
<blockquote>
95번째 줄: 87번째 줄:
 
</blockquote>
 
</blockquote>
  
−
 
+
  
−
 
+
  
 
==역사==
 
==역사==
  
−
* [[수학사연표 (역사)|수학사연표]]
+
* [[수학사 연표]]
  
−
 
+
  
−
 
+
  
 
==메모==
 
==메모==
  
−
 
+
  
−
 
+
  
 
==관련된 항목들==
 
==관련된 항목들==
118번째 줄: 110번째 줄:
 
* [[자연상수 e]]
 
* [[자연상수 e]]
  
−
 
+
  
−
 
+
  
 
==수학용어번역==
 
==수학용어번역==
126번째 줄: 118번째 줄:
 
* 난순열, 완전순열 등의 용어가 활용되고 있음
 
* 난순열, 완전순열 등의 용어가 활용되고 있음
 
* [http://www.google.com/dictionary?langpair=en%7Cko&q=derangement http://www.google.com/dictionary?langpair=en|ko&q=derangement]
 
* [http://www.google.com/dictionary?langpair=en%7Cko&q=derangement http://www.google.com/dictionary?langpair=en|ko&q=derangement]
−
* [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=&fstr= 대한수학회 수학 학술 용어집]
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=derangement
 
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=derangement
−
* [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 대한수학회 수학용어한글화 게시판]
+
* [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 대한수학회 수학용어한글화 게시판]
  
−
 
+
  
−
 
+
  
−
==사전 형태의 자료==
+
==사전 형태의 자료==
  
 
* [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/완전순열]
 
* [http://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8-%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC http://ko.wikipedia.org/wiki/포함-배제의_원리]
 
* [http://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8-%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC http://ko.wikipedia.org/wiki/포함-배제의_원리]
 
* http://en.wikipedia.org/wiki/derangement
 
* http://en.wikipedia.org/wiki/derangement
−
* http://www.wolframalpha.com/input/?i=
+
* http://www.wolframalpha.com/input/?i=A000166
−
* [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=
 
  
−
 
+
==블로그==
 +
 
 +
* [http://bomber0.byus.net/index.php/2008/07/26/696 derangement : 목욕탕에서 서로 등을 밀어주는 경우의 수와 자연상수]
 +
** 피타고라스의 창, 2008-7-26
  
−
 
 
  
 
==관련논문==
 
==관련논문==
 +
* 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.
  
−
* http://www.jstor.org/action/doBasicSearch?Query=
 
−
* http://dx.doi.org/
 
−
 
−
 
 
−
 
−
==관련도서 및 추천도서==
 
−
 
−
*  도서내검색<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=
 
  
−
 
+
[[분류:조합수학]]
 +
[[분류:수열]]
  
−
 
+
==메타데이터==
−
 
+
===위키데이터===
−
==관련기사==
+
* ID :  [https://www.wikidata.org/wiki/Q1207920 Q1207920]
−
 
+
===Spacy 패턴 목록===
−
*  네이버 뉴스 검색 (키워드 수정)<br>
+
* [{'LEMMA': 'derangement'}]
−
** 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=
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
==블로그==
 
−
 
 
−
* [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]
 

2021년 2월 17일 (수) 03:47 기준 최신판

개요

  • 고정점을 갖지 않는 순열을 교란순열이라 함 (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"