%I #56 Mar 18 2020 11:14:15
%S 1,1,1,1,4,2,1,7,11,3,1,10,29,26,5,1,13,56,94,56,8,1,16,92,234,263,
%T 114,13,1,19,137,473,815,667,223,21,1,22,191,838,1982,2504,1577,424,
%U 34,1,25,254,1356,4115,7191,7018,3538,789,55,1,28,326,2054,7646,17266,23431
%N Triangle read by rows giving number of arrangements of k dumbbells on 2 X n grid (n >= 0, k >= 0).
%C Equivalently, T(n,k) is the number of k-matchings in the ladder graph L_n = P_2 X P_n. - _Emeric Deutsch_, Dec 25 2004
%C In other words, triangle of number of monomer-dimer tilings on (2,n)-block with k dimers. If z marks the size of the block and t marks the dimers, then it is easy to see that the g.f. for indecomposable tilings, i.e., those that cannot be split vertically into smaller tilings, is g = (1+t)*z + t^2*z^2 + 2*t*z^2 + 2*t^2*z^3 + 2*t^3*z^4 + ... = (1+t)*z + t^2*z^2 + 2*t*z^2/(1-t*z); then the g.f. is 1/(1-g) = (1-t*z)/(1 - z - 2*t*z - t*z^2 + t^3*z^3) (see eq. (4) of the Grimson reference). From this the recurrence of the McQuistan & Lichtman reference follows at once. - _Emeric Deutsch_, Oct 16 2006
%H Reinhard Zumkeller, <a href="/A046741/b046741.txt">Rows n = 0..125 of triangle, flattened</a>
%H R. C. Grimson, <a href="/A002889/a002889.pdf">Exact formulas for 2 x n arrays of dumbbells</a>, J. Math. Phys., 15.2 (1974), 214-216. (Annotated scanned copy)
%H R. C. Grimson, <a href="http://dx.doi.org/10.1063/1.1666624">Exact formulas for 2 x n arrays of dumbbells</a>, J. Math. Phys., 15 (1974), 214-216.
%H H. Hosoya and A. Motoyama, <a href="http://dx.doi.org/10.1063/1.526778">An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices</a>, J. Math. Physics 26 (1985) 157-167.
%H R. B. McQuistan and S. J. Lichtman, <a href="http://dx.doi.org/10.1063/1.1665098">Exact recursion relation for 2 x N arrays of dumbbells</a>, J. Math. Phys., 11 (1970), 3095-3099.
%H D. G. Rogers, <a href="http://dx.doi.org/10.1007/BFb0102693">An application of renewal sequences to the dimer problem</a>, pp. 142-153 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching-GeneratingPolynomial.html">Matching-Generating Polynomial</a>
%H Donovan Young, <a href="https://www.emis.de/journals/JIS/VOL21/Young/young2.html">The Number of Domino Matchings in the Game of Memory</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.1.
%H Donovan Young, <a href="https://arxiv.org/abs/1905.13165">Generating Functions for Domino Matchings in the 2 * k Game of Memory</a>, arXiv:1905.13165 [math.CO], 2019. Also in <a href="https://www.emis.de/journals/JIS/VOL22/Young/young13.html">J. Int. Seq.</a>, Vol. 22 (2019), Article 19.8.7.
%F From _Emeric Deutsch_, Dec 25 2004: (Start)
%F The row generating polynomials P[n] satisfy P[n] = (1 + 2*t)*P[n-1] + t*P[n-2] - t^3*P[n-3] with P[0] = 1, P[1] = 1+t, P[2] = 1 + 4*t + 2*t^2.
%F G.f.: (1-t*z)/(1 - z - 2*t*z - t*z^2 + t^3*z^3). (End)
%F T(n,k) = T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-3,k-3).
%e T(3, 2)=11 because in the 2 X 3 grid with vertex set {O(0, 0), A(1, 0), B(2, 0), C(2, 1), D(1, 1), E(0, 1)} and edge set {OA, AB, ED, DC, UE, AD, BC} we have the following eleven 2-matchings: {OA, BC}, {OA, DC}, {OA, ED}, {AB, DC}, {AB, ED}, {AB, OE}, {BC, AD}, {BC, ED}, {BC, OA}, {BC, OE} and {DC, OE}. - _Emeric Deutsch_, Dec 25 2004
%e Triangle starts:
%e 1;
%e 1, 1;
%e 1, 4, 2;
%e 1, 7, 11, 3;
%e 1, 10, 29, 26, 5;
%p F[0]:=1:F[1]:=1+t:F[2]:=1+4*t+2*t^2:for n from 3 to 10 do F[n]:=sort(expand((1+2*t)*F[n-1]+t*F[n-2]-t^3*F[n-3])) od: for n from 0 to 10 do seq(coeff(t*F[n],t^k),k=1..n+1) od;# yields sequence in triangular form - _Emeric Deutsch_
%t p[n_] := p[n] = (1 + 2t) p[n-1] + t*p[n-2] - t^3*p[n-3]; p[0] = 1; p[1] = 1+t; p[2] = 1 + 4t + 2t^2; Flatten[Table[CoefficientList[Series[p[n], {t, 0, n}], t], {n, 0, 10}]][[;; 62]] (* _Jean-François Alcover_, Jul 13 2011, after _Emeric Deutsch_ *)
%t CoefficientList[LinearRecurrence[{1 + 2 x, x, -x^3}, {1 + x, 1 + 4 x + 2 x^2, 1 + 7 x + 11 x^2 + 3 x^3}, {0, 10}], x] // Flatten (* _Eric W. Weisstein_, Apr 03 2018 *)
%t CoefficientList[CoefficientList[Series[-(1 + x z) (-1 - x + x^2 z)/(1 - z - 2 x z - x z^2 + x^3 z^3), {z, 0, 10}], z], x] // Flatten (* _Eric W. Weisstein_, Apr 03 2018 *)
%o (Haskell)
%o a046741 n k = a046741_tabl !! n !! k
%o a046741_row n = a046741_tabl !! n
%o a046741_tabl = [[1], [1, 1], [1, 4, 2]] ++ f [1] [1, 1] [1, 4, 2] where
%o f us vs ws = ys : f vs ws ys where
%o ys = zipWith (+) (zipWith (+) (ws ++ [0]) ([0] ++ map (* 2) ws))
%o (zipWith (-) ([0] ++ vs ++ [0]) ([0, 0, 0] ++ us))
%o -- _Reinhard Zumkeller_, Jan 18 2014
%Y Diagonals give A002940, A002941, A002889.
%Y Row sums yield A030186. T(n,n) = Fibonacci(n+1) (A000045).
%K nonn,easy,nice,tabl
%O 0,5
%A _N. J. A. Sloane_
%E More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000
%E Formula fixed by _Reinhard Zumkeller_, Jan 18 2014