| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1998년01월11일(일) 14시02분10초 ROK 제 목(Title): Catalan Number에 대해서.. n번재 catalan number는 (2n choose n) / (n+1) 입니다. 재귀적인 구조를 가지는 수많은 문제에서 종종 부딛히게 되죠.. 예를 들어서.. 1) 수열 (a[1], a[2], ..., a[2n])이 있어 다음을 만족한다고 하자. a[i] = +1 or -1 a[1] + a[2] + ... + a[2n] = 0 a[1] + a[2] + ... + a[i] >= 0 for all 1 <= i <= 2n 당연히 a[i]=1 인 i 는 n 개 뿐이겠죠. 그럼 이러한 수열은 몇개나 있을까요? 2) Y 자 모양의 갈래길이 있습니다. 더 정확히는... (A) ---. .--- (B) \ / Y | (C) A 쪽에 1에서 n까지의 번호가 매겨진 차들이 한 줄로 서 있다고 합시다. 이 Y형 길을 지나서 차가 빠져나갈 때(길은 한대가 빠져나갈 만큼 좁습니다), B에 차들이 1에서 n까지 번호순으로 도착하는 경우의 수는?? (차는 A->C, C->B 로만 움직일 수 있다고 합시다.) (2, 1, 3) 순이었다면... 2번 차 A->C 1번 차 A->C 1번 차 C->B <- 1 도착 2번 차 C->B <- 2 도착 3번 차 A->C 3번 차 C->B <- 3 도착 순이면 됩니다. 하지만 (2, 3, 1) 순이었다면 죽어도 못 통과합니다. 3) 끝이 n+1 개로 이루어진 이진 트리를 그려봅시다. n=2일 경우엔 두가지 방법이 있습니다. /\ /\ /\ \ / /\ A B C A B C n=3일 경우엔 자그마치 5가지 방법이 있습니다. /\ /\ /\ /\ /\ /\ \ /\ \ / \ / /\ / /\ /\ \ \ / /\ \ /\ /\ / /\ \ / / /\ A B C D A B C D A B C D A B C D A B C D n=10일 경우엔 몇가지 방법이 있을까요? (정답: 16796) 그럼 일반적인 n일 때는?? 4) n+1 개의 숫자 x[0], x[1], ..., x[n] 이 있습니다. 이것의 합 x[0]+x[1]+...+x[n]을 구하려고 합니다. 이 식에 적당히 괄호를 치는 방법은 몇가지나 될까요? (결합법칙만 사용하고, 교환법칙은 사용하지 않을 때..) 5) (n+2)각 볼록 다각형이 있습니다. 여기에 대각선을 n-1 개 그리면 모두 삼각형이 되도록 자를 수 있습니다. 이 방법은 몇 가지나 될까요? 6) n 개의 node(말단, 중간 포함)를 가지는 rooted tree의 갯수는? 이 모든 문제의 답이 모두 n 번째 Catalan number입니다. n 번째 Catalan number를 C[n] 이라고 할 때, C[n] 은 다음과 같이 유도해 낼 수 있습니다. C[0] = 1 C[n] = C[0]C[n-1] + C[1]C[n-2] + ... + C[n-1]C[0] if n > 0 (직접 유도해 보시려우??) 좀 더 쉬운 걸 원하신다고요? 그럼 (1 - root(1-4z))/2z 식을 Taylor series로 전개할 때에 z^n 에 붙는 상수 항이 바로 C[n] 입니다. -- 박종대 |