login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

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

N. J. A. Sloane

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 24 03:51 EDT 2019. Contains 326260 sequences. (Running on oeis4.)