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.

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

Offset: 1

Author

Neil A. McKay, Feb 27 2020

Keywords

• nonn
• tabl

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

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..378
• Bjorn Huntemann, Svenja Huntemann, Neil A. McKay, SageMath code for Counting Domineering Positions
• Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.

Crossrefs

Columns 1..3 are A000045, A007598, A054894.

Rows 1..2 are A000931(n + 5), A329707.

Main diagonal is A332865.

Cf. A288026 (the number of placements of dominoes on an m X n grid where no two empty squares are horizontally or vertically adjacent).

Cf. A005418, A032120.

Programs

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

Sage

# See Bjorn Huntemann, Svenja Huntemann, Neil A. McKay link.