Counting the Tilings (Posted on 2023-08-29)

	Submitted by Brian Smith
No Rating
Solution:	(Hide)
We can count the number of tilings recursively. To do that we need to know the set of 3x2n rectangle tilings which cannot be divided into two smaller rectangles. For 3x2 there are three rectangles: AA AA AB BB BC AB CC BC CC For larger n there are two 3x2n rectangles which cannot be broken into smaller 3x2k rectangles (n=3 illustrated): AAEEHH ACCFFI BCCFFI ADDGGI BDDGGI BBEEHH Let D(n) be our formula for the tilings of a 3x2n rectangle. By hand D(0)=1 is the degenerate case, and it is easy to construct D(1)=3 and D(2)=11. Then for larger n we can write this recursively as D(n) = 3*D(n-1) + 2*D(n-2) + 2*D(n-3) + ... + 2*D(1) + 2*D(0) We can simplify this a bit by evaluating D(n) - D(n-1) = [3*D(n-1) + 2*D(n-2) + 2*D(n-3) + ... + 2*D(1) + 2*D(0)] - [3*D(n-2) + 2*D(n-3) + ... + 2*D(1) + 2*D(0)] = 3*D(n-1) - D(n-2). Then D(n) simplifies to D(n) = 4*D(n-1) - D(n-2). This sequence starts 1,3,11,41,153,571,.... From here it is easy to use a spreadsheet to extend this to n=15, which is the 3x30 rectangle. D(15)=299303201. A quick search in the OEIS finds OEIS A001835 which is this sequence but with an offset index. The second comment calls out this problem: "Number of ways of packing a 3 X 2*(n-1) rectangle with dominoes."

	Subject	Author	Date
	re: Solution	Charlie	2023-08-29 13:28:47
	Solution	Jer	2023-08-29 11:19:51