A033511 -id:A033511 - cp's OEIS frontend

A210662 Triangle read by rows: T(n,k) (1 <= k <= n) = number of monomer-dimer tilings of an n X k board.

1, 2, 7, 3, 22, 131, 5, 71, 823, 10012, 8, 228, 5096, 120465, 2810694, 13, 733, 31687, 1453535, 65805403, 2989126727, 21, 2356, 196785, 17525619, 1539222016, 135658637925, 11945257052321, 34, 7573, 1222550, 211351945, 36012826776, 6158217253688, 1052091957273408, 179788343101980135

Offset: 1

N. J. A. Sloane, Mar 28 2012

The triangle is half of a symmetric square array, since T(n,k) = T(k,n).
Equivalently, ways of paving n X k grid cells using only singletons and dominoes. Also, the number of tilings of an n X k chessboard with the two polyominoes (0,0) and (0,0)+(0,1).
Also, matchings of the n X k grid graph. The n X k grid graph is also denoted P_m X P_n. For k=2, this is called the ladder graph L_n.
In statistical mechanics, this is a special case of the Monomer-Dimer Problem, which deals with monomer-dimer coverings of a finite patch of a lattice.
Right hand diagonal is A028420. Left hand diagonal is A000045.
Taken as a full square array, columns (and rows) 1-7 respectively match A000045(n+1), A030186, A033506(n-1), A033507(n-1), A033508(n-1), A033509(n-1), A033510(n-1), and have recurrences of order 2 3 6 9 20 36 72. - R. H. Hardin, Dec 11 2012

			Triangle begins:
1
2 7
3 22 131
5 71 823 10012
8 228 5096 120465 2810694
13 733 31687 1453535 65805403 2989126727
21 2356 196785 17525619 1539222016 135658637925 11945257052321
34 7573 1222550 211351945 36012826776 6158217253688 1052091957273408 179788343101980135...
The 7 matchings of the P(2) X P(2)-graph are:
  . .   .-.   . .   . .   . .   . .   .-.
              |       |         | |
  . .   . .   . .   . .   .-.   . .   .-.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Rows n = 1..18, flattened
Ahrens, J. H. Paving the chessboard. J. Combin. Theory Ser. A 31(1981), no. 3, 277--288. MR0635371 (84d:05009). See Table I. - _N. J. A. Sloane_, Mar 27 2012
Anzalone, Nick, et al. A Reciprocity Theorem for Monomer-Dimer Coverings. DMCS. 2003. arXiv:math/0304359 [math.CO]
F. Cazals, Monomer-Dimer Tilings, 1997.
Steven R. Finch, Two Dimensional Monomer-Dimer Constant [Broken link]
Steven R. Finch, Two Dimensional Monomer-Dimer Constant [From the Wayback machine]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 362
Friedland, Shmuel, and Uri N. Peled, Theory of Computation of Multidimensional Entropy with an Application to the Monomer-Dimer Problem. arXiv:math/0402009 [math.CO]
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 (eq. (26) and Table V).
C. Kenyon, D. Randall, and A. Sinclair, Approximating the number of monomer-dimer coverings of a lattice, Journal of Statistical Physics 83 (1996), 637-659.
David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
R. C. Read, The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions, Aequationes Mathematicae, 24 (1982), 47-65.
Ralf Stephan, Animation of all 71 matchings of the P(2) X P(4) graph
D. Zeilberger, Source
Index entries for sequences related to dominoes
Index entries for sequences related to matchings
Index entries for sequences related to polyominoes

from sage.combinat.tiling import TilingSolver, Polyomino
def T(n, k):
    p = Polyomino([(0, 0)])
    q = Polyomino([(0, 0), (0, 1)])
    T = TilingSolver([p, q], box=[n, k], reusable=True)
    return T.number_of_solutions()
# Ralf Stephan, May 22 2014

T(1,n) = A000045(n+1), T(2,n) = A030186(n), T(3,n) = A033506(n), T(4,n) = A033507(n), T(5,n) = A033508(n), T(6,n) = A033509(n), T(7,n) = A033510(n), T(8,n) = A033511(n), T(9,n) = A033512(n), T(10,n) = A033513(n), T(11,n) = A033514(n), T(n,n) = A028420(n).

Typo in term 27 corrected by Alois P. Heinz, Dec 03 2012

Reviewed by Ralf Stephan, May 22 2014

A033507 Number of matchings in graph P_{4} X P_{n}.

Original entry on oeis.org

1, 5, 71, 823, 10012, 120465, 1453535, 17525619, 211351945, 2548684656, 30734932553, 370635224561, 4469527322891, 53898461609719, 649966808093412, 7838012982224913, 94519361817920403, 1139818186429110279, 13745178487929574337, 165754445655292452448

Offset: 0

Per H. Lundow

nonn

			a(1) = 5: the graph is
. o-o-o-o
and the five matchings are
. o o o o
. o-o o o
. o o-o o
. o o o-o
. o-o o-o

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. Phys., 26(1985), 157-167.

Alois P. Heinz, Table of n, a(n) for n = 0..500
David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Index entries for linear recurrences with constant coefficients, signature (9,41,-41,-111,91,29,-23,-1,1).

Column 4 of triangle A210662. Row sums of A100265.
For perfect matchings see A005178.
Cf. A033508-A033511.
Bisection (even part) gives A260034.

