A073044 Triangle read by rows: T(n,k) (n >= 1, n-1 >= k >= 0) = number of n-sequences of 0's and 1's with no pair of adjacent 0's and exactly k pairs of adjacent 1's.

2, 2, 1, 2, 2, 1, 2, 3, 2, 1, 2, 4, 4, 2, 1, 2, 5, 6, 5, 2, 1, 2, 6, 9, 8, 6, 2, 1, 2, 7, 12, 14, 10, 7, 2, 1, 2, 8, 16, 20, 20, 12, 8, 2, 1, 2, 9, 20, 30, 30, 27, 14, 9, 2, 1, 2, 10, 25, 40, 50, 42, 35, 16, 10, 2, 1, 2, 11, 30, 55, 70, 77, 56, 44, 18, 11, 2, 1, 2, 12, 36, 70, 105, 112, 112, 72

Offset: 1

Author

Roger Cuculière, Aug 24 2002

Keywords

• nonn
• tabl

Comments

T(n,k) is the number of domino tilings of 2 X (n+1) rectangles that have n+2-k perimeter dominoes. - Bridget Tenner, Oct 14 2019

Examples

			T(5,2)=4 because the sequences of length 5 with 2 pairs 11 are 11101, 11011,10111, 01110. Also the 2 X (5+1) rectangle has 4 domino tilings with 5+2-2 perimeter dominoes. - _Bridget Tenner_, Oct 14 2019
Triangle starts:
  2;
  2, 1;
  2, 2, 1;
  2, 3, 2, 1;
  2, 4, 4, 2, 1;
		

References

• S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 67-68).
• I. Goulden and D. Jackson, Combinatorial Enumeration, John Wiley and Sons, 1983, page 76.

Links

• B. E. Tenner, Tiling-based models of perimeter and area, arXiv:1811.00082 [math.CO], 2018.

Crossrefs

Row sums are the Fibonacci numbers (A000045).

Cf. A046854.

Weighted row sums 2*T(n,n) + 3*T(n,n-1) + 4*T(n,n-2) + ... give A320947. - Bridget Tenner, Oct 14 2019

Programs

Maple

G:=z*(2+2*z-t*z)/(1-t*z-z^2):Gser:=simplify(series(G,z=0,17)):for n from 1 to 15 do P[n]:=sort(coeff(Gser,z^n)) od:for n from 1 to 13 do seq(coeff(t*P[n],t^k),k=1..n) od;# yields sequence in triangular form

Mathematica

nn = 15; f[list_] := Select[list, # > 0 &]; Map[f, Drop[CoefficientList[Series[(1 + x) (1 + x - y x)/(1 - y x - x^2), {x, 0, nn}], {x,y}], 1]] //Flatten (* Geoffrey Critzer, Mar 05 2012 *)

PARI

T(n,k) = binomial((n+k-1)\2,k) + binomial((n+k-2)\2,k) \\ Charles R Greathouse IV, Jun 07 2016

Formula

Recurrence: T(n, k) = T(n-1, k-1) + T(n-2, k).

G.f.: G(t, z) = z*(2+2*z-t*z)/(1-t*z-z^2). - Emeric Deutsch, Feb 01 2005

T(n,k) = binomial(floor((n+k-1)/2),k) + binomial(floor((n+k-2)/2),k). - Jeremy Dover, Jun 07 2016

T(n,k) = A046854(n-1,k) + A046854(n-2,k), where A046854 is extended so that A046854(-1,0) = 1. - Jeremy Dover, Jun 07 2016

Extensions

More terms from Emeric Deutsch, Feb 01 2005