login
A367252
a(n) is the number of ways to tile an n X n square as explained in comments.
1
1, 0, 1, 4, 88, 3939, 534560, 185986304, 175655853776, 437789918351688, 2898697572048432368, 50698981110982431863735, 2342038257118692026082013568, 285250169294740386915765591840768, 91531011920509198679773321121428857296, 77312253225939431362091700178995800855209496
OFFSET
0,4
COMMENTS
Draw a Dyck path from (0,0) to (n,n) so the path always stays above the diagonal. Now section the square into horizontal rows of height one to the left of the path and tile these rows using 1 X 2 and 1 X 1 tiles. Similarly, section the part to the right of the path into columns with width one and tile these using 2 X 1 and 1 X 1 tiles. Furthermore, no 1 X 1 tiles are allowed in the bottom row.
FORMULA
a(n) == 1 (mod 2) <=> n in { A055010 }. - Alois P. Heinz, Nov 11 2023
MAPLE
b:= proc(x, y) option remember; (F->
`if`(x=0 and y=0, 1, `if`(x>0, b(x-1, y)*F(y-1), 0)+
`if`(y>x, b(x, y-1)*F(x+1), 0)))(combinat[fibonacci])
end:
a:= n-> b(n$2):
seq(a(n), n=0..15); # Alois P. Heinz, Nov 11 2023
MATHEMATICA
b[x_, y_] := b[x, y] = With[{F = Fibonacci},
If[x == 0 && y == 0, 1,
If[x > 0, b[x - 1, y]*F[y - 1], 0] +
If[y > x, b[x, y - 1]*F[x + 1], 0]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Nov 14 2023, after Alois P. Heinz *)
CROSSREFS
Special case of A003150.
Sequence in context: A303153 A154137 A154136 * A012830 A281180 A296465
KEYWORD
nonn
AUTHOR
Anna Tscharre, Nov 11 2023
STATUS
approved