A210724 -id:A210724 - cp's OEIS frontend

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 4, 5, 1, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 1, 13, 15, 36, 15, 13, 1, 1, 1, 1, 21, 41, 95, 95, 41, 21, 1, 1, 1, 1, 34, 56, 281, 192, 281, 56, 34, 1, 1, 1, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 1, 1, 1, 89, 209, 2245, 2415, 6728, 2415, 2245, 209, 89, 1, 1

Offset: 0

Alois P. Heinz, Apr 15 2011

			A(3,3) = 4, because there are 4 domino tilings of the 3 X 3 grid with upper left corner removed:
  . .___. . .___. . .___. . .___.
  ._|___| ._|___| ._| | | ._|___|
  | |___| | | | | | |_|_| |___| |
  |_|___| |_|_|_| |_|___| |___|_|
Array begins:
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  2,  3,   5,    8,   13, ...
  1, 1,  3,  4,  11,   15,   41, ...
  1, 1,  5, 11,  36,   95,  281, ...
  1, 1,  8, 15,  95,  192, 1183, ...
  1, 1, 13, 41, 281, 1183, 6728, ...

Alois P. Heinz, Antidiagonals n = 0..75, flattened
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, FKT algorithm
Wikipedia, Matching (graph theory)
Index entries for sequences related to dominoes

Rows m=0+1, 2-12 give: A000012, A000045(n+1), A002530(n+1), A005178(n+1), A189003, A028468, A189004, A028470, A189005, A028472, A210724, A028474.
Main diagonal gives: A189002.
Cf. A099390, A187596, A187616, A187617, A187618, A004003.

with(LinearAlgebra):
A:= proc(m, n) option remember; local i, j, s, t, M;
      if m=0 or n=0 then 1
    elif m1 or j>1 or s=0 then
               if j

