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

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

Author

Ralf Stephan, May 24 2014

Keywords

• nonn
• easy

Comments

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

Links

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

Crossrefs

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

Programs

Mathematica

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

PARI

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

Sage

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

Formula

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

Extensions

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