|
%I #20 Jun 13 2015 00:54:40
%S 1,3,26,163,1125,7546,51055,344525,2326760,15709977,106079739,
%T 716273960,4836475953,32657123299,220509407586,1488936665619,
%U 10053686907525,67885102598386,458377829683919,3095086053853821,20898824215523616
%N Number of ways to tile a fixed 3 X n square grid with 1 X 1, 2 X 2, and 1 X 2 tiles.
%H Andrew Woods, <a href="/A226351/b226351.txt">Table of n, a(n) for n = 0..100</a>
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,19,1,-26,1,6).
%F Recurrence: a(n) = 4*a(n-1)+19*a(n-2)+a(n-3)-26*a(n-4)+a(n-5)+6*a(n-6) for n>5, a(0)=1, a(1)=3, a(2)=26, a(3)=163, a(4)=1125, a(5)=7546.
%F G.f.: (1-x-5*x^2+x^3+2*x^4)/(1-4*x-19*x^2-x^3+26*x^4-x^5-6*x^6).
%t LinearRecurrence[{4, 19, 1, -26, 1, 6}, {1, 3, 26, 163, 1125, 7546}, 21] (* _T. D. Noe_, Jun 04 2013 *)
%o (Python)
%o # Depth-first search on 3 rows and n columns
%o # Produces "count" and the list "result[]"
%o # Omit the 2nd-last line if memory runs low
%o n=5; rows=3
%o count=0; result=[]
%o def f(b,row=0,col=-1):
%o ..global count
%o ..for i in range(row,len(b)):
%o ....for j in range((col+1 if i==row else 0),len(b[0])):
%o ......if b[i][j]==' ':
%o ........if i<len(b)-1:
%o ..........if b[i+1][j]==' ':
%o ............f(b[:i]+[b[i][:j]+'^'+b[i][j+1:],b[i+1][:j]+'V'+b[i+1][j+1:]]+b[i+2:],i,j)
%o ............if j<len(b[0])-1:
%o ..............if b[i][j+1]==' ' and b[i+1][j:j+2]==' ':
%o ................f(b[:i]+[b[i][:j]+'/\\'+b[i][j+2:],b[i+1][:j]+'\\/'+b[i+1][j+2:]]+b[i+2:],i,j)
%o ........if j<len(b[0])-1:
%o ..........if b[i][j+1]==' ':
%o ............f(b[:i]+[b[i][:j]+'<>'+b[i][j+2:]]+b[i+1:],i,j)
%o ..count+=1
%o ..result.append(b) # omit this line
%o f([' '*n]*rows); print(count)
%Y Cf. A226348.
%K nonn,easy
%O 0,2
%A _Andrew Woods_, Jun 04 2013
| 