"카탈란 수 (Catalan numbers)"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
(피타고라스님이 이 페이지의 이름을 카탈란 수로 바꾸었습니다.)
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>
  
 +
 
 +
 +
 
 +
 +
<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>
 +
 +
* [[조합수학]]에서 빈번하게 등장하는 수열의 하나로 <math>n\geq 0 </math>에 대하여 다음과 같이 정의됨<br><math>C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}</math><br>
 +
*  수열<br> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …<br>
 +
 +
 
 +
 +
 
 +
 +
<h5>생성함수</h5>
 +
 +
 
 +
 +
 
 +
 +
 
 +
 +
<h5 style="margin: 0px; line-height: 2em;">격자경로와 카탈란 수</h5>
 +
 +
*  (0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로<br>''''''<math>{2n \choose n}</math>''''''<br>
 +
*  (0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로 중에서 직선 <math>y=x</math>를 넘지 않는 경우의 수<br>
 +
 +
 
 +
 +
 
 +
 +
(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구한 다음,<br> 그 중에서 y=x를 넘어서 가는 방법의 수를 빼면 된다. 이 방법의 수가 얼마가 되겠느냐를 구하는 과정에서 일대일대응이 등장한다.
 +
 +
 
 +
 +
'''일단계'''
 +
 +
 
 +
 +
(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.<br> 이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.<br> 각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다.<br> 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 이다.<br> 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 이다.
 +
 +
 
 +
 +
'''이단계'''
 +
 +
 
 +
 +
이제 y=x를 넘어서서 가는 경로의 수를 구하자. 경로는 반드시 y=x+1과 만나게 될 것이다.
 +
 +
 
 +
 +
 +
 +
 
 +
 +
이 때, 이 경로의 (0,0)에서부터 y=x+1과 처음으로 만나는 점까지를 잘라서, y=x에 대칭시키자.
 +
 +
 
 +
 +
 +
 +
 
 +
 +
그리고 나머지 경로를 평행이동시켜 대칭이동된 경로에 갖다붙이자.
 +
 +
 
 +
 +
 +
 +
 
 +
 +
그 결과는 (0,0)에서 출발하여 (n+1,n-1)에 도착하는 경로일 것이다.
 +
 +
 
 +
 +
 +
 +
 
 +
 +
위에서 한 작업은 서로 다른 두 경로의 집합 사이에 어떤 대응을 만들어 낸 것이다. 이 대응은 일대일 대응이다.<br> 일대일대응임을 보이기 위해서는 두 가지를 생각해야 한다. 첫번째는, 서로 다른 것으로 대응되었는지를 살피고, 두번째는 공역의 모든 원소가 대응되었는지를 살피는 것이다.
 +
 +
 
 +
 +
y=x를 넘어서서 가는 경로는 (0,0)에서 (n+1,n-1)까지 가는 경로와 일대일 대응되므로 그 개수는 <math>{2n \choose n+1}</math>이다.
 +
 +
 
 +
 +
'''따라서 처음에 제기했던 문제의 답은 다음과 같다.'''
 +
 +
 
 +
 +
 +
 +
 
 +
 +
이렇게 해서 얻어진 수열 을 catalan number라고 하는데, 이 수는 조합수학에서 꽤나 자주 등장한다.
 +
 +
 
 +
 +
<h5>재미있는 사실</h5>
 +
 +
 
 +
 +
* 네이버 지식인 http://kin.search.naver.com/search.naver?where=kin_qna&query=
 +
 +
 
 +
 +
 
 +
 +
<h5>역사</h5>
 +
 +
* [[수학사연표 (역사)|수학사연표]]
 +
 +
 
 +
 +
 
 +
 +
<h5>메모</h5>
 +
 +
 
 +
 +
 
 +
 +
<h5>관련된 항목들</h5>
 +
 +
 
 +
 +
 
 +
 +
<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/Catalan_number
 +
* 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>
 +
 +
*  구글 블로그 검색<br>
 +
** 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월 7일 (월) 11:46 판

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

 

 

개요
  • 조합수학에서 빈번하게 등장하는 수열의 하나로 \(n\geq 0 \)에 대하여 다음과 같이 정의됨
    \(C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}\)
  • 수열
    1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

 

 

생성함수

 

 

 

격자경로와 카탈란 수
  • (0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로
    '\({2n \choose n}\)'
  • (0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로 중에서 직선 \(y=x\)를 넘지 않는 경우의 수

 

 

(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구한 다음,
그 중에서 y=x를 넘어서 가는 방법의 수를 빼면 된다. 이 방법의 수가 얼마가 되겠느냐를 구하는 과정에서 일대일대응이 등장한다.

 

일단계

 

(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.
이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.
각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다.
따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 이다.
즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 이다.

 

이단계

 

이제 y=x를 넘어서서 가는 경로의 수를 구하자. 경로는 반드시 y=x+1과 만나게 될 것이다.

 


 

이 때, 이 경로의 (0,0)에서부터 y=x+1과 처음으로 만나는 점까지를 잘라서, y=x에 대칭시키자.

 


 

그리고 나머지 경로를 평행이동시켜 대칭이동된 경로에 갖다붙이자.

 


 

그 결과는 (0,0)에서 출발하여 (n+1,n-1)에 도착하는 경로일 것이다.

 


 

위에서 한 작업은 서로 다른 두 경로의 집합 사이에 어떤 대응을 만들어 낸 것이다. 이 대응은 일대일 대응이다.
일대일대응임을 보이기 위해서는 두 가지를 생각해야 한다. 첫번째는, 서로 다른 것으로 대응되었는지를 살피고, 두번째는 공역의 모든 원소가 대응되었는지를 살피는 것이다.

 

y=x를 넘어서서 가는 경로는 (0,0)에서 (n+1,n-1)까지 가는 경로와 일대일 대응되므로 그 개수는 \({2n \choose n+1}\)이다.

 

따라서 처음에 제기했던 문제의 답은 다음과 같다.

 


 

이렇게 해서 얻어진 수열 을 catalan number라고 하는데, 이 수는 조합수학에서 꽤나 자주 등장한다.

 

재미있는 사실

 

 

 

역사

 

 

메모

 

 

관련된 항목들

 

 

수학용어번역

 

 

사전 형태의 자료

 

 

관련논문

 

관련도서 및 추천도서

 

 

관련기사

 

 

블로그
원본 주소 "https://wiki.mathnt.net/index.php?title=카탈란_수_(Catalan_numbers)&oldid=19452"