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 8×8 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?
Best Answer
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.