Number of ways of spelling Abracadabra in this grid

This is embarrasingly, the first problem in notes on introductory combinatorics by Polya and Tarjan. (Solved, but I havent looked).

Problem statement: Find the number of ways of spelling "abracadabra" always going from one letter to the adjacent.

$$A$$ $$B \quad B$$ $$R \quad R \quad R $$ $$A\quad A \quad A \quad A $$ $$C\quad C\quad C\quad C\quad C$$ $$A\quad A \quad A \quad A \quad A\quad A$$ $$D\quad D\quad D\quad D\quad D$$ $$A\quad A \quad A \quad A $$ $$B \quad B \quad B $$ $$R \quad R$$ $$A$$

I got a very improbable answer of $2^{25}$ so I tried a simpler case to understand it.

Starting at the northmost A there are two routes. At each of the two B's on the second row there are $2$ routes, so uptil this point

$$A$$ $$B \quad B$$ $$R \quad R \quad R $$

there should be $2^3$ ways to get the three letter word "ABR" but on manually counting the number of ways is just 4 (LL, LR, RR, RL where R=right/L=left). What is wrong with my approach? More precisely, where have I overcounted?

Edit: I understood my problem. I used the product rule instead of the sum rule. I think I will stop paying attention to these "rules" as they are hindering my problem solving anyway. (I have asked a previous questions on the subject)


This is essentially the same as this problem. Start by rewriting your array as a square, with the top now at the bottom left, and the bottom now at the top right: $$\begin{array}{cccccc} A & D & A & B & R & A\\ C & A & D & A & B & R\\ A & C & A & D & A & B\\ R & A & C & A & D & A\\ B & R & A & C & A & D\\ A & B & R & A & C & A \end{array}$$ You want to get from the bottom left to the top right, using only moves right or up. A simple thing is to note that there is only one way to get to the bottom left, and at any point, the number of ways to get to a point is the sum of the number of ways to get to the point directly below and the number of ways to get to the point directly left. This gives: $$\begin{array}{cccccc} 1 & 6 & 21 & 56 & 126 & 252\\ 1 & 5 & 15 & 35 & 70 & 126\\ 1 & 4 & 10 & 20 & 35 & 56\\ 1 & 3 & 6 & 10 & 15 & 21\\ 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 1 & 1 & 1 & 1 & 1 \end{array}$$ giving $252$ ways.

Alternatively, in the end, you must make five moves right and five moves up. Your only decisions to make is when you make the moves up. You have six locations (before all the moves right, between any two moves right, and after all moves right), and you have to choose them, allowing repetitions and without caring about the order. That is, you want to count combinations with repetitions, selecting six from seven possibililties. The way to make $r$ choices from $n$ possibilities, allowing repetitions and where order does not matter, is $\binom{n+r-1}{r}$, so in this case we have $$\binom{6+5-1}{5} = \binom{10}{5} = \frac{10!}{5!5!} = 252.$$


well, i think that you have to use the fundamental counting principle till the end, giving 2^9, and then subtract 8 since at the sides, since if you pick a path that goes to one of the A's on the very edge of the 6th row, you do not have a choice of path. Same if you pick one of the D's on the edge of row 7. This gives 8 paths that one picked, are not allowed to change. For example, if we took a path that took us to an A at the edge of row 6, then there would be no choice. Same for the rest of the letters in rows 7,8,9. After that is taken care of, you divide by 2 since in the way we used the fundamental counting principle, ABRACADABRA is the same as ARBADACARBA, so we divide by two to get the EXACT number of ways. This is (2^9-8)/2. This results in the correct answer, 252