A Particular Domino Tiling

Suppose that we first place one vertical domino so that it covers squares in Row 1 and Row 2. Then there are 51 squares in Row 1 that are not covered by the first domino.

Let the number of squares in Row 1 to the left of the first domino be $x$ and the number of squares in Row 1 to the right of the domino be $y$ . If the second domino placed does not cover Rows 1 and 2, then we have $x+y=51$ , so at least one of $x$ and $y$ is odd. We have a contradiction, because then these squares cannot be covered by horizontal dominoes.

Thus, the second domino covers the same rows as the first domino. The dominoes can either cover Rows 1 and 2, or Rows 2 and 3. They are symmetrical, so we count the number of dominoes satisfying the first case, and then multiply by 2 at the end.

If both dominoes cover Rows 1 and 2, then there are 50 remaining squares in Row 1. Let $2a$ be the number of squares in Row 1 to the left of the leftmost domino, let $2b$ be the number of squares in Row 1 between the two dominoes, and let $2c$ be the number of squares in Row 1 to the right of the rightmost domino, where $a, b, c$ are nonnegative integers. We have the "2" coefficients because they must be able to be tiled with horizontal dominoes, and thus are even. We also have $2a+2b+2c=50$ , or $a+b+c=25$ . Using the stars-and-bars argument, Stars and Bars , the number of such $a, b, c$ satisfying this equation is ${27 \choose 2}$ . Each possible ordered triple $a, b, c$ corresponds to a unique placement of the two dominoes, so we are done.

Multiplying our answer by 2 (to count the number of ways to place the dominoes so that they cover Rows 2 and 3), we have a final answer of $702$ .

Call the two vertical dominos Domino A and Domino B, where Domino A lies to the left of Domino B.

First, note that the two vertical dominos must occupy the same rows of the grid, i.e. it cannot be that one domino lies on rows 1 and 2 and another lies on rows 2 and 3; if this were the case, then the 51 remaining squares in row 1 would need to be tiled by horizontal 1x2 dominos, which would be impossible because 51 is odd. So both dominos must occupy the same rows of the grid.

If the vertical dominos lie on rows 1 and 2, they may only have an even number of columns between them because that space must be tiled by horizontal 1x2 dominos. Furthermore, there must be an even number of columns to the left of Domino A, by the same reasoning. Upon placing the two vertical dominos, there is only one tiling of horizontal dominos that will fill the remaining space.

Now we count the number of acceptable ways to place the two vertical dominos. In general, if there are 2n columns between Dominos A and B, there are 52-2n columns where the Domino A can lie so that Domino B still remains on the grid. In exactly half of these cases, the number of columns to the left of Domino A is even.

Thus, if there are 2n columns between Dominos A and B, there are 26-n acceptable placements of Dominos A and B. n can take integer values from 0 to 25, so the total is $\sum_{n=0}^{25} (26-n) = \frac {26 \cdot 27}{2} = 351$ .

We double this to account for the case where Dominos A and B lie in the second and third rows for a final result of $351 \cdot 2 = 702$ tilings.

Note that each horizontal domino spans 2 columns while each vertical domino span only 1 column. Each row has an even number of columns, so we cannot have a row which contains exactly 1 vertical domino (as that will cause the total number of columns spanned to be odd). Thus, each row must contain either 0 or 2 vertical dominoes, i.e. the 2 vertical dominoes span the same 2 rows.

We first consider the case where the 2 vertical dominoes span the first 2 rows. The only way that the last row can be covered with dominoes is by 26 adjacent horizontal dominoes. As for the first two rows, each row will be covered by 25 horizontal dominoes and the 2 vertical dominoes. In addition, these 2 rows will exhibit the same ordering of the horizontal and vertical dominoes since the vertical dominoes span the same columns on both rows and effectively determine the position of the horizontal dominoes. We can visualise this as 27 "positions" to be filled by 25 horizontal dominoes and 2 vertical dominoes. This gives $27 \choose 2$ possibilities for this case.

We now consider the other case where the 2 vertical dominoes span the last 2 rows. Using the same reasoning as the previous case, we can conclude that there are also $27 \choose 2$ possibilities for this case.

Thus, the total number of ways is ${27 \choose 2} \times 2 = \underline{702}$ .

There are attributes that each tile has, its vertical position and horizontal position.

For our vertical 2 by 1 tiles, there are only two possible vertical positions (touching the top and touching the bottom). So there must be 2 * 2 =4 possibilities for vertical positions. However, consider this: if one of the two tiles touch the top and the other touches the bottom, that implies each the top and the bottom rows are divided into an odd set and an even set of tiles by our two 2 by 1 vertical tiles. The rest of the board will be filled by horizontal tiles and the odd set in each the top and bottom row cannot be filled properly. So there are only two possibilities for vertical positions, both touching the top and both touching the bottom.

