login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 00:04 EDT 2021. Contains 345125 sequences. (Running on oeis4.)