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

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

Author

Gary W. Adamson, Mar 08 2009

Keywords

• nonn
• tabl

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

Examples

			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.
		

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.

Crossrefs

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

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

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

Programs

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

Mathematica

T[n_,k_]:= If[nMichael A. Allen, Apr 28 2019 *)

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

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

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)

Extensions

Name clarified by Michael A. Allen, Apr 28 2019

Definition improved by Michael A. Allen, Mar 11 2021

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.