카탈랑 수 Catalan Number

https://en.wikipedia.org/wiki/Catalan_number

Catalan number - Wikipedia

위키피디아의 카탈란 수 페이지를 요약 정리해본 내용입니다!

---

 

카탈랑 수는 여러가지 조합 수 세기 문제에서 발생하는 자연수의 수열이다.
재귀적으로 정의된 객체를 포함하는 경우가 많다

점화식

카탈랑 수를 나열해보면,

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

 

조합론에서 응용되는 사례

조합의 수를 세는 많은 문제들을 카탈랑 수를 사용해서 풀 수 있다.
Richard P. Stanley는 The book Enumerative Combinatorics: Volume 2라는 책에서 66개의 카탈랑 수 조합 문제를 소개하기도 했다.

 

1. 길이가 2n인 Dyck Words

Dyck word는 총 n 쌍의 X, Y로 구성된 문자열인데, 어떤 경우에서도 X보다 많은 수의 Y가 먼저 나올 수 없다.
(예를 들어 문자열에서 Y가 등장하려면 최소한 1개의 X가 먼저 등장해야 한다)

e.g. 문자열 길이가 6인 Dyck words (XY 3쌍)
C3 ⇒ XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

2. n개의 괄호 쌍을 포함하는 수식 조합

Dyck 단어에서 XY를 ()로 대체하여 생각하면 된다

e.g. 괄호쌍 3개의 조합 수
C3 ⇒ ((())) ()(()) ()()() (())() (()())

3. n번의 이항 연산의 조합 수

n+1개의 요소를 괄호로 완전히 둘러쌀 수 있는 경우의 수라고 생각해도 된다

e.g. 4개의 문자를 괄호로 완전히 둘러싸는 경우 (혹은 4개의 피연산자를 이항 연산하는 조합의 수)
C3 ⇒ ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

4. leaf 노드가 n+1개인 서로 다른 포화 이진 트리의 개수

연속적인 이항 연산의 조합은 포화 이진 트리(모든 분기점에서의 자식 노드가 꽉 차있거나 아예 없는 트리)로도 표현할 수 있다. leaf 노드가 n+1개인 서로 다른 이진 트리의 갯수는 카탈랑 수를 따른다.

e.g. leaf 노드가 4개인 서로 다른 포화 이진트리의 개수 (C3)

5. n*n 격자 그리드에서 서로 다른 경로의 수 찾기

단조 격자 경로 (단조monotonic: 증가/감소의 경향이 유지되는 것, 단조증가함수는 감소하는 구간이 없는 함수)에서 대각선 위로는 지나가지 않고 최종 지점까지 도착하는 서로 다른 경로의 수를 구할 때 사용할 수 있다.

단조 경로(Monotonic path)는 왼쪽 아래 구석에서 시작하여 오른쪽 위 구석까지 갈 때 오른쪽과 위로만 이동하는 경로를 의미한다.
Dyck 단어의 수를 세는것과 동일하게 생각해도 된다. X = 오른쪽으로 이동, Y = 위로 이동

e.g.
C4 ⇒ 4*4 그리드에서 대각선 위로 지나지 않고 (0, 0)에서 (4, 4)까지 이동하는 서로 다른 경로의 수

e.g.
위 그림을 column당 height의 리스트로 나타낼 수 있다 (그림의 순서대로)

             [0,0,0,0] [0,0,0,1] [0,0,0,2] [0,0,1,1]
[0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2] [0,0,2,2] [0,0,1,3]
               [0,0,2,3] [0,1,1,3] [0,1,2,2] [0,1,2,3]

6. 산 그리기

Dyck words의 XY를 Up, Down으로 치환해서 생각하면 된다
대각선을 위로만 그리고 바닥 밑으로는 내려가지 않는다는 경우도 똑같다.

7. 정 n+2각형을 쪼개서 만들 수 있는 삼각형의 개수

8. Stack-Sortable Permutation (트리순열) 의 n번째 요소

Stack-sortable permutaion은 이진 트리와 상호 변환이 가능한, 동일한 개념이라고 생각할 수 있다.

이진 트리의 노드를 왼쪽에서 오른쪽으로 번호를 매기고, 그 순서 번호들을 전위 순회 (Root → Left → Right) 시 방문하는 순서대로 나열하면 Stack-Sortable 순열이 된다.

반대로 Stack-sortable 순열을 이진트리로 변환할 때, 순열의 첫번째 값은 이진트리의 루트 번호가 되고 두번째는 왼쪽 서브트리의 루트, ... 의 식으로 바꿔서 생각할 수 있다.

e.g. 트리 순열 {5,2,1,4,3,7,6}일 때

9. 패턴 123을 따르지 않는 순열의 수

패턴 123(혹은 다른 n개 요소의 패턴)을 따르지 않는 순열의 개수를 구할 때 사용 가능하다.

e.g. n이 3일 때
C3 ⇒ 132, 213, 231, 312 and 321.

e.g. n이 4일 때
C4 ⇒ 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 and 4321.

10. 겹치지 않는 부분집합의 갯수

e.g. 5개의 요소를 겹치지 않는 부분집합으로 나누는 경우의 수 (C5)

11. 높이가 n인 계단을 n개의 사각형으로 나누는 경우의 수

e.g. 높이가 4인 계단을 4개의 사각형으로 나누는 경우 (C4)

12. 2*n의 사각형을 채울 수 있는 standard Young tableaux 개수

{1,2, ... , 2n}의 수열을 2행 n열의 사각형에 채우는데,
각 행에 있는 요소들이 오름차순으로 정렬되도록 하는 경우의 수를 구할 수 있다.

13. 2n각형의 꼭지점에서 서로 교차하지 않는 쌍으로 나눌 수 있는 경우의 수

e.g. 원탁에 둘러앉은 2n명의 사람들이 서로 팔이 교차되지 않으면서 악수할 수 있는 경우의 수