2007/08/12 21:45
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도 있던데.. 그건 뭐지..
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
행렬곱
등등..
관련된 논문
catalan.pdf카탈란 수가 적용되는 예가 무지 많다..
Super Catalan도 있던데.. 그건 뭐지..
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| 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 |
Trackback Address :: http://helloneo.pe.kr/trackback/25
|
Tracked from †너를 위한 랩소디† | 2009/04/22 22:44 | DEL
http://apnetwork.tistory.com/25
알고리즘 분석 chian matrix multiplication 의 곱하는 매트릭스 갯수에 따른 곱셈하는 경우의 수 구하는 공식 찾다가 발견 |
