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

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.

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

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.

Sequence in context: A209749 A248345 A094953 * A122687 A002948 A117113

Adjacent sequences: A332859 A332860 A332861 * A332863 A332864 A332865

Keyword

nonn,tabl

Author

Neil A. McKay, Feb 27 2020

Status

approved