For the horizontal position, allow us to label all the columns 1, 2...52. Without loss of generality, tile A is placed before tile B. Tile A cannot be placed on an even number column because in two of three rows, there are an odd number of tiles to the left of tile A and cannot be filled completely. Hence, there are 26 positions for tile A. Similarly, tile B cannot be placed on an odd numbered row or else in two of the three rows, there are an odd number of tiles to be filled and cannot be filled completely. Thus, because A is always to the left of B, when A is column 1, there are 26 positions for B (which are even). When A is in column 3, there are 25 positions for B... When A is in column 51, B must be in column 52.

26 + 25 + 24 ... + 1 = (26+1)*26/2 = 351 possibilities for horizontal positioning.

351*2 = 702 combinations.

Let $A(n,k)$ be the number of ways to cover a $3 \times 2n$ grid with $2 \times 1$ dominoes, in which there are $k$ vertical ones. Clearly, $A(n,0) =1$ for all $n$ and $A(0,2) = 0$ . We want to find the recursion formula for $A(n,2), n \geq 1$ .

Now, let's focus on the first 2 columns.

$\underline{a}|\underline{b}$ $\underline{c}|\underline{d}$ $\underline{e}|\underline{f}$

i) If $a-b,c-d,e-f$ are filled with horizontal dominoes, then we are left with $2 \times 2(n-1)$ grid which we can tile in $A(n-1,2)$ ways.

ii) Otherwise there is at least $1$ vertical domino $V_1$ located within the first 2 columns. Take the leftmost one, it can only either be at $a-c$ or $c-e$ . Assume it is on $a-c$ (the $c-e$ case is similar, so we will multiply the result by two).

Now, the second vertical domino $V_2$ can't be put to cover row $2-3$ on any columns, since if it does, then there will be odd numbers of squares covered on row $1$ ( $2$ for each horizontal dominoes, and $1$ for $V_1$ while we must cover $2n$ squares. So it must be put to cover row $1-2$ .

Moreover, the number of squares between the two dominoes must be even, as those must be covered with solely horizontal dominoes. Thus, the possible columns to put $V_2$ are column $2,4,6,...,2n$ (there are $n$ choices), and we can simply put horizontal dominoes to cover the rest of the space.

Hence, from the two possible cases, the recursion formula is $A(n,2) = A(n-1,2)+2n, A(0,2) = 0$

And it's easy to conclude that $A(n,2) = 2\sum_{k=1}^n k = n(n+1)$

In this problem $n = 52/2 = 26$ , and so $A(26,2) = 26 \times 27 = 702$ .

Firstly, let name each row from top to bottom as $a$ , $b$ , $c$ and each column with a number $1$ to $52$ from left to right. $$ Now before we start counting the number of ways, let us establish some rules according to which the two vertical dominoes will be tiled. These are as follows: $$ 1 : There should be an even number of gaps between two dominoes. Like if we place a domino in column $1$ , then we must place the other in $2,4,6,8...$ ,otherwise, the horizontal dominoes would not fill the gap, as they occupy even number of horizontal squares. $$ 2 : Each pair of vertical dominoes should occupy the same two rows, viz. $ab$ and $bc$ . This is because conversely, there will be an odd number $(51)$ of squares in some row, which clearly cannot be tiled by horizontal dominoes.

$$ Now we start counting (and find a pattern). Because of rule $2$ , we can ignore any one row among $1$ and $c$ and count the number of ways and then in the end, double it. Say, we ignore the row $c$

$$ Suppose we place the first vertical domino in column $1$ in rows $a$ and $b$ . Then we must place the other in one of the column from the set $\{2,4,6,8...52\}$ This accounts for $26$ possibilities. We continue and now place the domino in column $2$ . But this arrangement will not be possible as in column $1$ there cannot be a horizontal domino. So now we realize that we cannot place a vertical domino in an even numbered column. Continuing in the same way, we find that when we place the vertical domino in column $3$ , we get $25$ possibilities for the other vertical domino. We then get a pattern. $$ So, ignoring a column, we get $26+25+24...+1$ = $\frac{27*26}{2}$ ways. As discussed above, we must double this count. So we get the final answer as $$ $\boxed {26*27 = 702}$ ways

