The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A046741 Triangle read by rows giving number of arrangements of k dumbbells on 2 X n grid (n >= 0, k >= 0). 25
 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, 114, 13, 1, 19, 137, 473, 815, 667, 223, 21, 1, 22, 191, 838, 1982, 2504, 1577, 424, 34, 1, 25, 254, 1356, 4115, 7191, 7018, 3538, 789, 55, 1, 28, 326, 2054, 7646, 17266, 23431 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 0,5 COMMENTS 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 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 LINKS Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15.2 (1974), 214-216. (Annotated scanned copy) R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216. H. Hosoya and A. Motoyama, 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, J. Math. Physics 26 (1985) 157-167. R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys., 11 (1970), 3095-3099. D. G. Rogers, An application of renewal sequences to the dimer problem, pp. 142-153 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979. Eric Weisstein's World of Mathematics, Ladder Graph Eric Weisstein's World of Mathematics, Matching-Generating Polynomial Donovan Young, The Number of Domino Matchings in the Game of Memory, J. Int. Seq., Vol. 21 (2018), Article 18.8.1. Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7. FORMULA From Emeric Deutsch, Dec 25 2004: (Start) 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. G.f.: (1-t*z)/(1 - z - 2*t*z - t*z^2 + t^3*z^3). (End) T(n,k) = T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-3,k-3). EXAMPLE 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 Triangle starts:   1;   1,  1;   1,  4,  2;   1,  7, 11,  3;   1, 10, 29, 26,  5; MAPLE 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 MATHEMATICA 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 *) 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 *) 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 *) PROG (Haskell) a046741 n k = a046741_tabl !! n !! k a046741_row n = a046741_tabl !! n a046741_tabl = [[1], [1, 1], [1, 4, 2]] ++ f [1] [1, 1] [1, 4, 2] where    f us vs ws = ys : f vs ws ys where      ys = zipWith (+) (zipWith (+) (ws ++ [0]) ([0] ++ map (* 2) ws))                       (zipWith (-) ([0] ++ vs ++ [0]) ([0, 0, 0] ++ us)) -- Reinhard Zumkeller, Jan 18 2014 CROSSREFS Diagonals give A002940, A002941, A002889. Row sums yield A030186. T(n,n) = Fibonacci(n+1) (A000045). Sequence in context: A249206 A245324 A039962 * A136249 A142147 A291977 Adjacent sequences:  A046738 A046739 A046740 * A046742 A046743 A046744 KEYWORD nonn,easy,nice,tabl AUTHOR EXTENSIONS More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000 Formula fixed by Reinhard Zumkeller, Jan 18 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 14 18:25 EDT 2021. Contains 342951 sequences. (Running on oeis4.)