A350834 Number of ways to tile an n X n right triangle with squares and dominoes, where vertical dominoes are only allowed in the largest vertical column.

1, 1, 3, 11, 73, 749, 12657, 343693, 15140923, 1078147567, 124268659473, 23172219304577, 6991754237772409, 3413365649747365697, 2696315730346059254139, 3446235324323962173174283, 7127008624714819485698797681, 23848280807640171362927751869341

Offset

0,3

Comments

This is the third column in A229556.

Links

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

Formula

a(n) = Fibonacci(n+1)*a(n-1) + Fibonacci(n)*Fibonacci(n-1)*a(n-2).

a(n) = P(n+1) + Sum_{i=2..n} a(i-1)*Fibonacci(i-1)*Fibonacci(n-(i-1))*P(n)/P(i), where P(n) = A003266(n) the product of the first n Fibonacci numbers. - Greg Dresden and Tianle Tina Yao, Jul 03 2022

Example

Here is one of the 73 tilings for the n=4 case. Note that vertical dominoes are only allowed in the "first" column.
.  _
  | |_
  |_|_|_
  | |___|_
  |_|_|___|

Mathematica

T[0] = 1; T[1] = 1; T[n_] := T[n] = Fibonacci[n + 1] T[n - 1] + (Fibonacci[n] Fibonacci[n - 1]) T[n - 2]; Table[T[n], {n, 0, 20}]

Crossrefs

Cf. A229556, A000045, A003266.

Sequence in context: A127716 A035378 A258387 * A054461 A342433 A374533

Adjacent sequences: A350831 A350832 A350833 * A350835 A350836 A350837

Keyword

nonn

Author

Greg Dresden and Tianle Tina Yao, Jun 12 2022

Status

approved