My method was improper, but it works. Arbitrarily place the first vertical domino in bottom left corner. The next vertical domino must fall in an even column (in order to be able to place horizontal dominos between. Note that this domino can also be in rows 1,2 or rows 2,3.

For this first case, the vertical dominos can be in col1,col2 col1,col4 ... col1,col52 = 26 possibilities.

Next, we consider the first vertical domino in the 3rd column (no 2nd column or we wouldn't be able to fill the first with horizontal dominos. You will find the pattern is the same but now you only have 25 possibilities.

This pattern continues until you have 26+25+24+...+3+2+1 = 351 possibilities. But wait...that 2nd domino could go in rows1,2 or rows2,3. Thus, there are 2*351 = 702 ways to do this.

It may seem like there should be more (why not put the first domino in rows1,2 instead of setting it in rows2,3?). However, if you allow rotation of the board you'll notice that we've already counted all of those possibilities (they were our current possibilities upside down).

If one vertical domino is against the top but the other is not, then there are $51$ free columns on the top row. This can't be divided into units of $2$ , i.e. horizontal dominoes, so that configuration is impossible.

If two vertical dominoes are against the top, then the top row contains $2$ vertical and $25$ horizontal dominoes, so by the "stars-and-bars" approach, there are $\binom{27}{2}$ combinations.

The two vertical dominoes could be against the bottom row instead, so the total number is $\binom{27}{2} \times 2 = 27 \times 26 = \boxed{702}$ .

• At first, in the particular row, there 2 ways to chose a vertical domino.
• Secondly, the number of rows between two vertical dominoes is even; these two must be horizontal.
• Denote the S(n) be the number of ways in which the grid with 3 rows and 2n columns is tiled with 3n identical 2*1 dominoes and there are exactly two of the dominoes are vertical.
• And we will have S(n)=S(n-1)+2n; S(1)=2----> S(26)

Let an arbitrary vertical piece occupy rows 1 and 2. Clearly, a horizontal piece must fit below the vertical piece. Imagine trying to position a vertical piece in rows 2 and 3. In either row 2 or row 3, there will be an odd number of spaces between the vertical pieces. Because horizontal pieces take up 2 spaces at a time, this permutation is impossible. Therefore, the vertical pieces leave one row empty. The leftmost vertical piece must occupy an odd numbered column, again using the previous reasoning. Similarly, the rightmost piece must occupy an even numbered column. If the left piece is is column 1, there are ((52-2)/1)+1=26 possibilities for the right piece. Continuing this logic to column 51, there are 26+25+...+1=351 total permutations. The empty row could be either 1 or 3; 351x2=702 and we are done.

Let the number of tilings of a $2n \times 3$ grid using exactly $3n$ tiles such that exactly $2$ tiles are vertical be given by the function $f(n)$ for all positive integers $n$ . We wish to determine $f \left ( \frac{52}{2} \right ) = f(26)$ . We first make the following observations:

• There must be an even number of horizontal tiles between two vertical tiles. This holds true since the horizontal tiles cover exactly $2$ columns, and there must exist an integral number of horizontal tiles between the vertical tiles.

• If one of the vertical tiles covers the top two rows, the other vertical tile must also cover the top two rows (same case when one of the vertical tiles covers the bottom two rows). Proving this is tricky, but easy. Suppose we have tiled the space between the vertical tiles using some horizontal tiles. Consider the cell directly below the vertical tile covering the top two rows. This cell has to be covered by a horizontal tile. But note that if we put a horizontal tile there, we will get a discrepancy of two rows in the adjacent column. All these cells have to be filled using horizontal tiles, but we will always have such a discrepancy in the adjacent columns, which cannot be filled without a vertical tile. I advise the reader to draw a simple figure, which will make my arguments more clear.

We shall now try to find a relationship between $f(n)$ and $f(n+1)$ . If we increase $n$ by $1$ , we have two more columns and three more tiles. We see how many tilings are possible for such a grid.

Case $1$ The last two columns are covered entirely by three horizontal tiles
In this case, the first $2n$ columns must be covered with $3n$ tiles, out of which exactly $2$ are vertical. There are obviously $f(n)$ ways to do this. Note that the tiles cannot overlap, i.e any tile which is in the first $2n$ columns cannot cover any cell in the last two columns. This can be immediately deduced by drawing a picture, which shall show that if it does, we will require a vertical tile to cover the last two columns, contrary to our original assumption. Thus this case produces exactly $f(n)$ possibilities.

Case $2$ Exactly $1$ vertical tile is in the last two columns
Note that if the vertical tile is in the $(2n+1)^{th}$ column, there will be no possible tiling unless the other vertical tile is in the $(2n+2)^{th}$ columns. This can also be seen by drawing an image. The vertical tile must then be in the last column. From our first observation, the possible columns for the other vertical tiles are $2n-1$ , $2n-3$ , $\cdots$ , $1$ . There are exactly $n-1$ such numbers. For each such arrangement the vertical tiles can either cover the first two rows ore the bottom two rows, giving two more possibilities. This case gives rise to $2(n-1)$ possibilities.

Case $3$ All the vertical tiles are in the last two columns
In this case, similar arguments show that we cannot have overlapping of tiles from the first $2n$ columns and the last two columns. This case will give rise to exactly $f(1)$ possibilities. An easy check shows that $f(1)=2$ , so this case gives $2$ more possibilities.

Summing them up, we obtain the recursion $f(n+1)= f(n)+2n$ . Solving this recursion, we obtain $f(n)= 2(1 + 2 + \cdots + n) = 2 \frac{n(n+1)}{2} = n(n+1)$ Our desired answer is $f(26)= 26 \times 27 = \boxed{702}$ .

Answer should be 702*2=1404. Because if we keep the dominoes reversed then? Rotation and reflections are counted.