ps:카탈랑_수
카탈랑 수 (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)! )
- 관련 문제: 파댕이의 케이크 만들기
ps/카탈랑_수.txt · 마지막으로 수정됨: 2023/12/19 14:52 저자 teferi
토론