In how many ways can you cover a 2xN chessboard using 1x2 and 2x2 dominoes?

Using 1x2 dominoes the answer is just the N+1 term of the Fibonacci sequence, but I don't know what to do when you include 2x2 dominoes.|||I didn't know how to solve this, so I wrote a computer program.


It produced these numbers for N = 1,2,3,4, etc:


1,3,5,11,21,43,85,171,341,683,1365,273鈥?5461,10923,21845,43691


This is a well known sequence called the Jacobsthal Numbers


http://research.att.com/~njas/sequences/鈥?/a>





It says on that page that it is also (among many other things)


Number of ways to tile a 3 X (n-1) rectangle with 1 X 1 and 2 X 2 square tiles.


But I could not find anywhere which associated it with this problem.





From the numbers it is evident that each F(N) is 2 * the previous 卤 1 (alternating between + and -).





For a formula, I found this information:





On this page: http://mathforum.org/library/drmath/view鈥?/a>


It gives u(n+2) - u(n+1) - 2u(n) = 0 as a recurrence relation and


u(n) = (-1/3)(-1)^n + (1/3)(2^n)


as the closed form.





One can also find the same thing as (2^(n+1) + (-1)^n) / 3


in Knuth 5.3.1 equation 13, in conjunction with minimum comparison sorting.





Here is some insight into the problem, but not a complete solution:





Start with all the arrangements for 2 x N.


To make it 2 x (N+1) you can:


add a vertical 1x2 at the front or the back


You can remove a vertical 1x2 at the front or the back


and replace it by 2 horizontal 1x2's or a 2x2.


Unfortunately, there will be duplications among all those,


and you don't know how many have a vertical domino on an end.





UPDATE: I received the following explanation via email from Maximilian.





It is a better way of saying what I tried to say above,


and completes the solution.





Let 2x1 refer to a domino laid parallel to the long side of the chessboard (horizontal), and 1x2 be one the other way (verical).





From a 2 x (n-1) tiling, we can add two 2x1's or one 2x2.


From a 2 x (n) tiling, we can add a 1x2.





2 x F(n-1) + F(n) is the recurrence relation for the Josephthal sequence, and we are done.


(Thanks Maximilian.)|||It is correct that the answer is the Jacobsthal sequence.





To see it, let a(N) be that number. Clearly a(1)=1 and a(2)=3.


Moreover we have a(N+1) = a(N) + a(N-1)*2, where the first term arises from adding a 1x2 domino to the 2xN tiling, and the second term arises from adding either a square, or 2 1x2 dominoes in "longitudinal" direction to a 2x(N-1) tiling.





Or otherwise said, a 2xN tiling has either its last piece being a


domino in "transverse" direction, in which case removing it yields a 2x(N-1) tiling, or the last piece is a square or 2 dominoes in longitudinal direction, in which case removal will yield a 2x(N-2) tiling.





Thus we have the recurrent equation defining the Jacobsthal sequence, and since we start with 1,3,... it is the same sequence, with index shifted by one, a(n) = A001045(n+1), n%26gt;0.


(We might add a(0)=1 considering the empty tiling as the only possibility of tiling the 2x0 rectangle.)


|||2xN / 2x2











.