사용 방법 (3단계)
- n과 표현 방식(괄호열, 경로, 트리)을 고릅니다.
- 전체 나열 또는 샘플링을 선택하고, 필요한 경우 제한값과 seed를 조정합니다.
- C_n, 예시, 전체 표를 확인한 뒤 CSV로 내보내거나 URL을 공유합니다.
입력
결과
C_n 값
C_n = (1 / (n + 1)) * C(2n, n)
C_0 = 1, C_{n+1} = sum_{i=0..n} C_i * C_{n-i}
예시 읽는 법
괄호열은 '('와 ')'를 씁니다. 경로는 위쪽을 U, 오른쪽을 R로 표시합니다. 트리는 잎을 '*'로 두고 (L,R) 형태로 씁니다.
n이 크면 전체 나열은 자동으로 꺼집니다. 샘플링은 고정 seed를 쓰는 균등 DP 방식입니다.
예시
표 (C_0부터 C_nMax까지)
| n | C_n | 자릿수 |
|---|
예시 풀이
n = 3 (문자열 5개)
길이가 6인 올바른 괄호열은 ((())), (()()), (())(), ()(()), ()()()입니다.
n = 10 (C_10 = 16796)
테스트 데이터가 필요하면 샘플링으로 예시를 둘러보고 CSV로 내보내세요.
자주 묻는 질문
카탈란 수란 무엇인가요?
카탈란 수는 올바른 괄호열, Dyck 경로, 완전 이진 트리처럼 같은 점화식을 따르는 구조의 개수를 셉니다.
왜 전체 나열에 제한이 있나요?
예시 개수가 매우 빠르게 늘어나기 때문입니다. 샘플링을 쓰면 페이지가 가볍게 동작하면서도 대표 예시를 볼 수 있습니다.
샘플링은 균등한가요?
네. DP 개수를 이용해 각 단계를 고르므로 가능한 Dyck 단어가 같은 확률로 선택됩니다. 같은 seed를 쓰면 같은 목록을 다시 얻습니다.
Dyck 경로와 괄호열은 어떻게 대응하나요?
여는 괄호 '('는 U, 닫는 괄호 ')'는 R로 바꿉니다. 괄호열이 올바르면 경로가 대각선을 넘지 않습니다.
다각형 삼각분할과는 어떤 관계가 있나요?
볼록 (n+2)각형을 삼각형으로 나누는 방법의 수도 C_n입니다. 그래서 다각형 삼각분할도 카탈란 구조의 한 예입니다.
여기서 트리는 어떻게 정의하나요?
이 계산기는 내부 노드가 n개인 완전 이진 트리를 사용합니다. 잎은 '*'로 표시하고, 내부 노드는 (L,R) 형태로 씁니다.