I've spent the last couple of hours trying to figure out this problems. For some of you it may be easy, but I'm kind of a noob in combinatorics. Do you have any ideas?
On an 8x8 chessboard a pawn is located in the upper-left corner and can only move one square at a time down or to the right. How many different ways are there for it to reach the lower-right corner without making three consecutive downward moves?
On
There are two approaches. One way is to count the total number without restriction, which is ${14 \choose 7}=3432$ and subtract the ones that have three downs in a row. Naively, there are twelve places the three downs can start and ${11 \choose 4}=330$ ways to choose where the other four downs go in the series, so we would subtract $3960$. Unfortunately, this subtracts those with two runs of three downs, including those with a run of four downs, twice, so you need to add them back in. You can do that by the inclusion-exclusion principle, but it leads to a lot of cases in this problem.
The other approach is just to count them. I made three $8 \times 8$ grids in a spreadsheet. The first one has the number of ways to arrive at a cell with no downs at the end. The second has the number of ways to arrive at a cell with one down at the end and the third has the number of ways to arrive at a cell with two downs at the end. Each cell in the second copies the number from the top one corresponding to the cell above, because it is the number of ways to get to the cell above with no downs at the end, then add a down. Similarly for the bottom one feeding from the second. The top one has each cell with the sum of the numbers corresponding to the cell to the left because you can add a right to any string with any number of downs and have a string that ends in right that gets to that cell. I find $1016$ for an answer.
My spreadsheet is below. The $1-8$ on the borders refer to the rows and columns of the chessboard. The answer is then $393+357+266=1016$ where $393$ is the number of ways to get to the bottom right corner ending with right, $357$ is the number ending with one down, and $266$ is the number ending with two downs.
You can have the following moves: R, DR, DDR
Let $x_0, x_1,x_2$ represent the number of moves made R, DR, or DDR during the path to get to the bottom right (these will become repetition numbers for a multiset that we will permute).
You want $x_0+x_1+x_2=7$ because you want a total of 7 moves to the right. Additionally, you want $x_1+2x_2=7$ because you want a total of seven down movements.
For $x_2$ you can have the values $0,1,2,3$. Then for $x_1$, you have $x_1=7-2x_2$. And $x_0=7-x_2-x_1 = 7-x_2-(7-2x_2) = x_2$.
So, you have $x_0=x_2$ and $x_1 = 7-2x_2$. Since there are only 4 cases, we can just enumerate them.
Case $x_0=x_2=0$: Find the number of permutations of the multiset: $\{ DR\cdot 7\}$. There is only 1.
Case $x_0=x_2=1$: Find the number of permutations of the multiset: $\{ R\cdot 1, DR\cdot 5, DDR\cdot 1\}$. There are $\dfrac{7!}{1!5!1!}$.
Case $x_0=x_2=2$: Find the number of permutations of the multiset: $\{ R\cdot 2, DR\cdot 3, DDR\cdot 2\}$. There are $\dfrac{7!}{2!3!2!}$.
Case $x_0=x_2=3$: Find the number of permutations of the multiset: $\{ R\cdot 3, DR\cdot 1, DDR\cdot 3\}$. There are $\dfrac{7!}{3!1!3!}$.
I get a total of 393 possible paths that avoid three or more down moves. This only finds when the final move is an R. Next, apply a similar process for when the final move is RD, then RDD.
If the final moves are RD, then you have: R, DR, DDR, and $x_0+x_1+x_2=7$, $x_1+2x_2=6$. Now $x_0=x_2+1$ and $x_1=6-2x_2$. You can have values $0,1,2,3$ for $x_2$. That gives multisets:
$$\{R\cdot 1, DR\cdot 6\}, \{R\cdot 2, DR\cdot 4, DDR\cdot 1\}, \{R\cdot 3, DR\cdot 2, DDR\cdot 2\}, \{R\cdot 4, DDR\cdot 3\}$$
This adds $$\dfrac{7!}{1!6!}+\dfrac{7!}{2!4!1!}+\dfrac{7!}{3!2!2!}+\dfrac{7!}{4!3!}$$
Next, if it ends with RDD, you have R, DR, DDR and $x_0=x_2+2, x_1=5-x_2$, and $x_2=0,1,2$.
This gives multisets
$$\{R\cdot 2, DR\cdot 5\}, \{R\cdot 3, DR\cdot 3, DDR\cdot 1\}, \{R\cdot 4, DR\cdot 1, DDR\cdot 2\}$$
So, this final case adds: $$\dfrac{7!}{2!5!}+\dfrac{7!}{3!3!1!}+\dfrac{7!}{4!1!2!}$$
Now, the total is 1016.