A367252 a(n) is the number of ways to tile an n X n square as explained in comments.

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.

Links

Table of n, a(n) for n=0..15.

Anna Tscharre, A possible 6 X 6 tiling

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.

Cf. A055010, A307082.

Sequence in context: A303153 A154137 A154136 * A012830 A281180 A296465

Adjacent sequences: A367249 A367250 A367251 * A367253 A367254 A367255

Keyword

nonn

Author

Anna Tscharre, Nov 11 2023

Status

approved