카탈란수의 응용: n+2각형에서 삼각형으로 분할하기

카탈란수의 응용: n+2각형에서 삼각형으로 분할하기

---

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

---

 

1. 서론

저번 포스팅까지, 아주 기나긴 여정을 거쳐왔습니다. 키탈란 수가 뭔지부터 시작해서 일반항을 구하고 점화식까지 찾아봤었죠.
그러는 와중 어렵기도 하였지만, 아주 완벽하게 카탈란수의 점화식을 구해봤는데요
오늘은 본질적으로 '그래서 카탈란 수로 뭘 할 수 있는데?'에 대해 한가지 문제를 풀어볼까 합니다. 사실 그 전에 카탈란수는 여기저기 조합적 문제에서 답이 된다고 말씀드렸고, 간단하게 괄호치기 문제도 살펴보았으나 좀 더 본격적으로 문제를 하나 풀어보죠!

2. 삼각분할(Triangulation)[n각형을 n-2개의 삼각형으로 분할하기 = n+2각형을 n개의 삼각형으로 분할하기]

여러분은 n각형의 내각의 합을 아시나요?
예에에전에 얼핏 본 기억이 있지 않으신가요?
삼각형은 180도, 사각형은 360도... 어라? 규칙이 보이는 것도 같습니다?
네 바로 180(n-2)가 n각형의 내각의 합이죠!
그리고 이건 n각형을 n-2개의 (볼록다각형의 최소 단위인)삼각형으로 분할할 수 있으며, 이때 각 삼각형의 내각의 합은 무조건 180도가 되기때문에 간단하게 유도되는 식입니다.
다시말해 n+2각형을 n개의 삼각형으로 분해할 수 있다고 볼수도 있네요(n 위치만 조금 조정했습니다)
그렇다면, 여기서 문제!
삼각형으로 분할할 수 있는 경우의 수는 몇가지일까요!?
일단 삼각형은 단 한가지로밖에 분할이 안될 것 같고... 사각형은 어떻게 될까요?

사각형은

이렇게 두 가지 방법이 나올겁니다

그렇다면 오각형은요?

네, 요렇게 세가지 방법이 나오겠죠?
는 아닙니다!
잘 보시면 제일 왼쪽모양은 오른쪽에 사각형이 남아있고 위에서 봤듯이 이 사각형은 다시 두가지 방식으로 삼각형으로 나눌 수 있습니다.
제일 오른쪽 또한 마찬가지겠네요?
그래서 방법은 총 2+1+2로 다섯가지입니다.

어라..? 눈치빠르신 분들은 벌써 알아차리셨죠?
바로 카탈란수의 점화식 꼴이네요!!

쉽게 이해해보자면 두개의 점을 바닥에 두고 기준 변으로 잡은 뒤에 남은 n개 기준점에 순차적으로 삼각형을 그려보면서 그 뒤에 더 분할되는 부분이 있는지 보게 되는거죠!

기준점의 왼쪽과 오른쪽, 각각의 도형으로 분할하여 더 나눌 건덕지가 있는지 보는겁니다!

그래서 어떤 기준점 왼쪽에 아예 뭐가 없으면 $ C_0 $, 삼각형 하나 있으면(점 하나있으면) $ C_1 $ ... 이런식으로 보는거죠

그럼 육각형을 한전 카탈란수로 봐볼까요?

자, 제일 왼쪽그림(첫 번째그림)에서 삼각형 왼쪽은 점이 없죠?($ C_0 $), 그리고 오른쪽은 오각형, 그러니까 점이 3개 있습니다($ C_3 $)
= $ C_0C_3 $

두 번째그림은 왼쪽에 점 하나, 오른쪽에 점 두 개 있으니, $ C_1C_2 $네요

세 번째그림은 왼쪽에 점 두개, 오른쪽에 점 하나있으니 $ C_2C_1 $

네 번째그림은 왼쪽에 점 세개, 오른쪽에 점 0개 있으니 $ C_3C_0 $

모든 경우의 수를 합쳐주면 6각형(4+2각형)에서는
$ C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 $
즉, $ C_4 $군요

3. 결론

결국 n+2각형을 n개의 삼각형으로 나누는 경우의 수는 카탈란수의 점화식으로 나타나며, 결국 n번째 카탈란 수가 정답이 되겠네요!

의외로 신기하지 않나요? 뭔가 경우의수나 조합같지않은, 생뚱맞은 기하학 문제에서 이렇게 경우의 수와 카탈란 수열이 연관이 있다니요!

사실은 이거 진짜 쉽게 이해하기 어려운 부분입니다
그러나 이미 저번 포스팅에서 고생하며 구한 노력이 여기서 빛을 발하네요~

4. 미리니름

다음 번에는 아주 조금 어려운 주제를 들고와보겠습니다. 기대해주세요!

5. 여담

재미삼아 정 18각형으로 그려본 그림... 사실 원리만 알면 이렇게 n이 큰 다각형을 그릴 필요도 없지만요...