A046741 Triangle read by rows giving number of arrangements of k dumbbells on 2 X n grid (n >= 0, k >= 0).

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabl

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

Examples

			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;
		

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.

Crossrefs

Diagonals give A002940, A002941, A002889.

Row sums yield A030186. T(n,n) = Fibonacci(n+1) (A000045).

Programs

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

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

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

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000

Formula fixed by Reinhard Zumkeller, Jan 18 2014