This the problem from the test and I'm stuck at one part.
Matt will arrange four identical, dotless dominoes (shaded 1 by 2 rectangles) on the 5 by 4 grid to the right so that a path is formed from the upper left-hand corner A to the lower right hand corner B. In a path, consecutive dominoes must touch at their sides and not just their corners. No domino may be placed diagonally; each domino covers exactly two of the unit squares shown on the grid. One arrangement is shown. How many distinct arrangements are possible, including the one shown?
So do I just find all the numbers of vertical and horizontal possible and then multiply by the number of arrangements of each, or should I go a different route?
$\endgroup$ 24 Answers
$\begingroup$You need to traverse $7$ cells (you start from $A$, so that cell is a given). You need to make exactly $3$ movements rightwards in total (otherwise we won't reach point $B$'s x-coordinate).
So we are looking for the number of ways we can order $$rrrdddd$$ where $r$ denotes going right, and $d$ denotes going down.
That gives $$\binom 73 = 35$$ ways.
$\endgroup$ 1 $\begingroup$I’m not sure what you had in mind, but here is what I did to get the answer:
The trick here is that the dominos don’t actually restrict the problem much. In fact, any walk from the top left corner to the bottom right corner using only steps to the right and down gives a unique domino path, and vice versa. (I am leaving some of these details out. Showing this bijection isn’t hard, but is a bit technical.)
Thus we need to only count the number of such walks. We can encode such a walk as a sequence of R’s and D’s(right and down steps.) We need to take seven total steps, three to the right, so we get that there are a total of $$\binom{7}{3}=35$$ ways to do this.
$\endgroup$ 1 $\begingroup$You have to get from A to B using only steps right and down. The number of paths to a given square is the number of paths to the one just above (from which you step down) and the number of paths to the one just to the left (from which you step right). This sounds like Pascal's triangle.
$\endgroup$ $\begingroup$I would consider the cells that you can get at after placing 1,2,3, and 4 dominoes on the way to the lower right.
So, after 1 domino you can be in (1,2) (row 1, column 2), or (2,1), and there is only 1 way to get to each.
After 2 dominoes, you can be in (1,4) (only 1 possibility to get there, through (1,2)), (2,3) (3 ways to get there: 2 via (1,2), and 1 through (2,1)), (3,2) (3), or (4,1) (1)
After 3 dominoes, it's (3,4) (1+2*3+3=10), (4,3) (by symmetry, also 10), or (5,2) (2+3=5)
So, after 4, you have to be in (5,4), and there are 10+2*10+5=35 paths to get there.
Here's a graphic that will help, indicating in how many ways you can get to the various cells:
\begin{array}{|c|c|c|c|} \hline &1&&1\\ \hline 1&&3&\\ \hline &3&&10\\ \hline 1&&10&\\ \hline &5&&35\\ \hline \end{array}
$\endgroup$ 4