A[1, 1] = 1; A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2];M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i-1)*m+j-s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t+1] = 1]; If[i < n, M[t, t+m] = 1-2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m-s, n*m-s}]]]]]; Table[Table[A[m, d-m], {m, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 26 2013, translated from Maple *)

A139400 Number of spanning trees in the graph P_6 x P_n.

Original entry on oeis.org

1, 780, 380160, 170537640, 74795194705, 32565539635200, 14143261515284447, 6136973985625588560, 2662079368040434932480, 1154617875754582889149500, 500769437567956298239402223, 217185579535490113365186969600

Offset: 1

Paul Raff, Jun 09 2008; corrected recurrence Feb 03 2009

Also number of domino tilings of the 11 X (2n-1) rectangle with upper left corner removed. - Alois P. Heinz, Apr 14 2011

A linear divisibility sequence of order 32; a(n) divides a(m) whenever n divides m. It is the product of four linear divisibility sequences - three Lucas sequences of order 2 and one linear divisibility sequence of order 4. - Peter Bala, Apr 27 2014

			a(2) = 780, as can be verified from the seventh entry of A001353, which corresponds to the number of spanning trees of the same graph.

Paul Raff, Table of n, a(n) for n = 1..208
Paul Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (780, -194881, 22377420, -1419219792, 55284715980, -1410775106597, 24574215822780, -300429297446885, 2629946465331120, -16741727755133760, 78475174345180080, -273689714665707178, 716370537293731320, -1417056251105102122, 2129255507292156360, -2437932520099475424, 2129255507292156360, -1417056251105102122, 716370537293731320, -273689714665707178, 78475174345180080, -16741727755133760, 2629946465331120, -300429297446885, 24574215822780, -1410775106597, 55284715980, -1419219792, 22377420, -194881, 780, -1).

Row m=6 of A116469.

Bisection of A210724 (odd part). A001353, A001906, A004254, A159764, A161498.

seq(resultant(simplify(ChebyshevU(5, (x-4)*(1/2))), simplify(ChebyshevU(n-1, (1/2)*x)), x), n = 1 .. 12); # Peter Bala, Apr 27 2014

Array[Resultant[ChebyshevU[5, x/2-2], ChebyshevU[#-1, x/2], x] &, 20] (* Paolo Xausa, Mar 17 2024, after Peter Bala *)

a(n) = 780 a(n-1) - 194881 a(n-2) + 22377420 a(n-3) - 1419219792 a(n-4) + 55284715980 a(n-5) - 1410775106597 a(n-6) + 24574215822780 a(n-7) - 300429297446885 a(n-8) + 2629946465331120 a(n-9) - 16741727755133760 a(n-10)
+ 78475174345180080 a(n-11) - 273689714665707178 a(n-12) + 716370537293731320 a(n-13) - 1417056251105102122 a(n-14) + 2129255507292156360 a(n-15) - 2437932520099475424 a(n-16) + 2129255507292156360 a(n-17)
- 1417056251105102122 a(n-18) + 716370537293731320 a(n-19) - 273689714665707178 a(n-20) + 78475174345180080 a(n-21) - 16741727755133760 a(n-22) + 2629946465331120 a(n-23) - 300429297446885 a(n-24) + 24574215822780 a(n-25) - 1410775106597 a(n-26) + 55284715980 a(n-27) - 1419219792 a(n-28) + 22377420 a(n-29) - 194881 a(n-30) + 780 a(n-31) - a(n-32).
From Peter Bala, Apr 27 2014: (Start)
a(n) = Resultant( U(5,(x-4)/2), U(n-1,x/2) ), where U(n,x) denotes the Chebyshev polynomial of the second kind. The polynomial U(5,(x-4)/2) = x^5 - 20*x^4 + 156*x^3 - 592*x^2 + 1091*x - 780 (see A159764) has zeros z_1 = 3, z_2 = 4, z_3 = 5, z_4 = 4 + sqrt(3) and z_5 = 4 - sqrt(3). Hence a(n) = U(n-1,3/2)*U(n-1,2)*U(n-1,5/2)*U(n-1,1/2*(4 + sqrt(3)))*U(n-1,1/2*(4 - sqrt(3))).
a(n) = A001906(n)*A001353(n)*A004254(n)*A161498(n). (End)

A028473 Number of perfect matchings in graph P_{11} X P_{2n}.

Original entry on oeis.org

1, 144, 51205, 21001799, 8940739824, 3852472573499, 1666961188795475, 722364079570222320, 313196612952258199679, 135818983640055277506397, 58902468764522025160456848, 25545661075321867247577262777, 11079103257893769392837296086025

Offset: 0

Per H. Lundow

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200
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.
Vladeta Jovovic, Explicit formula, generating function and recurrence
Index entries for linear recurrences with constant coefficients, signature (780, -194881, 22377420, -1419219792, 55284715980, -1410775106597, 24574215822780, -300429297446885, 2629946465331120, -16741727755133760, 78475174345180080, -273689714665707178, 716370537293731320, -1417056251105102122, 2129255507292156360, -2437932520099475424, 2129255507292156360, -1417056251105102122, 716370537293731320, -273689714665707178, 78475174345180080, -16741727755133760, 2629946465331120, -300429297446885, 24574215822780, -1410775106597, 55284715980, -1419219792, 22377420, -194881, 780, -1).

Row 11 of array A099390.

Bisection of A210724 (even part).

T[?OddQ, ?OddQ] = 0;
T[m_, n_] := Product[2(2+Cos[2 j Pi/(m+1)]+Cos[2 k Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];
a[n_] := T[2n, 11] // Round;
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 28 2022 *)

{a(n) = sqrtint(polresultant(polchebyshev(2*n, 2, x/2), polchebyshev(11, 2, I*x/2)))} \\ Seiichi Manyama, Apr 13 2020

Title corrected by Sergey Perepechko, Nov 27 2012

cp's OEIS Frontend

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A139400 Number of spanning trees in the graph P_6 x P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A028473 Number of perfect matchings in graph P_{11} X P_{2n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions