A210662 -id:A210662 - cp's OEIS frontend

A030186 a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.

1, 2, 7, 22, 71, 228, 733, 2356, 7573, 24342, 78243, 251498, 808395, 2598440, 8352217, 26846696, 86293865, 277376074, 891575391, 2865808382, 9211624463, 29609106380, 95173135221, 305916887580, 983314691581, 3160687827102, 10159461285307, 32655756991442

Offset: 0

Ottavio D'Antona (dantona(AT)dsi.unimi.it)

Number of matchings in ladder graph L_n = P_2 X P_n.
Cycle-path coverings of a family of digraphs.
a(n+1) = Fibonacci(n+1)^2 + Sum_{k=0..n} Fibonacci(k)^2*a(n-k) (with the offset convention Fibonacci(2)=2). - Barry Cipra, Jun 11 2003
Equivalently, ways of paving a 2 X n grid cells using only singletons and dominoes. - Lekraj Beedassy, Mar 25 2005
It is easy to see that the g.f. for indecomposable tilings (pavings) i.e. those that cannot be split vertically into smaller tilings, is g=2x+3x^2+2x^3+2x^4+2x^5+...=x(2+x-x^2)/(1-x); then G.f.=1/(1-g)=(1-x)/(1-3x-x^2+x^3). - Emeric Deutsch, Oct 16 2006
Row sums of A046741. - Emeric Deutsch, Oct 16 2006
Equals binomial transform of A156096. - Gary W. Adamson, Feb 03 2009
a(n) = Lucas(2n) + Sum_{k=2..n-1} Fibonacci(2k-1)*a(n-k). This relationship can be proven by a visual proof using the idea of tiling a 2 X n board with only singletons and dominoes while conditioning on where the vertical dominoes first appear. If there are no vertical dominoes positioned at lengths 2 through n-1, there will be Lucas(2n) ways to tile the board since a complete tour around the board will be made possible. If the first vertical domino appears at length k (where 2 <= k <= n-1) there will be Fibonacci(2k-1)*a(n-k) ways to tile the board. - Rana Ürek, Jun 25 2018

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25.
J. D. E. Konhauser et al., Which Way Did The Bicycle Go? Problem 140 "Count The Tilings" pp. 42; 180-1 Dolciani Math. Exp. No. 18 MAA Washington DC 1996.

Indranil Ghosh, Table of n, a(n) for n = 0..1968 (terms 0..200 from T. D. Noe)
Ottavio M. D'Antona and Emanuele Munarini, The Cycle-path Indicator Polynomial of a Digraph, Advances in Applied Mathematics 25 (2000), 41-56.
Roger C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.
Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 473
Matt Katz and Catherine Stenson, Tiling a (2xn)-Board with Squares and Dominoes, JIS 12 (2009) 09.2.2, Table 1.
David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
Richard M. Low and Ardak Kapbasov, Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 2.
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.
Richmond B. McQuistan and S. J. Lichtman, Exact recursion relation for (2 × N) arrays of dumbbells, J. Math Phys. 11 (1970), 3095-3099.
László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019.
László Németh, Walks on tiled boards, arXiv:2403.12159 [math.CO], 2024. See pp. 1, 7.
N. J. A. Sloane Notes on A030186 and A033505
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Matching
Yifan Zhang and George Grossman, A Combinatorial Proof for the Generating Function of Powers of a Second-Order Recurrence Sequence, J. Int. Seq. 21 (2018), #18.3.3.
Index entries for linear recurrences with constant coefficients, signature (3,1,-1).

Partial sums give A033505.
Column 2 of triangle A210662.
Cf. A054894, A055518, A055519, A088016.
Cf. A156096. - Gary W. Adamson, Feb 03 2009
Bisection (even part) gives A260033.

a:=[1,2,7];; for n in [4..30] do a[n]:=3*a[n-1]+a[n-2]-a[n-3]; od; a; # G. C. Greubel, Sep 27 2019

a030186 n = a030186_list !! n
a030186_list = 1 : 2 : 7 : zipWith (-) (tail $
   zipWith (+) a030186_list $ tail $ map (* 3) a030186_list) a030186_list
-- Reinhard Zumkeller, Oct 20 2011

a[0]:=1: a[1]:=2: a[2]:=7: for n from 3 to 30 do a[n]:=3*a[n-1]+a[n-2]-a[n-3] od: seq(a[n],n=0..30); # Emeric Deutsch, Oct 16 2006
# second Maple program:
a:= n-> (<<0|1|0>, <0|0|1>, <-1|1|3>>^(n+1))[3,2]:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 07 2024

LinearRecurrence[{3,1,-1}, {1,2,7}, 26] (* Robert G. Wilson v, Nov 20 2012 *)
Table[RootSum[1 -# -3#^2 +#^3 &, 9#^n -10#^(n+1) +7#^(n+2) &]/74, {n, 0, 30}] (* Eric W. Weisstein, Oct 03 2017 *)
CoefficientList[Series[(1-x)/(1-3x-x^2+x^3), {x,0,30}], x] (* Eric W. Weisstein, Oct 03 2017 *)

{a(n)=if(n==0,1,if(n==1,2,(sum(k=0, n-1, a(k))^2+sum(k=0, n-1, a(k)^2))/a(n-1)))} \\ Paul D. Hanna, Nov 20 2012

def A030186_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1-3*x-x^2+x^3)).list()
A030186_list(30) # G. C. Greubel, Sep 27 2019

G.f.: (1-x)/(1-3*x-x^2+x^3).

a(n) = ( (Sum_{k=0..n-1} a(k))^2 + (Sum_{k=0..n-1} a(k)^2) ) / a(n-1) for n>1 with a(0)=1, a(1)=2 (similar to A088016). - Paul D. Hanna, Nov 20 2012

More terms from James Sellers

Entry revised by N. J. A. Sloane, Feb 13 2002

A218354 T(n,k) = Hilltop maps: number of nXk binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 n X k array.

Original entry on oeis.org

1, 3, 3, 5, 11, 5, 9, 41, 41, 9, 17, 149, 291, 149, 17, 31, 547, 2069, 2069, 547, 31, 57, 2007, 14811, 28661, 14811, 2007, 57, 105, 7361, 105913, 401253, 401253, 105913, 7361, 105, 193, 27001, 757305, 5609569, 10982565, 5609569, 757305, 27001, 193, 355

Offset: 1

R. H. Hardin, Oct 26 2012

From Andrew Howroyd, May 10 2017: (Start)
Number of n X k binary matrices with every 1 vertically or horizontally adjacent to some 0.
Number of dominating sets in the grid graph P_n X P_k. (End)

			Table starts
....1.......3...........5..............9.................17
....3......11..........41............149................547
....5......41.........291...........2069..............14811
....9.....149........2069..........28661.............401253
...17.....547.......14811.........401253...........10982565
...31....2007......105913........5609569..........300126903
...57....7361......757305.......78394141.........8199377227
..105...27001.....5415209.....1095695529.......224032447213
..193...99043....38722037....15314367301......6121258910011
..355..363299...276885777...214044940145....167250519310183
..653.1332617..1979899795..2991651891557...4569773233045519
.1201.4888173.14157473937.41813576818545.124859601874166153
...
Some solutions for n=3 k=4
..1..0..1..1....1..1..1..0....1..1..1..0....1..0..1..1....1..0..1..1
..1..0..1..0....1..0..1..0....0..0..1..0....1..0..1..1....1..1..0..1
..0..0..1..0....1..1..0..1....0..1..1..1....1..1..1..1....1..1..1..0

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 198 terms from R. H. Hardin)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Dominating Set
Wikipedia, Dominating Set

Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.
Diagonal is A133515.
Cf. A089934 (independent vertex sets), A210662 (matchings).

Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-3).
k=2: a(n) = 3*a(n-1) +2*a(n-2) +2*a(n-3) -a(n-4) -a(n-5).
k=3: a(n) = 6*a(n-1) +5*a(n-2) +22*a(n-3) +7*a(n-4) +8*a(n-5) -18*a(n-6) -20*a(n-7) -a(n-8) +4*a(n-9) +3*a(n-10) +a(n-12).
Column k=1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){a(n-i)} z=1,2,3,4

