피보나치 타일링(Fibonacci Tilings)

 

 한국에서는 2×N 타일링 문제로 많이 알려져있는 문제이다. 세로 길이 2, 가로 길이 n인 직사각형에 대하여 세로 2, 가로 1인 타일과 세로 1, 가로 2인 타일로 채우는 방법의 수를 구하는 문제이다. n=8인 경우의 예시는 다음과 같다. 

 

이 문제는 어떻게 풀어야하는가? 간단하게 점화식을 이용하여 풀 수 있는데, 제목에서 알 수 있듯이 결론적으로 이는 피보나치 수의 형태를 띄게 된다. 함께 보도록 하자.

 

가로 길이가 n일 때 채울 수 있는 총 방법의 가짓 수를 a_n이라고 한다면 다음과 같이 표현 될 수 있다.

 

여기서 중요한 점은 바로 "과연 모든 가짓 수를 표현 하는가?" 이다. 이 점을 잊지 않고 생각을 해보도록 하자. a_n-2의 다른 가짓 수 1개 즉, 세로로 2개가 세워지는 경우는 a_n-1에 의해서 커버가 되므로 겹치지 않기 위해 생략되었음을 알 수 있다. 또한, 어짜피 모든 경우의 수가 두 가지중 하나에서 시작하며 겹치지 않으므로 모든 가짓 수를 표현 하겠지만 그래도 검토해보고 싶다면 후자의 경우로 해서 그 뒤로 가로2짜리 타일이 오는 경우까지만 생각하면 되므로 즉, a_n-4 인 경우 까지 그려봐서 모두 커버하는지 검토해보면 되겠다. 따라서 결론적으로 채울 수 있는 총 가짓 수는 다음과 같이 표현할 수 있다.

 

 

 그렇다면 다음으로 고려해 볼 수 있는 부분이 있는데 "가능한 표현 식이 유일한가?"를 생각해 볼 수 있겠다. 결론 부터 말하자면 여러 가지 표현이 가능하다. 즉, 바꿔말해서 본인이 원하는 상황을 선택하되, 겹치지 않게 모든 가짓 수를 표현 할 수 있으면 되는 것이다. 만약 a_n-1을 고르고 싶지 않았다면, 다음과 같이 표현 할 수 있다. 

 

이는 곧 다음과 같은 상황을 고려한 것이다. a_n-3의 다른 가짓 수들 및 그 이하들은 아래의 그림들로 커버가 되기 때문에 겹치므로 생략된 것이다.

이 외에도 a_n = a_n-1+a_n-3+a_n-4 등등의 표현이 가능함을 알 수 있다. 따라서 우리는 이 부분을 통해 본인에게 적합한 표현 식을 이용하면 됨을 알 수 있다. 

 

 

 

 

하지만 이런 Top-down 방식으로 접근할 때, "정말로 모든 가짓 수가 피보나치 수를 따르는가?" 하는 의구심이 들 수도 있다. 혹시 무언가 놓친 부분이 있지 않을까? 또는 좀 더 정교한 접근방법은 없을까? 하는 생각이 든다면 다음과 같이 Bottom-up으로 접근해보자. 즉, 모든 가짓 수를 직접 계산해서 이 수가 Fibonacci number인지 비교해보면 되겠다.

 

필자는 well-known한 Binomial-Fibonacci identity 들중 하나인 다음과 같은 식을 이용하여 비교할 것이다.

 

 

0이상의 정수 l,m에 대하여 직사각형이 가로 길이 l을 갖는다고 하고, 가로2인 타일을 a, 가로1인 타일을 b라고 표현한다고 하자(단, a와 b의 갯수는 각각 0이상의 정수). 또한 세로와 상관없이 가로의 패턴에 따라 경우의 수가 결정되므로, 그렇다면 다음과 같이 경우를 나눌 수 있다.

 

i) l = 2m 일때

각 (a,b) 순서쌍에 대하여, 총 a+b개의 자리중에 a를 뽑거나 b를 뽑는 경우의 수가 곧 순서쌍에 대한 각 타일을 채우는 방법의 수이므로 총 타일을 채우는 방법의 수(N_l)은 다음과 같이 쓸 수 있다.

이를 정리하면 다음과 같다.

따라서 Binomial-Fibonacci identity에 따라 총 타일을 채우는 방법의 수는 Fibonacci number임을 알 수 있다.

 

 

ii) l = 2m+1 일때

마찬가지로 각 (a,b) 순서쌍에 대하여, 총 a+b개의 자리중에 a를 뽑거나 b를 뽑는 경우의 수가 곧 순서쌍에 대한 각 타일을 채우는 방법의 수이므로 총 타일을 채우는 방법의 수(N_l)은 다음과 같이 쓸 수 있다.

 

 

이를 정리하면 다음과 같다.

따라서 마찬가지로 Binomial-Fibonacci identity에 따라 총 타일을 채우는 방법의 수는 Fibonacci number임을 알 수 있다.

 

 

 

끝으로 정리하자면, 총 타일을 채우는 방법의 수 N_l은 General Fibonacci number의 sequence를 따름을 알 수 있다.

 

 

 

---

끝