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
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
Comments