login
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.
3

%I #49 Feb 06 2021 21:49:15

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

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

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

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

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

%D 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).

%D I. Goulden and D. Jackson, Combinatorial Enumeration, John Wiley and Sons, 1983, page 76.

%H B. E. Tenner, <a href="https://arxiv.org/abs/1811.00082">Tiling-based models of perimeter and area</a>, arXiv:1811.00082 [math.CO], 2018.

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

%F G.f.: G(t, z) = z*(2+2*z-t*z)/(1-t*z-z^2). - _Emeric Deutsch_, Feb 01 2005

%F T(n,k) = binomial(floor((n+k-1)/2),k) + binomial(floor((n+k-2)/2),k). - _Jeremy Dover_, Jun 07 2016

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

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

%e Triangle starts:

%e 2;

%e 2, 1;

%e 2, 2, 1;

%e 2, 3, 2, 1;

%e 2, 4, 4, 2, 1;

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

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

%o (PARI) T(n,k) = binomial((n+k-1)\2,k) + binomial((n+k-2)\2,k) \\ _Charles R Greathouse IV_, Jun 07 2016

%Y Row sums are the Fibonacci numbers (A000045).

%Y Cf. A046854.

%Y Weighted row sums 2*T(n,n) + 3*T(n,n-1) + 4*T(n,n-2) + ... give A320947. - _Bridget Tenner_, Oct 14 2019

%K nonn,tabl

%O 1,1

%A _Roger Cuculière_, Aug 24 2002

%E More terms from _Emeric Deutsch_, Feb 01 2005