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

1, 1, 0, 1, 1, 0, 1, 2, 0, 1, 1, 3, 1, 2, 0, 1, 4, 3, 3, 2, 0, 1, 5, 6, 5, 6, 0, 1, 1, 6, 10, 9, 12, 3, 3, 0, 1, 7, 15, 16, 21, 12, 6, 3, 0, 1, 8, 21, 27, 35, 30, 14, 12, 0, 1, 1, 9, 28, 43, 57, 61, 35, 30, 6, 4, 0, 1, 10, 36, 65, 91, 111, 81, 65, 30, 10, 4, 0, 1, 11, 45, 94, 142, 189, 169, 135, 90, 30, 20, 0, 1

Offset

0,8

Comments

T(n, k) is the number of tilings of an n-board that use k (1/2, 1)-fences and n-k squares. A (1/2, 1)-fence is a tile composed of two pieces of width 1/2 separated by a gap of width 1. (Result proved in paper by K. Edwards - see the links section.) - Michael A. Allen, Apr 28 2019

T(n, k) is the (n, n-k)-th entry in the (1/(1-x^3), x*(1+x)/(1-x^3)) Riordan array. - Michael A. Allen, Mar 11 2021

Links

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fib. Q., 46/47 (2008/2009), 18-25.

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.

Formula

T(n,k) = T(n-1,k) + T(n-2,k-1) + T(n-3,k-3) + delta(n,0)*delta(k,0), T(n,k<0) = T(n<k,k) = 0.

Sum_{k=0..n} T(n, k) = A000073(n+2). - Reinhard Zumkeller, Jun 25 2009

From G. C. Greubel, Sep 01 2022: (Start)

T(n, k) = T(n-1, k) + T(n-2, k-1) + T(n-3, k-3), with T(n, 0) = 1.

T(n, n) = A079978(n).

T(n, n-1) = A087508(n), n >= 1.

T(n, 1) = A001477(n-1).

T(n, 2) = A161680(n-2).

Sum_{k=0..floor(n/2)} T(n-k, k) = A120415(n). (End)

Example

First few rows of the triangle are:
  1;
  1,  0;
  1,  1,  0;
  1,  2,  0,  1;
  1,  3,  1,  2,  0;
  1,  4,  3,  3,  2,  0;
  1,  5,  6,  5,  6,  0,  1;
  1,  6, 10,  9, 12,  3,  3,  0;
  1,  7, 15, 16, 21, 12,  6,  3,  0;
  1,  8, 21, 27, 35, 30, 14, 12,  0,  1;
  ...
T(9,3) = 27 = T(8,3) + T(7,2) + T(6,0) = 16 + 10 + 1.

Mathematica

T[n_, k_]:= If[n<k || k<0, 0, T[n-1, k]+T[n-2, k-1]+T[n-3, k-3]+KroneckerDelta[n, k, 0]];
Flatten[Table[T[n, k], {n, 0, 14}, {k, 0, n}]] (* Michael A. Allen, Apr 28 2019 *)

Prog

(Magma)
function T(n, k) // T = A157897
  if k lt 0 or k gt n then return 0;
  elif k eq 0 then return 1;
  else return T(n-1, k) + T(n-2, k-1) + T(n-3, k-3);
  end if; return T;
end function;
[T(n, k): k in [0..n], n in [0..14]]; // G. C. Greubel, Sep 01 2022
(SageMath)
def T(n, k): # T = A157897
    if (k<0 or k>n): return 0
    elif (k==0): return 1
    else: return T(n-1, k) + T(n-2, k-1) + T(n-3, k-3)
flatten([[T(n, k) for k in (0..n)] for n in (0..14)]) # G. C. Greubel, Sep 01 2022

Crossrefs

Cf. A000073 (row sums), A006498, A120415.

Cf. A001477, A079978, A087508, A120415, A161680.

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

Sequence in context: A319854 A124035 A204184 * A213910 A288002 A140129

Adjacent sequences: A157894 A157895 A157896 * A157898 A157899 A157900

Keyword

nonn,tabl

Author

Gary W. Adamson, Mar 08 2009

Extensions

Name clarified by Michael A. Allen, Apr 28 2019

Definition improved by Michael A. Allen, Mar 11 2021

Status

approved