[프로그래밍 수학] 카탈란 수(catalan number)

 이 개념이 적용된 프로그래밍 문제를 풀 때 풀이과정이 흥미로웠다. 이를 다른 사람들과 공유하고 동시에 기록에 남기고 싶어서 이렇게 글을 쓴다.

 

카탈란 수는 자연수로 이루어진 수열이다. 항을 차례대로 나열하면 아래와 같다.

 

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, ...

 

카탈란 수를 C_n이라고 하고 이를 점화식으로 표현하면

이를 조합으로 표현하면

이 조합은 어떻게 얻어진 것일까?

---

나는 카탈란 수라는 개념을 주어진 key로 만들 수 있는 Binary Search Tree의 개수를 구하는 문제에서 처음 접했다.

https://soccer-programming.tistory.com/15

Program to find the total number of possible Binary Search Trees with n keys. feat. catalan number

---

문제에서 어떠한 방식으로 활용되는지는 위의 링크를 참고하면 된다.

이 문제 말고도, n쌍의 괄호로 만들 수 있는 다른 괄호의 갯수를 구하는 문제, 정사각형으로 이루어진 평면에서 최저경로로 목적지에 가는 경우의 수를 묻는 문제 등 흥미로운 것들이 많다. 관심이 있으신 분은 한 번 찾아보길 권장한다.

---

우리는 위의 수열이나, 문제의 규칙성을 찾아내는 과정에서 아래의 점화식을 얻었다. (링크에서 점화식 얻는 부분 보고오기)

위의 점화식을 이용하여 일반항을 구하기 위해 아래와 같이 생성함수를 선언하고

---

생성함수란?

생성 함수는 여러 경우에 이용되는데 예를 들어 어떤 수열에 대한 점화식을 이용하여 일반항을 알아낼 때에도 쓰인다.

---

 

이를 정리하면

 

근의 공식을 이용하면

c(0)이 0이므로

근은 부호가 음수인 경우이다.

 

이제 여기서 일반화된 이항정리(Newton's generalized binomail theorem)를 이용한다. 이를 이용하여 c(x)값을 다시 다른 급수형식으로 표현할 수 있다.(한정된 합을 한정되지 않은 수열로 표현할 수 있다)

일반화된 이항정리(뉴턴의 이항정리)

z값에 y, n값에 1/2을 넣은 경우

여기서 y값에 -4x를 넣고 생성함수를 정리하면 아래와 같다.

 

생성함수의 n항의 계수가 카탈란 수의 일반항이므로 

가 성립한다.

 

규칙성 발견->카탈란수점화식->생성함수->근의공식->이항정리->생성함수의n차항->카탈란수의일반항

---

 

참고자료

https://en.wikipedia.org/wiki/Catalan_number
https://blog.naver.com/wlsthf9401/60168275689
https://jjycjnmath.tistory.com/139
https://suhak.tistory.com/77
https://terms.naver.com/entry.nhn?docId=3405365&cid=47324&categoryId=47324
https://terms.naver.com/entry.nhn?docId=3405166&cid=47324&categoryId=47324