====== 카탈랑 수 (Catalan number) ======
  * 카탈**란** 수라고 표기하는 책도 많은 것 같은데, 여기서는 [[https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98|위키피디아]]를 따라서 카탈**랑**수로 표기한다
    * 사실 이 수열을 처음 만든 사람은 카탈랑이 아니다. 기록상 처음 사용한 사람은 몽골 수학자 명안도이고, 유럽 기준으로는 오일러가 삼각분할의 갯수를 설명할때 처음 사용했다.
  * 카탈랑 수가 뭔지를 설명하기 전에, 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. [[https://en.wikipedia.org/wiki/Dyck_language|Dyck word]]로 변환되는 문제들
      * Dyck word의 갯수
        * n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것의 갯수
      * [[https://www.findstat.org/CollectionsDatabase/Cc0005/|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보다 큰 임의의 수가 된다면, [[ps:Bertrand's ballot theorem]] 문제가 된다. 이것을 증명하는 방법도 역시 격자에서의 경로문제로 변환해서 증명하는 것이 가장 간단하다.
      * n쌍의 괄호로 만들수 있는 올바른 괄호 표현식의 갯수
        * (를 X, )를 Y로 놓으면 Dyck word
  * '올바른 괄호 표현식의 갯수'가 쉽게 양쪽으로 변환이 되는 편이다. 이 문제를 연결고리로 생각하면 위의 두 카테고리가 모두 동일한 문제가 된다는 것을 이해할 수 있다.

===== 일반식 =====
  * 일반식을 유도하는 방법은 다양하다.[[https://en.wikipedia.org/wiki/Catalan_number#Proof_of_the_formula|위키피디아]]에는 6가지 증명법이 나와있다. 그중에서 대표적인 두가지만 들면,
  * 첫번째 방법은 점화식을 일반식으로 변환하는 것이다. 생성함수를 이용해서 계산하는 방법인데 간단하지는 않다. 과정은 [[https://namu.wiki/w/%EC%B9%B4%ED%83%88%EB%9E%91%20%EC%88%98|나무위키]] 를 참고.
  * 두번째 방법은 Dyck path 문제에서 유도하는 방식이다. 수학적 지식 없이도 직관적으로 이해 가능하고, 다른 문제에 활용하기에도 유리하다.
    * [[https://namu.wiki/w/%EC%B9%B4%ED%83%88%EB%9E%91%20%EC%88%98?from=%EC%B9%B4%ED%83%88%EB%9E%80%20%EC%88%98#s-1.3|나무위키]]
    * 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) 이 된다.

===== 계산 =====
  * 사실 식 자체가 [[ps:이항 계수]]이므로 이항계수를 구하는 방법을 똑같이 적용하면 된다.
  * 한개의 특정 항, 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!의 모듈러 역원이 필요하다. 이는 [[ps:모듈러 연산]] 에서 설명한 방법으로 둘다 O(K)에 계산 가능하므로 시간복잡도에 변화는 없다.
    * q의 갯수가 K보다 많이 작은 경우에는 C_i를 모두 구하는 첫번째 방법보다, 그냥 팩토리얼만 구해두는 두번째 방법이 좀더 빨랐다. 
      * 그리고 팩토리얼의 모듈러 역원을 미리 구해두기보다는 그냥 O(logP)의 추가시간을 들여서 그때그때 역원을 계산하는 것이 좀더 빨랐다. 

===== 관련 문제 =====
  * [[ps:problems:boj:4811]] - Dyck Word. K<=30
  * [[ps:problems:boj:9343]] - Dyck Word. K<=1,000,000, q<=1000
  * [[ps:problems:boj:10422]] - 올바른 괄호문자열. K<=2500, q<=100
  * [[ps:problems:boj:18132]] - 이진트리의 갯수. K<=5000, q<=100

===== 변형 및 일반화 =====
  * 점화식으로 표현할 때, 한개를 제외한 나머지들을 두 묶음으로 나누는 방식이 아니라, 두개를 제외하고 나머지를 두 짝수개의 묶음으로 나누는 방식으로 세워지는 경우도 있다.
    * DP[n+2] = DP[0]*DP[n] + DP[2]*DP[n-2] + ... + DP[n]*DP[0] 와 같은 식.
    * 당황하지 말고, DP[n] = $ C_{n/2} $ 으로 치환하면 카탈랑 수의 점화식과 같아진다.
    * 관련 문제: [[ps:problems:boj: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]])
    * 이것은 [[wp>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} $ 이다
      * 코드는 이런식
        * <dkpr py>
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
</dkpr>
    * 관련 문제: [[ps:problems:boj: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행짜리 직사각형 모양의 표준 [[ps:영 타블로]]의 갯수를 세는 문제로 변환해서 생각하는 것이 더 간단하다. 그러면 표준 영 타블로의 개수를 세는 Hook length formula 를 적용해서 공식을 유도할 수 있다.
    * 그러면 d차원 카탈랑 수의 n번째 항 (=d종류의 알파벳을 각각 n개씩 사용해서 만드는 문자열 중에서, 조건을 만족하는 문자열의 갯수) 은 다음처럼 공식을 적을수 있다.
      * (n*d)! * 0!*1!*..*(d-1)! / ( n!*(n+1)!*..*(n+d-1)! )
    * 관련 문제: [[ps:problems:boj:30984]]