문제 링크

문제 1

크기 $n$ 의 크리스마스 트리는 총 몇 가지가 있을까? 꼭짓점들을 모두 고정하고 연결 방법만 달리한다고 가정하자.

답안 1

크기 $n$ 의 크리스마스 트리의 경우의 수를 구해보자.

마지막 줄을 제외한 크기 $n-1$ 의 크리스마스가 있을 때,

$n-1$ 번째 행의 $n-1$ 개의 점과 $n$ 번째 행의 $n$ 개의 점을 적절히 연결하는 방법의 수를 생각하자.

위의 $n-1$ 개 점은 반드시 아래에 있는 점과 연결되어야하는 것은 아님을 고려하자.

아래의 $n$ 개 점은 반드시 위에 있는 점(양 끝의 점을 제외한 나머지 각 점마다 왼쪽, 오른쪽 2개의 선택지가 있음) 중에서 정확히 1개의 점과 연결되어야 한다. 따라서 $n$ 번째 행의 $n$ 개 점들 중에서 양 끝의 점은 선택지가 1개 뿐이고 나머지 $n-1$ **개의 점**은 자신 기준으로 왼쪽 점과 오른쪽 점 중에서 1개를 결정해야하는 2가지 선택지가 발생한다.

따라서 $a_{n} = 2^{n-2} \cdot a_{n-1}$이 성립하고 $a_{1} = a_{2} = 1$ 이므로

$a_{n} \\= 2^{n-2} \cdot a_{n-1} \\= 2^{n-2} \cdot 2^{n-3} \cdots 2^{1} \cdot a_2 \\= 2^{(n-2) + (n-3) + \cdots + 1} \\=2^{\frac{(n-2)(n-1)}{2}}$

문제 2

다음의 4번 조건을 추가로 만족하는 크리스마스 트리를 안정적인 크리스마스 트리라고 하자.

(4) 변 1개로만 연결된 꼭짓점들은 전부 맨 아래층에만 있다.

그렇다면 크기 $n$ 의 안정적인 크리스마스 트리는 총 몇 가지가 있을까? 1번 문제와 마찬가지로 꼭짓점들을 고정하고 연결 방법만 달리한다고 하자.

답안 2

답안 1의 아이디어를 참고하자.

문제 2가 문제 1과 다른 점은 $n-1$ 번째 행의 점도 반드시 $n$ 번째 행과 연결되어야한다는 사실이다.