확률과 통계

카탈란 수

점확식의 의미: 한 가지 경우를 시행하면 그와 쌍이 되는 다른 경우를 반드시 시행해야 하는 모든 개수, 즉 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다.

Cn은 길이가 2n인 모든 Dyck word의 개수
n개의 X와 n개의 Y로 이루어진 문자열 중, 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것
- XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY
X를 여는 괄호, Y를 닫는 괄호로 보면 n쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수
- [[[]]] [][[]] [][][] [[]][] [[][]]
  활용 문제
  1. Cn은 n+1개의 항에 괄호를 씌우는 모든 경우의 수 (위의 경우, n=3)
  2. n+1개의 항에 이항연산자를 적용하는 순서의 모든 가짓수
  3. 정사각형으로 이루어진 평면에서 최저 경로로 목적지에 가는 경우의 수
0 0 B
0 0 0
A 0 0
- 위와 같이 A에서 B까지 최단경로로 도착하기 위해서는 오른쪽/위쪽 밖에 길이 없다. 그리고 반드시 이 방향은 대칭이므로 카탈란 수이다.