Catalan's Number
 
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...



구하는 법 

C(n) = (2nCn) / (n+1) = (2n)! / ((n+1)! * n!)
or
C[0]=1, C[n+1] = C[0]C[n] + C[1]C[n-1] + ... + C[n]C[0]


 
Catalan 수가 적용되는 예

n개의 노드로 만들 수 있는 tree 개수
n+2 측면으로 된 다각형을 n 삼각형들로 자를 수 있는 방법의 수
한 번에 두 개씩, 괄호 안에 곱해지며 늘여지는 수들을 놓는 방법의 수
n +1로 남겨지는 planar binary trees의 수
길이 2n을 통해서 n-by-n로 향하는데 주요한 대각선을 넘지 않는 경로의 수
stack-sort
행렬곱
등등..



관련된 논문






카탈란 수가 적용되는 예가 무지 많다..
Super Catalan도 있던데.. 그건 뭐지..

'Problem Solving > Algorithm notes' 카테고리의 다른 글

Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Game Theory  (0) 2007.12.19
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12
Multinomial Theorem  (0) 2007.08.04

Comments

  1. 김우현 2007.08.15 08:29 Permalink Modify/Delete Reply

    astein님께서 catalan number라고 말한게 이거였군요 +_+!

  2. 이선진 2007.08.15 13:17 Permalink Modify/Delete Reply

    오~ 이런 것도 있었네요 ㅎㅎ
    퍼갈데는 없고, 저거 참고할께요

  3. mynotepad 2007.08.17 10:49 신고 Permalink Modify/Delete Reply

    Catalan Number 논문이 참 내용이 좋네...
    퍼갈께~ ;)

  4. 2007.08.24 00:41 Permalink Modify/Delete Reply

    이선진이는 내 블로그는 안오고.. 규욱이 형만 좋아해.. 흥~

  5. 무릎팍동생준모팍 2007.09.21 22:41 Permalink Modify/Delete Reply

    이거 2.1 해석좀해주세요 왜 그렇게 칼라탄넘버가 이용되는지 모르겠네요 왜 성립하는 지 알려주실분 후하게 사례하겠습 니 다

    • helloneo 2007.09.22 01:00 신고 Permalink Modify/Delete

      2.1에서 설명하는것은 convex polygon에 대해서 triangulation가능한 개수를 구해보니 카탈란 넘버가 되더라.. 입니다.. polygon에 대해서 임의의 대각선을 그을때 쪼개지는 두개의 polygon에 대해서 또 같은 식이 적용되죠.. 음.. 그림을 그리면서 설명하면 좋은데.. 힘드네요.. ^^

Leave a Comment


to Top