카탈랑 수 (Catalan number)

카탈란 수라고 표기하는 책도 많은 것 같은데, 여기서는 위키피디아를 따라서 카탈랑수로 표기한다
- 사실 이 수열을 처음 만든 사람은 카탈랑이 아니다. 기록상 처음 사용한 사람은 몽골 수학자 명안도이고, 유럽 기준으로는 오일러가 삼각분할의 갯수를 설명할때 처음 사용했다.
카탈랑 수가 뭔지를 설명하기 전에, PS에서 언제 필요한지부터 들어가보자.
많은 종류의 조합론 문제의 해가 카탈랑수로 표현된다. 이 문제가 카탈랑 수로 표현되는 문제라는 것을 알면 바로 카탈랑수의 일반식을 이용해서 계산하면 된다.
- 카탈랑 수의 일반식은 $ C_n = \frac{1}{n+1}{2n \choose n} $ 이다.
  - 이 일반식을 BigO로 표현하면, 스털링 근사를 적용해서 $ O(4^n / n^{\frac{3}{2}}) $ 으로 쓸수 있다.
아래의 문제들은 전부 같은 문제로 변환 가능하지만, 한번에 변환하는 과정이 쉽게 안떠오를 때도 있다.. 그래서 직관적으로 식을 세울때 점화식이 우선적으로 떠오르는 문제와 Dyck Word 문제로의 동치관계가 떠오르는 문제의 두 카테고리로 나눴다.
- 1. 해가 다음의 점화식으로 표현되는 문제
  - $ \begin{align} &C_0 = 1 \\ &C_{n+1} = \sum_{i+j=n} C_iC_j \end{align}$
  - 아래 문제들은 다들 이런 점화식으로 유도되므로 다들 동치이다.
    - 리프 노드가 n+1개인 full binary tree (모든 노드가 자식을 2개 또는 0개만 갖는 이진트리)의 갯수를 구하는 문제가 대표적이다.
      - 루트를 제외한 n개의 노드를 왼쪽 서브트리와 오른쪽 서브트리로 나눠서 재귀적으로 계산
      - n+1개의 항에 이항 연산을 적용하는 순서의 갯수도 같다. (연산 순서는 이진트리로 쉽게 변환된다)
    - n쌍의 괄호로 만들수 있는 올바른 괄호 표현식의 갯수
      - 맨 앞의 여는 괄호와 대응되는 닫는 괄호의 위치를 기준으로 남은 n-1개의 괄호쌍을 둘로 분할할 수 있다.
    - 볼록 n+2각형을 n개의 삼각형으로 분할하는 방법
      - 분할 방식을 이항연산 순서로 1:1 대응시키는 방법이 널리 알려져있다. 모르면 떠올리기 힘들지만, 보고나면 이해하기 쉽다.
      - 그냥 작은 문제로 쪼개서 점화식을 세우려면, 1번-2번-x번 꼭짓점으로 삼각형이 만들어지는 경우들로 나눠서 식을 세우면 된다.
- 2. Dyck word로 변환되는 문제들
  - Dyck word의 갯수
    - n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것의 갯수
  - Dyck Path의 갯수
    - 좌표평면에서 (0,0)에서 출발해서 오른쪽 또는 위쪽으로 1씩 이동하되 대각선(y=x)의 아래쪽을 지나지 않고 점 (n,n)에 이르는 방법의 수
    - 위쪽을 X, 오른쪽을 Y로 놓으면 Dyck word
  - ai가 1 또는 -1일 때, a1+a2+…+a_2n+2=0이고 각각의 부분합 a1, a1+a2, …, a1+a2+…+a_2n+1이 모두 0 보다 크게 되도록 하는 방법의 수.
    - +1을 X, -1을 Y로 놓으면 Dyck word
    - 전체 합이 0보다 큰 임의의 수가 된다면, Bertrand's ballot theorem 문제가 된다. 이것을 증명하는 방법도 역시 격자에서의 경로문제로 변환해서 증명하는 것이 가장 간단하다.
  - n쌍의 괄호로 만들수 있는 올바른 괄호 표현식의 갯수
    - (를 X, )를 Y로 놓으면 Dyck word
'올바른 괄호 표현식의 갯수'가 쉽게 양쪽으로 변환이 되는 편이다. 이 문제를 연결고리로 생각하면 위의 두 카테고리가 모두 동일한 문제가 된다는 것을 이해할 수 있다.

일반식

일반식을 유도하는 방법은 다양하다.위키피디아에는 6가지 증명법이 나와있다. 그중에서 대표적인 두가지만 들면,
첫번째 방법은 점화식을 일반식으로 변환하는 것이다. 생성함수를 이용해서 계산하는 방법인데 간단하지는 않다. 과정은 나무위키 를 참고.
두번째 방법은 Dyck path 문제에서 유도하는 방식이다. 수학적 지식 없이도 직관적으로 이해 가능하고, 다른 문제에 활용하기에도 유리하다.
- 나무위키
- nxn 격자를 이동하는 방법은 C(2n,n) 이고, 그중에서 대각선을 교차하면서 이동하는 방법의 갯수는, 교차한 위치에서 격자를 뒤집어주어 생각하면 (n-1)x(n+1) 격자를 이동하는 방법의 갯수 (= C(2n,n+1)) 과 같다. 결국 전체 경로 갯수에서 대각선 교차 경로 갯수를 뺀, C(2n,n) - C(2n, n+1) = C(2n,n)/(n+1) 이 된다.

계산

