A335964 - OEIS

%I #44 Apr 25 2022 08:07:31

%S 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,

%T 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,

%U 1,9,29,40,22,3,0,0,0,0,0,0

%N 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.

%C 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.

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

%C 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

%H Kenneth Edwards and Michael A. Allen, <a href="https://arxiv.org/abs/2009.04649">New Combinatorial Interpretations of the Fibonacci Numbers Squared, Golden Rectangle Numbers, and Jacobsthal Numbers Using Two Types of Tile</a>, arXiv:2009.04649 [math.CO], 2020.

%H Kenneth Edwards and Michael A. Allen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Allen/edwards2.html">New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile</a>, J. Int. Seq. 24 (2021) Article 21.3.8.

%H John Konvalina, <a href="https://doi.org/10.1016/0097-3165(81)90006-6">On the number of combinations without unit separation.</a>, Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table I.

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

%F From _Michael A. Allen_, Oct 02 2021: (Start)

%F 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.

%F T(n,0) = 1.

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

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

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

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

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

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

%e Triangle begins:

%e   1;

%e   1,  0;

%e   1,  0,  0;

%e   1,  1,  0,  0;

%e   1,  2,  1,  0,  0;

%e   1,  3,  2,  0,  0,  0;

%e   1,  4,  4,  0,  0,  0,  0;

%e   1,  5,  7,  2,  0,  0,  0,  0;

%e   1,  6, 11,  6,  1,  0,  0,  0,  0;

%e   1,  7, 16, 13,  3,  0,  0,  0,  0,  0;

%e   1,  8, 22, 24,  9,  0,  0,  0,  0,  0,  0;

%e   1,  9, 29, 40, 22,  3,  0,  0,  0,  0,  0,  0;

%e   ...

%t 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}]]

%t (* or via the g.f.: *)

%t 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}]]

%o (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

%o T(n,k) = TT(n-k,k);

%o \\ matrix(7,7,n,k, T(n-1,k-1)) \\ _Michel Marcus_, Jul 18 2020

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

%Y Cf. A006498, A011973, A348445.

%K easy,nonn,tabl

%O 0,12

%A _Michael A. Allen_, Jul 01 2020