A028420 Number of monomer-dimer tilings of n X n chessboard.

Original entry on oeis.org

1, 1, 7, 131, 10012, 2810694, 2989126727, 11945257052321, 179788343101980135, 10185111919160666118608, 2172138783673094193937750015, 1743829823240164494694386437970640, 5270137993816086266962874395450234534887, 59956919824257750508655631107474672284499736089

Offset: 0

Jennifer Henry, Shalosh B. Ekhad, and Steven Finch

Also the total number of matchings (not necessarily perfect ones; i.e., Hosoya index) in the n X n grid. - Andre Poenitz (poenitz(AT)htwm.de), Nov 20 2003

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.

Jennifer Henry, Table of n, a(n) for n = 0..21 [From S. R. Finch, Jan 30 2009]
J. H. Ahrens, 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
Steven R. Finch, Two Dimensional Monomer-Dimer Constant [Broken link]
Steven R. Finch, Two Dimensional Monomer-Dimer Constant [From the Wayback machine] H P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 362.
Svenja Huntemann and 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).
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hosoya Index
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
D. Zeilberger, Source; Local copy
Index entries for sequences related to dominoes

Cf. A004003. A diagonal of A210662.

Row sums of A242861.

b:= proc(n, l) option remember; local k;
      if n=0 then 1
    elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
    else for k while l[k]>0 do od; `if`(k b(n, [0$n]):
seq(a(n), n=0..13);  # Alois P. Heinz, Dec 04 2020

Table[With[{g = GridGraph[{n, n}]}, Count[Subsets[EdgeList[g], Length @ Flatten @ FindIndependentEdgeSet[g]], ?(IndependentEdgeSetQ[g, #] &)]], {n, 4}] (* _Eric W. Weisstein, May 28 2017 *)
b[n_, l_] := b[n, l] = Module[{k}, Which[
     n == 0, 1,
     Min[l] > 0, Function[t, b[n-t, Map[#-t&, l]]][Min[l]],
     True, For[k = 1, l[[k]] > 0, k++]; If[k < Length[l] &&
          l[[k+1]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 1}]], 0] +
          Sum[If[n j]]], {j, 1, 2}]]];
a[n_] := b[n, Table[0, {n}]];
Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Dec 30 2021, after Alois P. Heinz *)

Broken links corrected by Steven Finch, Jan 27 2009

a(0)=1 prepended by Alois P. Heinz, Dec 04 2020

A242861 Triangle T(n,k) by rows: number of ways k dominoes can be placed on an n X n chessboard, k>=0.

Original entry on oeis.org

1, 1, 1, 4, 2, 1, 12, 44, 56, 18, 1, 24, 224, 1044, 2593, 3388, 2150, 552, 36, 1, 40, 686, 6632, 39979, 157000, 407620, 695848, 762180, 510752, 192672, 35104, 2180, 1, 60, 1622, 26172, 281514, 2135356, 11785382, 48145820, 146702793, 333518324, 562203148

Offset: 0

Ralf Stephan, May 24 2014

Also, coefficients of the matching-generating polynomial of the n X n grid graph.

In the n-th row there are floor(n^2/2)+1 values.

			Triangle starts:
  1
  1
  1  4   2
  1 12  44   56    18
  1 24 224 1044  2593   3388   2150    552     36
  1 40 686 6632 39979 157000 407620 695848 762180 510752 192672 35104 2180
  ...

Alois P. Heinz, Rows n = 0..14, flattened
Ralf Stephan, Two dominoes on the 3x3 chessboard, illustration of T(3,2)=44.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Wikipedia, Matching polynomial
Index entries for sequences related to dominoes
Index entries for sequences related to matchings

Cf. A046741, A096713.

b:= proc(n, l) option remember; local k;
      if n=0 then 1
    elif min(l[])>0 then b(n-1, map(h->h-1, l))
    else for k while l[k]>0 do od; expand(`if`(n>1,
         x*b(n, subsop(k=2, l)), 0) +`if`(k (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [0$n])):
seq(T(n), n=0..8); # Alois P. Heinz, Jun 01 2014

b[n_, l_List] := b[n, l] =  Module[{k}, Which[n == 0, 1, Min[l]>0, b[n-1, l-1], True, For[k=1, l[[k]]>0, k++]; Expand[If[n>1, x*b[n, ReplacePart[l, k -> 2]], 0] + If[k 1, k + 1 -> 1}]], 0] + b[n, ReplacePart[l, k -> 1]]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, Array[0&, n]]]; Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Jun 16 2015, after Alois P. Heinz *)

def T(n,k):
   G = Graph(graphs.Grid2dGraph(n,n))
   G.relabel()
   mu = G.matching_polynomial()
   return abs(mu[n^2-2*k])

T(n,1) = A046092(n-1), T(n,2) = A242856(n).
T(n,floor(n^2/2)) = A137308(n), T(2n,2n^2) = A004003(n).
sum(k>=0, T(n,k)) = A210662(n,n) = A028420(n).
T(n,3) = A243206(n), T(n,4) = A243215(n), T(n,5) = A243217(n), T(n,floor(n^2/4)) = A243221(n). - Alois P. Heinz, Jun 01 2014

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 1, 7, 1, 2, 43, 43, 2, 3, 277, 969, 277, 3, 5, 1777, 23663, 23663, 1777, 5, 8, 11407, 571099, 2180738, 571099, 11407, 8, 13, 73219, 13807469, 198906617, 198906617, 13807469, 73219, 13, 21, 469981, 333735575, 18169793971, 68534828391, 18169793971, 333735575, 469981, 21

Offset: 1

Andrew Howroyd, May 15 2017

			Table starts:
======================================================================
m\n| 1     2        3           4              5                 6
---|------------------------------------------------------------------
1  | 0     1        1           2              3                 5 ...
2  | 1     7       43         277           1777             11407 ...
3  | 1    43      969       23663         571099          13807469 ...
4  | 2   277    23663     2180738      198906617       18169793971 ...
5  | 3  1777   571099   198906617    68534828391    23650967140325 ...
6  | 5 11407 13807469 18169793971 23650967140325 30833670159649637 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Grid Graph

Rows 1-3 are A000045(n-1), A286911, A288031.
Main diagonal is A286913.
Cf. A210662, A099390, A089934, A218354.

T(1,1) corrected by Andrew Howroyd, Jun 04 2017

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

A242856 Number of 2-matchings of the n X n grid graph.

Original entry on oeis.org

2, 44, 224, 686, 1622, 3272, 5924, 9914, 15626, 23492, 33992, 47654, 65054, 86816, 113612, 146162, 185234, 231644, 286256, 349982, 423782, 508664, 605684, 715946, 840602, 980852, 1137944, 1313174, 1507886, 1723472, 1961372, 2223074, 2510114, 2824076, 3166592

Offset: 2

Ralf Stephan, May 24 2014

Number of ways two dominoes can be placed on an n X n chessboard.

Alois P. Heinz, Table of n, a(n) for n = 2..1000
Ralf Stephan, In how many ways can we place two dominoes on the n x n chessboard? Proof of formula.
Ralf Stephan, Two dominoes on the 3x3 chessboard, illustration of a(3)=44.
Index entries for sequences related to dominoes.
Index entries for sequences related to matchings.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Second column of A242861. Cf. A016742, A046092, A054000, A210662.

LinearRecurrence[{5, -10, 10, -5, 1}, {2, 44, 224, 686, 1622}, 50] (* Paolo Xausa, May 20 2024 *)

Vec(-2*x^2*(x^4-7*x^3+12*x^2+17*x+1)/(x-1)^5 + O(x^100)) \\ Colin Barker, Jun 26 2014

def a(n):
    G = Graph(graphs.Grid2dGraph(n,n))
    G.relabel()
    return G.matching_polynomial()[n^2-4]

a(n) = 2*n^4 - 4*n^3 - 5*n^2 + 13*n - 4.
G.f.: -2*x^2*(x^4-7*x^3+12*x^2+17*x+1) / (x-1)^5. - Colin Barker, Jun 26 2014
a(n + 1) = (1/2)*A046092(n)*(A046092(n) - 1) - A016742(n) - A054000(n). - Nicolas Bělohoubek, May 15 2024
E.g.f.: 4 - 2*x + exp(x)*(2*x^4 + 8*x^3 - 3*x^2 + 6*x - 4). - Stefano Spezia, Jun 04 2024

a(7)-a(36) from Alois P. Heinz, Jun 01 2014

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

A033511 Number of matchings in graph P_{8} X P_{n}.

Original entry on oeis.org

1, 34, 7573, 1222550, 211351945, 36012826776, 6158217253688, 1052091957273408, 179788343101980135, 30721240815429999078, 5249581929453966097649, 897032469743945346623442, 153282416794739031814924079, 26192460807219455656314349664

Offset: 0

Per H. Lundow

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450
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.
Sergey Perepechko, Generating function

Column 8 of triangle A210662.

Bisection (even part) gives A260036.

A033508 Number of matchings in graph P_{5} X P_{n}.

Original entry on oeis.org

1, 8, 228, 5096, 120465, 2810694, 65805403, 1539222016, 36012826776, 842518533590, 19711134149599, 461148537211748, 10788744980331535, 252406631116215534, 5905146419664967132, 138153075553825008696

Offset: 0

Per H. Lundow

nonn

These are the row sums of the following triangle of the matchings of P_5 X P_n with k>=0 monomers (A003775 appears in the first column):
1;
0, 3, 0, 4, 0, 1;
8, 0, 56, 0, 94, 0, 56, 0, 13, 0, 1;
0, 106, 0, 757, 0, 1670, 0, 1597, 0, 758, 0, 185, 0, 22, 0, 1;
95, 0, 2111, 0, 12181, 0, 29580, 0, 36771, 0, 25835, 0, 10769, 0, 2696, 0, 395, 0, 31, 0, 1;
0, 2180, 0, 35104, 0, 192672, 0, 510752, 0, 762180, 0, 695848, 0, 407620, 0, 157000, 0, 39979, 0, 6632, 0, 686, 0, 40, 0, 1;
1183, 0, 52614, 0, 611633, 0, 3146447, 0, 8803727, 0, 14957414, 0, 16492039, 0, 12307901, 0, 6380454, 0, 2329148, 0, 600254, 0, 108186, 0, 13295, 0, 1058, 0, 49, 0, 1;
0, 37924, 0, 1054776, 0, 10405842, 0, 51732687, 0, 151233778, 0, 283790459, 0, 361377070, 0, 324069497, 0, 209807278, 0, 99625091, 0, 34985010, 0, 9096697, 0, 1740018, 0, 240905, 0, 23414, 0, 1511, 0, 58, 0, 1;
- R. J. Mathar, May 06 2016

F. Cazals, Monomer-Dimer Tilings, 1997.
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.

Column 5 of triangle A210662.

# The following g.f. is for the sequence a(0)=1, a(1)=8, a(2)=228, etc.
Gf:= (1-6*x-113*x^2+88*x^3+1794*x^4-1994*x^5-6956*x^6+7532*x^7+
11175*x^8-9448*x^9-9255*x^10+4700*x^11+3820*x^12-870*x^13-654*x^14+
68*x^15+45*x^16-2*x^17-x^18)/(1-14*x-229*x^2+16*x^3+4757*x^4-898*x^5-
35106*x^6+26564*x^7+74665*x^8-60482*x^9-73623*x^10+50158*x^11+
38553*x^12-17604*x^13-10366*x^14+2538*x^15+1281*x^16-140*x^17-65*x^18+
2*x^19+x^20):
expr:=convert(series(Gf,x,21),polynom):
seq(coeff(expr,x,j),j=0..20);
# Sergey Perepechko, Apr 26 2013

For g.f. see Maple program. - Sergey Perepechko, Apr 26 2013

cp's OEIS Frontend

A030186 a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A218354 T(n,k) = Hilltop maps: number of nXk binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 n X k array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A028420 Number of monomer-dimer tilings of n X n chessboard.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A242861 Triangle T(n,k) by rows: number of ways k dominoes can be placed on an n X n chessboard, k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

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

A242856 Number of 2-matchings of the n X n grid graph.

Views

Author