Header

  1. View current page

    수학이 알고싶은 중고대딩들을 위한 수학 노트

Springnote Home
Profile_image?t=1256009541&type=big
33 1217

All Pages

Updates

Add to Watch List

카탈란 수열(Catalan numbers)

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

 

 

개요
  • 조합수학에서 빈번하게 등장하는 수열의 하나
  • (0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로 중에서 직선 y=x를 넘지 않는 경우의 수

  • 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, …

 

 

점화식
  • c_{n+1}=c_0c_n+c_1c_{n-1}+\cdots+c_nc_0

 

 

생성함수
  • 기본적인 내용에 대해서는  생성함수 항목을 참조

  • 카탈란 수열의 생성함수는 다음과 같이 주어짐

    G(x)= c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n + \cdots=\frac{1-\sqrt{1-4x}}{2x}

    (증명)

    x G(x)^2= (c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n + \cdots)^2=c_0^2x+(c_0c_1+c_1c_0)x^2+(c_0c_2+c_1c_1+c_2c_0)x^3+\cdots=G(x)-1

    x G(x)^2-G(x)+1=0

    따라서 G(x)= \frac{1-\sqrt{1-4x}}{2x} ■

 

 

근사식


 

격자경로와 카탈란 수

  • (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}이다.

 

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

 {2n \choose n}-{2n \choose n+1}=\frac{1}{n+1}{2n \choose n}

 

■

 

 

 

적분표현

  • c_n=\int_{0}^{1} 2^{2n+1}{\cos^{2n} \pi x}\, {\sin^2 \pi x}\,dx

 

 

 

재미있는 사실

 

  • 네이버 지식인 http://kin.search.naver.com/search.naver?where=kin_qna&query=

 

 

역사

 

 

메모

 

 

관련된 항목들

 

 

수학용어번역

 

 

사전 형태의 자료

 

 

관련논문
  • http://www.jstor.org/action/doBasicSearch?Query=
  • http://dx.doi.org/

 

 

관련도서

 

 

관련기사

  • 네이버 뉴스 검색 (키워드 수정)

    • 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=

 

 

블로그

Tags

수열

History

Last edited on 06/26/2010 10:06 by 피타고라스

Linked Page

Linked Pages: 5

Comments (0)

You must log in to leave a comment. Please sign in.