|
| |
|
|
A332862
|
|
Array read by antidiagonals: T(m,n) = number of placements of zero or more dominoes on the m X n grid where no two empty squares are horizontally adjacent.
|
|
4
|
|
|
|
1, 1, 2, 2, 4, 3, 2, 11, 9, 5, 3, 25, 48, 25, 8, 4, 61, 172, 227, 64, 13, 5, 146, 731, 1427, 1054, 169, 21, 7, 351, 2976, 10388, 11134, 4921, 441, 34, 9, 844, 12039, 72751, 140555, 88733, 22944, 1156, 55, 12, 2028, 49401, 510779, 1693116, 1932067, 701926, 107017, 3025, 89
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
By symmetry this is the same as the number of placements of zero or more dominoes on the n X m grid where no two empty squares are vertically adjacent.
The number of positions of m X n Domineering where horizontal (Right) has no moves, also called Right ends. Domineering is a game in which players take turns placing dominoes on a grid, one player placing vertically and the other horizontally until the player to place cannot place a domino.
All rows and columns are linear recurrences with constant coefficients. An upper bound on the order of the recurrence for columns is A005418(n+1), which is the number of binary words of length n up to reversal. An upper bound on the order of the recurrence for rows is A032120(m). This upper bound is exact for at least 1 <= m <= 6. - Andrew Howroyd, Feb 28 2020
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Table starts:
===================================================================
m\n| 1 2 3 4 5 6 7
---|---------------------------------------------------------------
1 | 1 1 2 2 3 4 5 ...
2 | 2 4 11 25 61 146 351 ...
3 | 3 9 48 172 731 2976 12039 ...
4 | 5 25 227 1427 10388 72751 510779 ...
5 | 8 64 1054 11134 140555 1693116 20414525 ...
6 | 13 169 4921 88733 1932067 40008789 831347033 ...
7 | 21 441 22944 701926 26425981 941088936 33656587715 ...
8 | 34 1156 107017 5567467 362036629 22168654178 1365206879940 ...
...
|
|
|
PROG
|
(Sage) See Bjorn Huntemann, Svenja Huntemann, Neil A. McKay link.
(PARI) \\ here R(n) is row 1 as vector.
R(n)={Vec((1+x+x^2)/(1-x^2-x^3)+O(x*x^n))}
F(b, r)={my(t=1); while(b, b=(b>>valuation(b, 2))+1; my(s=valuation(b, 2)); t*=r[s]; b>>=s+1); t}
step(v, f)={vector(#v, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, j), v[1+j]*(f[#v-bitor(i, j)]))))}
T(m, n)={my(r=R(n), f=vector(2^n, i, F(i-1, r)), v=vector(2^n)); v[1]=1; for(k=2, m, v=step(v, f)); sum(j=0, #v-1, v[1+j]*f[#v-j])}
{for(m=1, 8, for(n=1, 8, print1(T(m, n), ", ")); print)} \\ Andrew Howroyd, Feb 28 2020
|
|
|
CROSSREFS
|
Cf. A288026 (the number of placements of dominoes on an m X n grid where no two empty squares are horizontally or vertically adjacent).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
