{'fraction_non_alphanumeric': 0.028813612929752982, 'fraction_numerical': 0.016921276528449884, 'mean_word_length': 4.115353502669471, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Counting Domineering Positions

Abstract. Domineering is a two player game played on a checkerboard in which one player places dominoes vertically, while the other places them horizontally. We will give bivariate generating polynomials enumerating Domineering positions given the number of pieces placed by each player. Specifically, we enumerate all positions, maximal positions, and Right or Left ending positions. We also discuss how this relates to other counting problems, including matchings on grid graphs.


Introduction
Combinatorial games are 2-player games with perfect information and no chance devices, such as Chess or Go. Many combinatorial games have, for a fixed starting position, a finite number of options and the game is guaranteed to end in a finite number of moves; in theory we could determine by computer which player would win if both players play perfectly. In practice game theorists and computer scientists have not determined the outcomes of games under perfect-play because of the complexity of the required search.
Enumeration of positions has been studied, directly or indirectly, for several combinatorial games. The first few papers on counting game positions considered the problem of enumerating specific types of positions-Go end positions in [7,6,16] and second-player win positions for two games in [8,9]. In the game Node Kayles, played on a graph, the two players alternate choosing vertices not adjacent to any previously chosen ones, thus forming an independent set. Therefore the independence polynomial of a graph is equal to the generating polynomial for positions of Node Kayles on that graph. Similarly, in the play of Arc Kayles the players form a matching. The enumeration of matchings has been studied for many graphs (see Section 1.1). In partizan games, where players may have distinct options at some point during play, the convention is to call the two players Left (who uses bLue pieces) and Right (who uses Red pieces). In Col, which is played on a graph, a move for Left is to colour a vertex blue, while a move for Right is to colour a vertex red, and no two vertices of the same colour may be adjacent. Oh and Lee [12] call such a position a bipartite independent vertex set and give the generating polynomial for grid graphs. Brown et al. [4] give the generating polynomial, which they call the polynomial profile, for several games, including closed forms for Col and the game Snort (like Col, but two vertices of different colours may not be adjacent) played on paths.
In this paper we consider the game ÓÑ Ò Ö Ò . This game is played on a checkerboard. The two players alternately place dominoes; Left places vertically and Right places horizontally. The game ends when the player whose turn it is cannot place a piece; this player loses -this is the Normal play convention. We will count all Domineering positions, as well as Domineering positions with certain properties, following the method used by Oh and Lee in [11,12]. In newer work Oh also considers monomer-dimer tilings in [10], thus implicitly counting Domineering positions, which overlaps with some of our work as discussed in Section 2.
Domineering, also called Dominoes or Crosscram in older work, was introduced by Göran Andersson and popularized by Martin Gardner in the 1970s. There has been significant interest in this game since then (see for example [2,3,17,18,19] and references therein). Some simplification techniques are known and can be combined with computer search for analysis, but no complete solution is available. It is known who wins on many rectangular boards up to size 11 × 11 and some nonrectangular boards, as well as some values (essentially who has the advantage and by how much) and temperatures (essentially the urgency of moving). For the reader further interested in combinatorial game theory techniques, see [14].
As a game of Domineering progresses, it often naturally breaks into smaller components, see Figure 1. A player on their turn has to decide which component they want to play in and make their move there. This is called the disjunctive sum of these components. If the two players choose different components in the disjunctive sum it can happen that the same player makes two consecutive turns in the same component. For example in Figure 1, if it is Right's turn, he could choose to play in the third component, Left may choose the fourth, and Right choose the third again. Due to this, we are also interested in Domineering positions in which the two players do not necessarily alternate turns, hence we consider plays where the difference between the number of Left dominoes and Right dominoes may be larger than 1.
In Section 2 we will find the generating function for the number of positions on an m × n rectangular board which we denote by where d(a, b) is the number of positions with a Left dominoes and b Right dominoes. We then demonstrate in Section 3 how to generalize the technique employed to find D m,n (x, y) to calculate the generating function for non-rectangular boards.
We are also particularly interested in enumerating positions at the end of the game. A Left end is a position in which Left can no longer play a piece, while Right potentially still has moves; a Right end is defined similarly. A maximal position is a position which is both a Left end and a Right end -a position in which no player can place a domino. In Section 4 we will find the generating function for maximal positions, which we denote by F m,n (x, y). In Section 5 we consider the generating function for Right ends; this is essentially the same as the generating function for Left ends.
Finally, in Section 6 we will discuss some other questions related to the technique used within and the problem of enumerating Domineering positions.
1.1. Related Problems. The checkerboard corresponds to a grid graph by using a vertex for each square and connecting them with an edge if the two squares are horizontally or vertically adjacent. Playing Domineering on the checkerboard is then equivalent to forming a matching (also called an edge independent set) on the grid graph, with a distinction made between horizontal and vertical edges.
If we make no distinction between Left and Right dominoes, that is, we enumerate the positions with a fixed number of dominoes, this is equivalent to enumerating the number of matchings in a grid graph or enumerating the monomer-dimer tilings of the chessboard (for a summary of connections to physics and chemistry see [13]). In particular, this means that D m,n (x, x) is the generating function for matchings in an m × n grid graph, and that D m,n (1, 1) gives the total number of such matchings. The latter, also known as the Hosoya index of the grid graph, is known (for example see [1] or the OEIS 1 sequences A030186 for 2 × n, A033506 for 3 × n, and A028420 for n × n). If a perfect matching exists in the m × n grid graph, then the number of perfect matchings is the leading coefficient of D m,n (x, x) as this is the number of maximum matchings.
Similarly, F m,n (x, x) gives the generating function for the maximal matchings in an m × n grid graph. The total number of maximal positions F m,n (1, 1) are known for some values of m and n (OEIS sequences A000931 for 1 × n, A286945 for 2 × n, A288028 for 3 × n, and A287595 for n × n).
Domineering belongs to the class of strong placement games, and thus one can assign to each game a simplicial complex representing the legal positions (see [5] for details). The coefficients of D m,n (x, x) are then the entries of the f -vectorthe vector counting the number of faces of a given dimension -of this simplicial complex, while the coefficients of F m,n (x, x) give the number of maximal faces, called facets, of a fixed dimension. Our work in this paper was originally motivated by wanting to determine how many facets there are with a given number of vertices representing Left or Right moves. We solve this problem by finding F m,n (x, y) in Section 4.

Counting All Domineering Positions
Given m and n, our goal is to count the number of Domineering positions that can occur as the result of play in an m × n rectangle. To distinguish this problem from counting specific types of domineering positions later we refer to these as general Domineering positions.
We will find a generating function D m,n (x, y) such that where d(a, b) is the number of Domineering positions with a Left (vertical) dominoes and b Right (horizontal) dominoes.
From the generating function, we will extract information on the play positions, those that can be reached through alternating play, in Section 2.1.
In their paper, Oh [10] considers an equivalent problem to the particular problem of counting general positions using a trivariate generating function, where the third variable counts the number of empty squares. The number of empty squares is not particularly relevant to Domineering. However, this information can be deduced from the number of dominoes of either player and the board size. We use an equivalent method, but as our generating functions are slightly different, our recursions are different as well. We include the recursion here for completeness, particularly as we continue using the matrices in Section 3.
To count rectangular Domineering positions we consider the tilings of rectangles using tiles with edge labels, then count the tilings that correspond to positions.
We use the tiles in Figure 2. (1) Adjacency condition: All shared edges of adjacent tiles have the same label.
(2) Boundary condition: All boundary edges of the tiling have label 0. Together these conditions ensure that the tiling has no half-dominoes. In turn, any Domineering position can be uniquely represented using such a tiling. See Figure 3 for an example.
In the tiling of a Domineering position, such as in Figure 3, the number of Left (vertical) dominoes is equal to the number of T 1 tiles, and the number of Right (horizontal) dominoes is equal to the number of T 3 tiles. We use the term mosaic for tilings that satisfy the adjacency condition, but not necessarily the boundary condition. A 1 × q mosaic is called a bar mosaic, that is, a row of q tiles.
We will find generating polynomials by first counting bar mosaics. We then stack these bars to count rectangular mosaics. It is in this step that we will consider the adjacency condition for vertically adjacent tiles. Finally, we will restrict to those tilings that also satisfy the boundary condition.
We will count mosaics instead of just Domineering tilings as a row or column of a Domineering rectangle is not necessarily a Domineering position itself. For example in Figure 3 the second row from the bottom forms the bar mosaic shown in Figure 4-it does not correspond to a Domineering position on its own as the leftmost two tiles are unpaired half-dominoes but shared edges of horizontally adjacent tiles do have the same label. Figure 4. A row of a Domineering tiling is a bar mosaic, which satisfies the (horizontal) adjacency condition but not necessarily boundary condition.
The enumeration of bar mosaics will be done using matrices, called bar-state matrices. We take care to construct these matrices so that we can count rectangular mosaics by matrix multiplication. As we only want in the end to count mosaics that satisfy the boundary condition we can make due with counting only bar mosaics with label 0 on the right end. The enumeration of the bar mosaics will be done recursively -we use the enumeration of bar mosaics to enumerate longer bar mosaics -so our matrices are recursively defined (using blocks). We use two bar-state matrices; the matrix to count bar mosaics of length q with right label 0 and left label 0 is denoted by G 0,q and the matrix to count bar mosaics of length q with right label 0 and left label 1 is denoted by G 1,q . We use G here for naming the matrices, standing for 'general', to reserve M for matrices in the subsequent sections of the paper, which include a discussion of maximal positions.
Theorem 2.1. The polynomial profile of Domineering on an m × n board is the (1,1) entry of G m 0,n where G 0,0 = 1 , G 1,0 = 0 , and Proof. We will first prove that the bar-state matrices give the generating polynomials for bar mosaics.
In a bar-state matrix the rows and columns are indexed by binary strings of length q. Thus each matrix has size 2 q ×2 q . We order these strings lexicographically. Thus, the strings of length 3 are ordered as 000, 001, 010, 011, 100, 101, 110, 111.
An entry in a bar-state matrix is the generating polynomial of the bar whose top edge labels are the column index, and whose bottom edge labels are the row index; the right edge label is 0 and the left edge label corresponds to the matrix (the first subscript of G). The generating polynomial of the bar is the monomial x a y b where a is the number of T 1 in the bar and b is the number of T 3 in the bar.
For q = 0, so the length is 0, it is only possible to satisfy the adjacency condition if both the starting and ending labels are the same. We thus have G 0,0 = 1 and G 1,0 = 0 .
Our construction for larger q uses blocks and we name them as in Figure 5 to avoid proliferating subscripts. We need to show that in each matrix the 4 blocks are as we claim. Our argument is recursive and follows by first considering the leftmost tile in each bar. The block considered determines the top label and bottom label of the leftmost tile in bar mosaics enumerated as in Figure 5. For q = 1 the bars we are counting consist of a single tile which must have right label 0 (or cannot have right label 1), that is, one of the four tiles 0-3; you may wish to reference Figure 2. Thus between the bar-state matrices G 0,1 and G 1,1 we have four nonzero blocks -determined by the top and bottom labels of tiles 0-3. Recall that each block has a corresponding top and bottom label of the leftmost tile. Thus and this shows that the recursion is correct for the first step. The bar-state matrix G 0,q+1 enumerates mosaics where the leftmost tile has left label 0 (and right label 0). We consider possible leftmost tiles which are tiles 0-2 and 4, as these are the only tiles with left label 0. Of these four tiles, those tiles that meet the conditions for block I are tile 0 and tile 4. As the right label of tile 0 is 0, the possible completions of our bar when the leftmost tile is tile 0 are given by G 0,q . As the right label of tile 4 is 1, the possible completions of our bar are given by G 1,q . So block I is G 0,q + G 1,q .
The conditions for block II (that the leftmost tile have top label 1 and bottom label 0) require T 1 as the leftmost tile in the bar mosaic and the entry is xG 0,q because the right label of tile 1 is 0 and G 0,q counts the bar mosaics with left label 0 and right label 0 (recall that for each T 1 we have an x).
The conditions for block III force T 2 as the leftmost tile, giving the entry G 0,q . For block IV, we would need a tile with bottom and top label 1 but no tiles have such labels and so our entry is 0.
In G 1,q+1 , we have a left label of 1. As our recursion starts by consider possible left tiles, we need only consider tile 3, as this is the only tile with 1 as a left label.
Thus the only block for which tile 3 has appropriate top and bottom labels is block I. Since T 3 is forced and its left label is 0, the possible completions of the bar are given by G 0,q and the entry in block one is yG 0,q . All other blocks, having no possible leftmost tiles, count no mosaics and thus their blocks are 0.
We turn our attention to rectangular m × n tilings and in particular those that satisfy the left and right boundary conditions, so we will only consider the bar mosaics of length n with left label 0 in addition to having the right label 0; these are counted by G 0,n .
First consider 2 × n mosaics that satisfy the adjacency condition. Such a mosaic consists of two bar mosaics where the string of bottom labels of one mosaic matches the string of top labels of the other. Suppose A is the bar-state matrix for the top bar and B is the bar-state matrix for the bottom bar. To count all the 2×n mosaics that satisfy the adjacency condition we need to consider all 2 n strings of matched labels along the stacked bar mosaics. That is, we take columns in A and rows in B.
Since the other labels of the bar mosaics have to match, we take the dot product of the two vectors to get the polynomial for this mosaic. Thus the matrix for the 2 × n mosaic is BA.
To get mosaics that also satisfy the boundary conditions and thus correspond to Domineering positions we can start with bar mosaics that satisfy the left and right boundary conditions; in our case A = B = G 0,n , so the state matrix for 2 × n mosaics where the left and right boundary conditions are also satisfied is G 2 0,n . For larger mosaics this works the same way; we stack more bars and find that the matrix for a m × n mosaic is G m 0,n . Fixing the string of top labels and of bottom labels for the 2 × n mosaic corresponds to specifying an entry in the matrix. Finally, to satisfy the boundary condition on top and bottom we need to restrict to all top and bottom labels being 0. This means we take the entry in the top left corner, entry (1, 1).
For example, that on a 4 × 3 Domineering board there are 90 positions with 1 vertical domino and 2 horizontal dominoes is shown by the term 90xy 2 and that there is 1 position with 6 vertical dominoes is shown by the term x 6 .
2.1. Play positions. The polynomials we have found count all legal Domineering positions. That is, as mentioned previously, we do not assume alternating play. To enumerate positions which may occur during alternating play, which we call play positions, we have to restrict to those terms in D m,n (x, y) where the difference in the powers of x and y is at most 1. Example 2.3. Using Example 2.2 we can see that the polynomial for the play positions on a 4 × 3 board is 46x 3 y 2 + 24x 2 y 3 + 100x 2 y 2 + 100x 2 y + 90xy 2 + 48xy + 9x + 8y + 1.
Setting x = y = 1 in this polynomial we get the total number of play positions, in this case 426.
The number of play positions on an n × n board are given in Table 1. We also include the ratio of all positions that are play positions, truncated to 5 decimals. Recall that the number of all positions, being equal to the number of matchings in a grid graph, are given in the OEIS sequence A028420.
The ratio computed in Table 1 gives a sense of the cost of considering all plays from a position, as is standard in combinatorial game theory, compared to considering only plays reachable in alternating play which is common in practice.
We expect that the ratio of play positions decreases as the board size increases because on larger boards there are an increasing number of ways to have a board with the number of dominoes for the two players differing by more than one. The ratios apparently do not follow an arithmetic or geometric sequence. We expect the ratios of play positions to general positions to approach 0. While it is interesting to consider how this ratio changes as the board size grows, it is also potentially interesting to observe how this ratio changes during play.

Non-Rectangular Boards
The techniques we use to find the generating polynomials of rectangular boards can be used to find the generating polynomials of non-rectangular boards as well.
We think of a non-rectangular board as being a rectangular board with missing squares and treat the missing squares as squares forced to be empty. For example, the board on the left in Figure 6 we think of as being contained in a 2 × 3 board with forced empty squares on the top left and top middle. ←→ 0 0 0 Figure 6. The equivalence of a non-rectangular board and a rectangular board with forced empty squares.
We will create a (bar-state) matrix R i for each row, then multiply these matrices to get the state matrix for the entire mosaic. In the board in Figure 6 the matrix for row 1 is R 1 = G 0,1 . For row 2 we will use G 0,3 , but restrict those columns which have 0 in the first and second position for the label. We denote this as R 2 = G 0,3 | 00 . For restrictions on bottom labels we will use a subscript. Example 3.2 shows this procedure but before that we consider rows with missing squares in the middle as in Example 3.1. If a row contains an missing square in the middle, the Kronecker product of the bar-state matrices of the shorter strips is the bar-state matrix for the row. The Kronecker product of two matrices A and B is If missing squares in a row break it into three or more parts we use the Kronecker product multiple times.
The tilings/play in the left part of the broken row are independent of those in the right part. The state-matrix for the whole row is a block matrix where the blocks are determined by possible labels of the first part of the row, while the order of the second part in each block is the same and determined by the possible top and bottom labels in that part. Thus, taking the Kronecker product of the matrix for the first strip with the matrix for the second strip is exactly what we need here. The matrix for this row is Finally, we multiply the matrices for each row such that the bottom row matrix is the left-most one, while the top row matrix is the right-most one, allowing us to match the top/column label of each row with the bottom/row label of the row above.
Using this technique for non-rectangular boards, we are thus able to find the generating polynomial counting positions that can be reached from a partially played board. We will do so in Example 3.4, where we will also use the following simplification for disjunctive sums.
Therefore, the generating polynomial of G + H is the product of those of G and H.
This proposition again emphasizes that it makes sense to enumerate all positions, not just play positions, due to disjunctive sums allowing a difference in the number of pieces larger than 1.
In this polynomial we see from the small degree terms the number of possible paths of the game from this position. The high degree terms give some sense of state at the end of the game provided play continues in such a way that the game lasts as long as possible. In this game Left played first; we see that Left (vertical) has played 6 times whereas Right has played 5 times and thus it is Right's turn from this position. Right has 21 possible moves. Right would likely have been happy to see terms in the polynomial where the degree of y is greater than the degree of x as these indicate the possibility of Right winning; of note then is the term 17x 10 y 11 with a relatively small coefficient. The actual winner of this game was Left.
Further, by setting x = y in all matrices, we are also able to count the number of matchings of a subgraph of a grid using this technique.

Counting Maximal Domineering Positions
Recall that a maximal Domineering positions is one in which neither player has any available moves. In this section we count maximal Domineering positions. We find the generating function where the board has size m×n and f (a, b) is the number of maximal Domineering positions with a Left (vertical) dominoes and b Right (horizontal) dominoes. We use F for the generating polynomial of the maximal positions as these correspond to the facets (maximal faces) of the simplicial complex representing the position. We will use the same technique as for the general Domineering positions of counting bar mosaics, multiplying the matrices, and then restricting to tilings, with only a few small differences. The tiles will be different so that with only using adjacency and boundary conditions we can force the tiling to be equivalent to a maximal position, i.e. no two empty spaces may be adjacent, and in turn a position corresponds to a unique tiling. The possible tiles in this case are given in Figure 8. For these tiles to form a maximal Domineering position a tiling has to satisfy the following conditions: (1) Adjacency condition: All shared edges of adjacent tiles have the same label.
(2) Boundary condition: The left and top boundary edges of the tiling have label 0; the right and bottom boundary edges have label 0 or 1.
In turn, any maximal Domineering position can be uniquely represented using a such a tiling. To decide between the different tiles representing domino halves one simply has to check for empty squares above and to the left. As an example, see the position and equivalent tiling in Figure 9. Note that the number of Left (vertical) dominoes is equal to the number of T 1 and T 2 tiles, and the number of Right (horizontal) dominoes is equal to the number of T 7 and T 8 tiles.
In this case we will use M as the label of the bar-state matrices to represent that we are counting maximal positions only. Also note that, since the bottom and right edge in a tiling are allowed to have both 0 and 1 as their labels, the generating polynomial will be a sum of entries. A detailed explanation is given in the proof of the following theorem.
Proof. The proof will be along the same lines as the proof of Theorem 2.1, thus some of the details will be omitted. The bar-state matrices count bar mosaics of length q. The matrix M k,q counts those bars with starting label k and ending label 0, while the matrix M ′ k,q counts those with starting label k and ending label 1.
The labels will be ternary strings, ordered lexicographically. Thus, the strings of length 2 are ordered as 00, 01, 02, 10, 11, 12, 20, 21, 22. The column labels of the matrix again correspond to the top label of the bar mosaic, while the row label is the bottom label. Each bar is represented by a monomial x a y b where a is the number of tiles 1 and 2 in the bar and b the number of tiles 7 and 8.
Each matrix has 9 blocks, which we label using roman numerals as shown in Figure 10, where we also show the corresponding top and bottom labels for the leftmost tile. In M 0,q+1 , we have a left label of 0. The only tile that meets the conditions for block I (and M 0,q+1 ) is T 9 . As the right edge label of T 9 is 2, the possible completions of our bar are given by M 2,q and so our block I entry is M 2,q .
The conditions for block II force T 10 as the starting tile and the entry is again M 2,q .
The conditions for block III force T 1 -giving the entry xM 0,q as T 1 has right label of 0. For block IV, tile T 0 is the only possible starting tile, giving entry M 1,q . For blocks V and VI we would need a tile with bottom label 1 and top label 1 or 2, respectively, and no such tiles exist so our entry is 0.
The conditions for block VII are top label of 0 and bottom label of 2; the only tile that works is T 3 and hence the entry is M 0,q . The conditions for block VIII are similar but with top label 1 so T 4 is the only tile that works.
The conditions for block IX are top label of 2 and bottom label of 2 which never occurs and thus our entry is 0.
In M 1,q+1 , we have a starting (left) label of 1. This forces: T 11 in block I; T 12 in block II; T 2 in block III; T 5 in block VII; and T 6 in block VIII. The remaining blocks have no possible tiles. Thus our entries for the matrix are as above.
In M 2,q+1 , we have a starting (left) label of 2. Thus the only possible tiles are T 7 and T 8 . In block I the only possible tile is T 7 , giving yM 0,q . In block II the tile is T 8 , giving yM 0,q . All other blocks have no possible tiles, so are 0.
Note that the arguments for M ′ 0,q+1 , M ′ 1,q+1 , and M ′ 2,q+1 are similar as the possible left-most tile is identical and only the ending label changes. Thus we skip these.
Now, restricting to tilings, we will only consider the bar mosaics of length n with left label 0 and right labels 0 or 1, so M 0,n + M ′ 0,n . As in the general positions case, stacking the bar mosaics corresponds to matrix multiplication. Thus the mosaics with all left labels 0 and right labels 0 or 1 are enumerated in (M 0,n + M ′ 0,n ) m . Finally, we need to restrict to top labels being all 0 and bottom labels 0 or 1. This means we need to sum the entries in the first column which are in rows numbered 1 + Taking the third power and summing the relevant entries, we get that F 3,2 (x, y) = 2x 2 y + 2x 2 + y 3 . Remark 4.3. As for the general positions case, we can also use these matrices to find the generating polynomial for non-rectangular boards. The technique is the same, thus we do not demonstrate it here.

Counting Left and Right Ending Positions
Similar to maximal positions, we are also able to count Left or Right ending positions by choosing the tiles appropriately so that the adjacency condition alone forces such an end. We will just be counting the Right ending positions in this section as it results in bar-state matrices of size 2 q × 2 q , while the Left ending positions, using a similar argument, would need bar-state matrices of size 3 q × 3 q (although fewer matrices). For Right ending positions, we may have two empty squares vertically adjacent as Left may potentially still play a domino. But we may not have two empty squares horizontally adjacent as Right cannot have any moves. To achieve this using the adjacency condition, the tiles we use are given in Figure 11. The two conditions for a tiling to be a Domineering Right end are: (1) Adjacency condition: All shared edges of adjacent tiles have the same label.
(2) Boundary condition: The left, top, and bottom edges of the tiling have labels 0; the right edge has labels 0 or 1. Figure 12 contains an example of a position and the corresponding tiling. We use RE for naming the bar-state matrices. The matrix RE k,q counts those bar mosaics of length q with starting label k and ending label 0, while the matrix RE ′ k,q counts those with starting label k and ending label 1.
We give no proof here as the argument is simply a combination of the arguments for the general and maximal positions.
In Table 2  The number of Right ending positions on a 1 × n board is recursively given by a 1 = 1, a 2 = 1, a 3 = 2, a n = a n−2 + a n−3 (the Padovan sequence shifted, OEIS sequence A000931). Consider the leftmost square: If it contains a domino, then the strip to the right of the domino can contain any Right ending position of length n − 2. If it is an empty square, then a domino has to be immediately to the right of it, and the remaining strip of length n − 3 can contain any Right ending position.
In the positions of shape m × 1 Right cannot play, thus all positions are Right ending. The sequence of these numbers is the Fibonacci sequence (OEIS sequence A000045) as every position is a combination of empty squares and Left dominoes.
It appears that the number of Right ending positions on an m × 2 board is given by the squared Fibonacci numbers (OEIS sequence A007598) and the number of positions on an m × 3 is given by the recursion a m = 4a m−1 + 4a m−2 − 4a m−3 − a m−4 (OEIS sequence A054894). Other sequences for the number of Right ending positions do not appear in the OEIS at this point.

Further Work
We suggest three broad avenues for continuing the work in this paper. One is to explore our original motivation and connect the enumeration of Domineering to questions of the algebraic structure of placement game positions. Secondly, we expect the methods demonstrated in this paper to be useful for other placement games played on grid-like boards (such as Cartesian products of cycles and paths). Lastly, there is the possibility of counting positions to analyze particular game situations either in theory or practice to develop better play strategies.