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,1

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

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

Table of n, a(n) for n=1..86.

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

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

Example

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;

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 *)

Prog

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

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

Sequence in context: A178305 A338621 A024327 * A361870 A124800 A247349

Adjacent sequences: A073041 A073042 A073043 * A073045 A073046 A073047

Keyword

nonn,tabl

Author

Roger Cuculière, Aug 24 2002

Extensions

More terms from Emeric Deutsch, Feb 01 2005

Status

approved