A335964 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-3,k-1) + T(n-4,k-2) + delta(n,0)*delta(k,0), T(n,k<0) = T(n<k,k) = 0.

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 3, 2, 0, 0, 0, 1, 4, 4, 0, 0, 0, 0, 1, 5, 7, 2, 0, 0, 0, 0, 1, 6, 11, 6, 1, 0, 0, 0, 0, 1, 7, 16, 13, 3, 0, 0, 0, 0, 0, 1, 8, 22, 24, 9, 0, 0, 0, 0, 0, 0, 1, 9, 29, 40, 22, 3, 0, 0, 0, 0, 0, 0

Offset

0,12

Comments

T(n,k) is the number of tilings of an n-board (a board with dimensions n X 1) using k (1,1)-fence tiles and n-2k square tiles. A (w,g)-fence tile is composed of two tiles of width w separated by a gap of width g.

Sum of n-th row = A006498(n).

T(2*j+r,k) is the coefficient of x^k in (f(j,x))^(2-r)*(f(j+1,x))^r for r=0,1 where f(n,x) is one form of a Fibonacci polynomial defined by f(n+1,x) = f(n,x) + x*f(n-1,x) where f(0,x)=1 and f(n<0,x)=0. - Michael A. Allen, Oct 02 2021

Links

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

Kenneth Edwards and Michael A. Allen, New Combinatorial Interpretations of the Fibonacci Numbers Squared, Golden Rectangle Numbers, and Jacobsthal Numbers Using Two Types of Tile, arXiv:2009.04649 [math.CO], 2020.

Kenneth Edwards and Michael A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Int. Seq. 24 (2021) Article 21.3.8.

John Konvalina, On the number of combinations without unit separation., Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table I.

Formula

T(n,k) = A059259(n-k,k).

From Michael A. Allen, Oct 02 2021: (Start)

G.f.: 1/((1 + x^2*y)(1 - x - x^2*y)) in the sense that T(n,k) is the coefficient of x^n*y^k in the expansion of the g.f.

T(n,0) = 1.

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

T(n,2) = binomial(n-4,2) + n - 3 for n>3.

T(n,3) = binomial(n-6,3) + 2*binomial(n-5,2) for n>5.

T(4*m-3,2*m-2) = T(4*m-1,2*m-1) = m for m>0.

T(2*n+1,n-k) = A158909(n,k). (End)

T(n,k) = A348445(n-2,k) for n>1.

Example

Triangle begins:
  1;
  1,  0;
  1,  0,  0;
  1,  1,  0,  0;
  1,  2,  1,  0,  0;
  1,  3,  2,  0,  0,  0;
  1,  4,  4,  0,  0,  0,  0;
  1,  5,  7,  2,  0,  0,  0,  0;
  1,  6, 11,  6,  1,  0,  0,  0,  0;
  1,  7, 16, 13,  3,  0,  0,  0,  0,  0;
  1,  8, 22, 24,  9,  0,  0,  0,  0,  0,  0;
  1,  9, 29, 40, 22,  3,  0,  0,  0,  0,  0,  0;
  ...

Mathematica

T[n_, k_]:=If[n<k || k<0, 0, T[n-1, k] + T[n-3, k-1] + T[n-4, k-2] + KroneckerDelta[n, k, 0]]; Flatten[Table[T[n, k], {n, 0, 11}, {k, 0, n}]]
(* or via the g.f.: *)
Flatten[Table[CoefficientList[Series[1/((1+x^2*y)(1 - x - x^2*y)), {x, 0, 23}, {y, 0, 11}], {x, y}][[n+1, k+1]], {n, 0, 11}, {k, 0, n}]]

Prog

(PARI) TT(n, k) = if (n<k, 0, if((n==0) || (k==0), 1, if(k==n, (1+(-1)^n)/2, TT(n-1, k)+TT(n-1, k-1)))) \\ A059259
T(n, k) = TT(n-k, k);
\\ matrix(7, 7, n, k, T(n-1, k-1)) \\ Michel Marcus, Jul 18 2020

Crossrefs

Other triangles related to tiling using fences: A059259, A123521, A157897, A158909.

Cf. A006498, A011973, A348445.

Sequence in context: A076833 A071676 A319933 * A301570 A301567 A115363

Adjacent sequences: A335961 A335962 A335963 * A335965 A335966 A335967

Keyword

easy,nonn,tabl

Author

Michael A. Allen, Jul 01 2020

Status

approved