카탈랑 수 계산기

괄호 n쌍을 짝이 어긋나지 않게 묶는 방법의 수입니다. C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14로 이어지며, 예를 들어 괄호 3쌍은 ((())), (()()), (())(), ()(()), ()()() 로 정확히 5가지입니다.

C(n+1) = C(n) × 2(2n+1) / (n+2) 라는 승법 점화식을 씁니다. 원래 닫힌 형태 C(n) = (2n)!/(n!(n+1)!)을 그대로 계산하면 n이 커질수록 분자·분모가 함께 천문학적으로 커지지만, 이 점화식은 매 단계 정수 하나만 곱하고 나눠 훨씬 빠르고 오차가 없습니다.

네. 마디(내부 노드) n개짜리 이진트리의 모양 수, (n+2)각형을 대각선으로 잘라 전부 삼각형으로 나누는 방법의 수, n×n 격자에서 대각선을 넘지 않고 걷는 단조경로의 수 — 전부 같은 카탈랑 수 C(n)입니다. 겉보기엔 다른 문제지만 같은 재귀 구조(맨 바깥을 왼쪽·오른쪽으로 나눠 센다)를 갖기 때문입니다.

C(n) = C(2n,n)/(n+1) = (2n)!/(n!(n+1)!)로도 같은 값이 나옵니다. 다만 (2n)!을 그대로 계산하면 n=100만 되어도 분자·분모가 150자리를 넘는 수가 되어 비효율적입니다. 이 계산기는 두 공식이 항상 같은 값을 내는지 테스트로 교차 검증했습니다.

대략 4ⁿ/n^1.5에 비례해서 커집니다. n이 하나 늘 때마다 거의 4배씩 뛴다는 뜻으로, 50번째 항만 해도 이미 28자리 수입니다.

아니요. 모든 계산은 브라우저 안에서만 이뤄지며 서버로 전송되지 않습니다.