사실 식 자체가 이항 계수 (Binomial Coefficient)이므로 이항계수를 구하는 방법을 똑같이 적용하면 된다.
한개의 특정 항, C_n 의 값을 계산하기: O(n)
q개의 항, C_n1, C_n2, …, C_nq 의 값을 계산하기
- n1,n2,…n_q의 최대값을 K라고 하면, O(K)의 전처리 이후에 각 항을 O(1)에 구할수 있다.
- 첫번째 방법은 $ C_{n+1} = \frac{2(2n+1)}{n+2}C_n $ 의 점화식을 이용해서 그냥 C_i를 모두 구해두는 방법이다.
- 두번째 방법은 이항계수를 구할때와 마찬가지로 K까지의 팩토리얼 값을 미리 구해둔 뒤, $ C_n = \frac{2n!}{n!(n+1)!} $ 로 구하는 방법이다
- 보통 문제에서는 C_i % P 를 구해야 하는 경우가 대부분이므로, 첫번째는 1,2,…,K의 모듈러 역원이, 두번째는 1!,2!,…,K!의 모듈러 역원이 필요하다. 이는 모듈러 연산 (Modular arithmetic) 에서 설명한 방법으로 둘다 O(K)에 계산 가능하므로 시간복잡도에 변화는 없다.
- q의 갯수가 K보다 많이 작은 경우에는 C_i를 모두 구하는 첫번째 방법보다, 그냥 팩토리얼만 구해두는 두번째 방법이 좀더 빨랐다.
  - 그리고 팩토리얼의 모듈러 역원을 미리 구해두기보다는 그냥 O(logP)의 추가시간을 들여서 그때그때 역원을 계산하는 것이 좀더 빨랐다.

변형 및 일반화

점화식으로 표현할 때, 한개를 제외한 나머지들을 두 묶음으로 나누는 방식이 아니라, 두개를 제외하고 나머지를 두 짝수개의 묶음으로 나누는 방식으로 세워지는 경우도 있다.
- DP[n+2] = DP[0]*DP[n] + DP[2]*DP[n-2] + … + DP[n]*DP[0] 와 같은 식.
- 당황하지 말고, DP[n] = $ C_{n/2} $ 으로 치환하면 카탈랑 수의 점화식과 같아진다.
- 관련 문제: 1670
점화식이 한개를 제외한 나머지를 세 묶음으로 나누는 방식으로 생기는 경우도 있다.
- (오프셋은 좀 무시하면) 이런 형태이다
  - $ DP_{n+1} = \sum_{i+j+k=n} DP_iDP_jDP_k $
- 기존 카탈랑 수의 문제들을 확장한 문제들이 이런식의 점화식을 갖는다.
  - (2n+1)개의 리프노드를 갖는 3진 트리의 개수
  - (2n+1)개의 항에 삼항연산을 적용하는 방법의 수
  - 좌표평면에서 (0,0)에서 출발해서 오른쪽 또는 위쪽으로 1씩 이동하되 대각선(y=2x)의 아래쪽을 지나지 않고 점 (n,2n)에 이르는 방법의 수
  - 볼록 (2n+2)각형을 사각형으로 분할하는 방법의 수
  - 기타등등… (https://oeis.org/A001764)
- 이것은 Fuss-Catalan number라고 불리운다.
  - 링크된 위키피디아에서는 보다 일반화된 two-parameter Fuss-Catalan number 를 설명하는데 이렇게까지 일반화된 값을 답으로 갖는 문제는 못봤다; 위의 문제들은 r=1로 고정된 경우이고, 이렇게 파라메터 하나를 갖는 형태를 그냥 Fuss-Catalan number라고 부르기도 한다고 한다.
  - https://robertdickau.com/fusscatalan.html 위키보다 여기가 좀더 도움된다.
  - 일반항은 $ C^{(3)}_n = \frac{1}{2n+1}{3n \choose n} $, $ C^{(k)}_n = \frac{1}{((k-1)n+1}{kn \choose n} $ 이다
  - 코드는 이런식
    - def fuss_catalan(k, n, prime_mod=0): if prime_mod == 0: return math.comb(n * k, n) // ((k - 1) * n + 1) numer, denom = 1, (k - 1) * n + 1 for nu, de in zip(range(n * (k - 1) + 1, n * k + 1), range(1, n + 1)): numer = numer * nu % prime_mod denom = denom * de % prime_mod return numer * pow(denom, -1, prime_mod) % prime_mod
- 관련 문제: 2392
d차원 카탈랑 수
- Dyck word 문제를 세개의 알파벳을 사용하는 것으로 확장해보자.
  - n개의 X와 n개의 Y와 n개의 Z로 이루어진 문자열 중, 처음부터 X, Y, Z의 개수를 세어서 a(X), a(Y), a(Z)라 했을 때 항상 a(X) ≥ a(Y) ≥ a(Z) 가 되는 문자열의 갯수
  - 이것을 3차원 카탈랑 수라고 부른다. 식은 2*(3*n)!/(n!*(n+1)!*(n+2)!) 이 된다. https://oeis.org/A005789
- 이제 알파벳 갯수를 d개까지 늘리면 d차원 카탈랑 수가 된다.
- 사실 이 문제는 d행짜리 직사각형 모양의 표준 영 타블로 (Young tableau)의 갯수를 세는 문제로 변환해서 생각하는 것이 더 간단하다. 그러면 표준 영 타블로의 개수를 세는 Hook length formula 를 적용해서 공식을 유도할 수 있다.
- 그러면 d차원 카탈랑 수의 n번째 항 (=d종류의 알파벳을 각각 n개씩 사용해서 만드는 문자열 중에서, 조건을 만족하는 문자열의 갯수) 은 다음처럼 공식을 적을수 있다.
  - (n*d)! * 0!*1!*..*(d-1)! / ( n!*(n+1)!*..*(n+d-1)! )
- 관련 문제: 파댕이의 케이크 만들기

목차

카탈랑 수 (Catalan number)

일반식

계산

관련 문제

변형 및 일반화