OFFSET
2,1
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 linear recurrences with constant coefficients, signature (5,-10,10,-5,1).
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
MATHEMATICA
LinearRecurrence[{5, -10, 10, -5, 1}, {2, 44, 224, 686, 1622}, 50] (* Paolo Xausa, May 20 2024 *)
PROG
(Sage)
def a(n):
G = Graph(graphs.Grid2dGraph(n, n))
G.relabel()
return G.matching_polynomial()[n^2-4]
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ralf Stephan, May 24 2014
EXTENSIONS
a(7)-a(36) from Alois P. Heinz, Jun 01 2014
STATUS
approved