A276171 Irregular triangle T(n,k) read by rows: The number of tilings of the n X n board by 1 X 1 and k 3 X 3 squares, n >= 0, k >= 0.

1, 1, 1, 1, 1, 1, 4, 1, 9, 1, 16, 30, 12, 1, 1, 25, 132, 200, 79, 1, 36, 360, 1232, 1246, 1, 49, 780, 5048, 13211, 11984, 4526, 758, 51, 1, 1, 64, 1470, 15468, 78851, 193672, 234394, 139188, 37760, 3600, 1, 81, 2520, 38972, 324721, 1490562, 3761236, 5052890, 3305328, 807648

Offset

0,7

Comments

The number of monomers (1 X 1 squares) is n^2 - 9*k.

Row lengths are triplicated A002522.

Links

Alois P. Heinz, Rows n = 0..24, flattened

R. J. Mathar, Tiling n X m rectangles with 1 X 1 and s X s squares, arXiv:1609.03964 [math.CO] (2016).

Formula

T(n,0) = 1.

T(n,1) = (n-2)^2, n >= 2.

From Alois P. Heinz, Sep 27 2016: (Start)

T(n,2) = (n-3)*(n-4)*(n-5)*(n+4)/2 for n > 2.

T(n,3) = (n^6 - 12*n^5 - 15*n^4 + 620*n^3 - 1234*n^2 - 7616*n + 22368)/6 for n > 5. (End)

Example

The triangle starts in row n=0 with columns k=0,1,...:
  1;
  1;
  1;
  1,  1;
  1,  4;
  1,  9;
  1, 16,  30,   12,     1;
  1, 25, 132,  200,    79;
  1, 36, 360, 1232,  1246;
  1, 49, 780, 5048, 13211, 11984, 4526, 758, 51, 1;

Maple

b:= proc(n, l) option remember; local k, m; m:=min(l[]);
      if n<3 then 1
    elif m>0 then b(n-m, map(x->x-m, l))
    else for k while l[k]>0 do od; b(n, subsop(k=1, l))+
         expand(`if`(k+1<nops(l) and l[k+1..k+2]=[0$2],
              b(n, subsop(k=3, k+1=3, k+2=3, l))*x, 0))
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [0$n])):
seq(T(n), n=0..12);  # Alois P. Heinz, Sep 27 2016

Mathematica

b[n_, l_] := b[n, l] = Module[{ k, m}, m = Min[l]; Which[n < 3, 1, m > 0, b[n - m, l - m],  True, k = 1; While[l[[k]] > 0, k++]; b[n, ReplacePart[ l, k -> 1]] + Expand[If[k + 1 < Length[l] && l[[k+1 ;; k+2]] == {0, 0}, b[n, ReplacePart[l, {k -> 3, k+1 -> 3, k+2 -> 3}]]*x, 0]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]} ] ][b[n, Table[0, n]]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

Crossrefs

Cf. A002522, A140304 (row sums), A193580 (1 X 1 and 2 X 2 squares).

Sequence in context: A080103 A091419 A326582 * A306603 A181859 A218972

Adjacent sequences: A276168 A276169 A276170 * A276172 A276173 A276174

Keyword

nonn,tabf

Author

R. J. Mathar, Aug 23 2016

Status

approved