OFFSET
0,4
COMMENTS
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.
LINKS
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
FORMULA
EXAMPLE
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
...
MAPLE
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<nops(l) and l[k+1]=0,
x*b(n, subsop(k=1, k+1=1, l)), 0) +b(n, subsop(k=1, l)))
fi
end:
T:= n-> (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
MATHEMATICA
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<Length[l] && l[[k+1]] == 0, x*b[n, ReplacePart[l, {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 *)
PROG
(Sage)
def T(n, k):
G = Graph(graphs.Grid2dGraph(n, n))
G.relabel()
mu = G.matching_polynomial()
return abs(mu[n^2-2*k])
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Ralf Stephan, May 24 2014
STATUS
approved