a:=[1,5,71,823,10012,120465, 1453535,17525619,211351945];; for n in [10..30] do a[n]:=9*a[n-1]+41*a[n-2]-41*a[n-3]-111*a[n-4]+91*a[n-5] +29*a[n-6]-23*a[n-7]-a[n-8]+a[n-9]; od; a; # G. C. Greubel, Oct 26 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-x)*(1 -3*x-18*x^2+2*x^3+12*x^4+x^5-x^6)/(1-9*x-41*x^2+41*x^3+111*x^4-91*x^5 -29*x^6+23*x^7+x^8-x^9) )); // G. C. Greubel, Oct 26 2019

a:=array(0..20,[1, 5, 71, 823, 10012, 120465, 1453535, 17525619, 211351945]):
for j from 9 to 20 do
  a[j]:=9*a[j-1]+41*a[j-2]-41*a[j-3]-111*a[j-4]+91*a[j-5]+
        29*a[j-6]-23*a[j-7]-a[j-8]+a[j-9]
od:
convert(a,list);
# Sergey Perepechko, Apr 24 2013

LinearRecurrence[{9,41,-41,-111,91,29,-23,-1,1},{1,5,71,823,10012,120465, 1453535,17525619,211351945},30] (* Harvey P. Dale, Mar 27 2015 *)

my(x='x+O('x^30)); Vec((1-x)*(1 -3*x-18*x^2+2*x^3+12*x^4+x^5-x^6)/(1-9*x-41*x^2+41*x^3+111*x^4-91*x^5 -29*x^6+23*x^7+x^8-x^9)) \\ G. C. Greubel, Oct 26 2019

def A033507_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-x)*(1 -3*x-18*x^2+2*x^3+12*x^4+x^5-x^6)/(1-9*x-41*x^2+41*x^3+111*x^4-91*x^5 -29*x^6+23*x^7+x^8-x^9) ).list()
A033507_list(30) # G. C. Greubel, Oct 26 2019

From Sergey Perepechko, Apr 24 2013: (Start)
a(n) = 9*a(n-1) +41*a(n-2) -41*a(n-3) -111*a(n-4) +91*a(n-5) +29*a(n-6) -23*a(n-7) -a(n-8) +a(n-9).
G.f.: (1-x) * (1 -3*x -18*x^2 +2*x^3 +12*x^4 +x^5 -x^6) / (1 -9*x -41*x^2 +41*x^3 +111*x^4 -91*x^5 -29*x^6 +23*x^7 +x^8 -x^9). (End)

Edited by N. J. A. Sloane, Nov 15 2009

A033506 Number of matchings in graph P_{3} X P_{n}.

Original entry on oeis.org

1, 3, 22, 131, 823, 5096, 31687, 196785, 1222550, 7594361, 47177097, 293066688, 1820552297, 11309395995, 70254767718, 436427542283, 2711118571311, 16841658983944, 104621568809247, 649916534985369, 4037327172325542

Offset: 0

Per H. Lundow

nonn

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 50, 999.
Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
R. C. Read, The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions, Aequationes Mathematicae, 24 (1982), 47-65.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Index entries for linear recurrences with constant coefficients, signature (4,14,0,-10,0,1).

Column 3 of triangle A210662. Row sums of A100245.

Cf. A030186, A033507, A033508, A033509, A033510, A033511.

a:=[1,3,22,131,823,5096];; for n in [7..30] do a[n]:=4*a[n-1] +14*a[n-2]-10*a[n-4]+a[n-6]; od; a; # G. C. Greubel, Oct 26 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) )); // G. C. Greubel, Oct 26 2019

seq(coeff(series((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5 )), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 26 2019

CoefficientList[Series[(1-2x-x^2)(1+x-x^2)/((1+x)(1-5x-9x^2+9x^3+x^4-x^5) ), {x, 0, 30}], x] (* Harvey P. Dale, Dec 05 2014 *)
LinearRecurrence[{4, 14, 0, -10, 0, 1}, {1, 3, 22, 131, 823, 5096}, 30] (* Harvey P. Dale, Dec 05 2014 *)
Table[RootSum[-1 +# +9#^2 -9#^3 -5#^4 +#^5 &, 1436541#^n + 3941068#^(n+1) -6086452#^(n+2) -2800519#^(n+3) +591744#^(n+4) &]/10204570 -(-1)^n/5, {n, 20}] (* Eric W. Weisstein, Oct 02 2017 *)

my(x='x+O('x^30)); Vec((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2 +9*x^3+x^4-x^5))) \\ G. C. Greubel, Oct 26 2019

def A033506_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) ).list()
A033506_list(30) # G. C. Greubel, Oct 26 2019

G.f.: (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)). - Sergey Perepechko, Apr 19 2013

A260036 Number of configurations of the general monomer-dimer model for an 8 X 2n square lattice.

Original entry on oeis.org

1, 7573, 211351945, 6158217253688, 179788343101980135, 5249581929453966097649, 153282416794739031814924079, 4475693398084103779028604877129, 130685784089846859975392644067590259, 3815894599555857747953551843550514992237

Offset: 0

N. J. A. Sloane, Jul 19 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..225
N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv:1410.4131 [cond-mat.stat-mech], 2014. See Table 5.

Bisection (even part) of A033511.

A033511 = Cases[Import["https://oeis.org/A033511/b033511.txt", "Table"], {, }][[All, 2]];
Partition[A033511, 2][[All, 1]] (* Jean-François Alcover, Feb 29 2020 *)

a(0), a(5)-a(9) from Alois P. Heinz, Mar 08 2016

cp's OEIS Frontend

A210662 Triangle read by rows: T(n,k) (1 <= k <= n) = number of monomer-dimer tilings of an n X k board.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Sage

Formula

Extensions

A033507 Number of matchings in graph P_{4} X P_{n}.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A033506 Number of matchings in graph P_{3} X P_{n}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A260036 Number of configurations of the general monomer-dimer model for an 8 X 2n square lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions