조합론 - C++ 로 구현한 카탈란 수(Catalan Number), 원리와 응용

소개

조합론의 주요 수열 중 하나인 카탈란 수(Catalan Number) 에 대해서 정리한 리포트입니다.
응용사례 및 실제 동작하는 구현 소스코드가 포함되어 있어 프로그래밍 및 이산수학을 공부하시는 분들께 매우 유용합니다.

목차

조합론 - 카탈란 수(Catalan Number)

1. 개요
2. 설명
3. Catalan Number 가 적용되는 예
4. Catalan Number 구현 (C++)
5. 참고문헌

본문내용

조합론 – 카탈란 수 (Catalan Number)

조합론에서는 일정한 규칙을 가진 수열이 자주 등장한다. 대표적인 예가 바로 피보나치 수열(Fibonacci Numbers) 이며, 이 외에도 여러 가지 수열들이 많은데, 여기에서는 조합론에서 자주 등장하는 수열 중 하나인 카탈란 수에 대해서 알아보기로 한다.

1. 개요

카탈란 수(Catalan Number) 란 다음과 같이 정의되는 수를 말하며, 여러 응용 분야가 존재하여 조합론 분야와 프로그래밍 경시대회와 같은 문제풀이 대회에서 매우 자주 등장한다.

= =

이는 주어진 조건들이 2(n-1) 개인 상태에서 n-1 개 만큼 선택하는 경우의 수들이 된다.

Catalan Number 의 첫 10개는 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 이 된다.

2. 설명

각각 n 개의 왼쪽, 오른쪽 괄호가 있을 때 괄호의 짝을 맞춰서 식을 만드는 경우의 수는 얼마일까? 예를 들어 n = 3 인 경우에는 ((())), ()(()), (())(). (()()), ()()() 이렇게 다섯 가지 방법이 있다.

맨 왼쪽에 있는 괄호 l 은 오른쪽에 있는 어떤 괄호 r 에 매치되며 이 괄호들은 전체 식을 l 과 r 사이에 있는 부분과 r 오른쪽에 있는 부분, 이렇게 두 개의 균형 잡힌 식으로 나눈다. l 과 r 이 한 쌍을 이루므로, 왼쪽 부분에 k쌍의 괄호가 있다면, 오른쪽 부분에는 n-k-1 쌍의 괄호가 있어야 한다.


N 개의 짝을 가진 괄호가 입력될 때, 이 괄호들의 짝을 맞추는 방법의 수

참고자료

· Tom Davis – Catalan Numbers, November, 26, 2006
· Programming Challenges