[정수론] 확산형 도미노와 경우의 수

도미노를 삼각수(triangle number) 에서와 같이 배치한다.

예.
ㅠ

위에서 부터 1층, 2층, 3층 , ... 순으로 부르기로 하고,  총 층수를 n 으로 나타내자.


도미노가 쓰러지는 규칙은 다음과 같다.

----------------------------------------------------------------------------------------
1. 모든 도미노는 건드려질 경우, 넘어질 수 도 있고, 안넘어질 수 도 있다.  -_- ;;;
     ( 1층 시작 도미노는 손으로 건드리되, 이것도 안넘어 갈 수 있다. )
2. 안건드려 질 경우에는 안넘어진다.
-----------------------------------------------------------------------------------------

주어진 n 에 대해, 모든 가능한 서로다른 상황의 가지수를 Dn 이라 하자.

n = 1 인 경우, 도미노는 1개 밖에 없고, 따라서 (1) 넘어지는 상황과  (2) 넘어지지 않는 상황의 2가지 경우가 가능하므로, D1 = 2 가 된다.

n = 2 인 경우, 도미노는 3개가 되고, (1)  1층의 도미노가 넘어지지 않는 경우, (2) 1층의 도미노가 넘어졌으나 2층의 도미노가 하나도 안넘어간 경우, (3) 두개중 왼쪽것만 넘어간 경우, (4) 오른쪽것만 넘어간 경우, (5) 둘다 넘어간 경우가 가능하므로, D2 = 5  가 된다.

Dn 의 일반항을 구해라.