Consider a regular n-gon. We divide it by nonintersecting diagonals into triangles in such a way that each of the resulting triangles has at least one side in common with the original n-gon. How many such triangulations are there?

추가 조건: n-gon은 각 점을 정점으로 가짐(=회전해서 같은 모양도 다르게 취급)


그래프 문제인데... 그래프 기초만 배우고 나온 과제 수듄이;;


일단 변 하나 잡고 나머지 모든 점에 한번씩 쏴서 삼각형 만들고 그때 나오는 두 다각형(인접한 점이면 선분)에서 나오는 경우의 수를 곱하는걸 생각했는데 그럼 least one side in common with the original n-gon 조건때문에 점화식도 엄청 꼬이고 올바른 풀이 방향도 아닐거같아서....

아오 진짜 어케해야할지 모르겠다