|
%I #23 Feb 28 2020 21:37:09
%S 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,
%T 1054,169,21,7,351,2976,10388,11134,4921,441,34,9,844,12039,72751,
%U 140555,88733,22944,1156,55,12,2028,49401,510779,1693116,1932067,701926,107017,3025,89
%N 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.
%C 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.
%C 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.
%C 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
%H Andrew Howroyd, <a href="/A332862/b332862.txt">Table of n, a(n) for n = 1..378</a>
%H Bjorn Huntemann, Svenja Huntemann, Neil A. McKay, <a href="http://www2.unb.ca/~nmckay/oeis/CountingDomineering.sagews">SageMath code for Counting Domineering Positions</a>
%H Svenja Huntemann, Neil A. McKay, <a href="https://arxiv.org/abs/1909.12419">Counting Domineering Positions</a>, arXiv:1909.12419 [math.CO], 2019.
%e Table starts:
%e ===================================================================
%e m\n| 1 2 3 4 5 6 7
%e ---|---------------------------------------------------------------
%e 1 | 1 1 2 2 3 4 5 ...
%e 2 | 2 4 11 25 61 146 351 ...
%e 3 | 3 9 48 172 731 2976 12039 ...
%e 4 | 5 25 227 1427 10388 72751 510779 ...
%e 5 | 8 64 1054 11134 140555 1693116 20414525 ...
%e 6 | 13 169 4921 88733 1932067 40008789 831347033 ...
%e 7 | 21 441 22944 701926 26425981 941088936 33656587715 ...
%e 8 | 34 1156 107017 5567467 362036629 22168654178 1365206879940 ...
%e ...
%o (Sage) See Bjorn Huntemann, Svenja Huntemann, Neil A. McKay link.
%o (PARI) \\ here R(n) is row 1 as vector.
%o R(n)={Vec((1+x+x^2)/(1-x^2-x^3)+O(x*x^n))}
%o 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}
%o 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)]))))}
%o 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])}
%o {for(m=1, 8, for(n=1, 8, print1(T(m,n), ", ")); print)} \\ _Andrew Howroyd_, Feb 28 2020
%Y Columns 1..3 are A000045, A007598, A054894.
%Y Rows 1..2 are A000931(n + 5), A329707.
%Y Main diagonal is A332865.
%Y Cf. A288026 (the number of placements of dominoes on an m X n grid where no two empty squares are horizontally or vertically adjacent).
%Y Cf. A005418, A032120.
%K nonn,tabl
%O 1,3
%A _Neil A. McKay_, Feb 27 2020
|
