Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
I think your problem is that you're treating picking the "A" as one of two choices, when there's really nothing you can do about it. Two routes to a B and two from each B to an R gives $2*2 = 4$ ways. –  El'endia Starman May 23 '11 at 3:33
1  
Please don't add "SOLVED" to the subject. The main site notes that an answer has been accepted, that is more than sufficient. –  Arturo Magidin May 23 '11 at 4:24
    
@El'enida Thanks. I think my problem is formulating the problem in words and then try to solve it. I guess combinatoric problems are best solved intuitively. –  kuch nahi May 23 '11 at 4:25
    
@Arturo Ok. And thanks for answering. –  kuch nahi May 23 '11 at 4:26
add comment

2 Answers 2

up vote 9 down vote accepted

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.$$

share|improve this answer
    
It was quite clever to have reformulated it this way. Inspired by the class of problems you've exposed this to, another restatement could be: number of non-negative solutions of $x_1+\cdots +x_6=5$ (based on the first grid you have drawn) –  kuch nahi May 23 '11 at 4:03
2  
+1 though I am not sure why you need to rewrite the pattern: in the original you need 5 moves south-west and 5 moves south-east, and can choose these in ${5+5 \choose 5}=252$ different orders. –  Henry May 23 '11 at 6:39
    
@Henry: I've seen the "get from bottom left to top right along this rectangular grid" problem far more times than I've seen the "spell this letter from this grid" problem. Hence the conversion to something that might be more familiar (assuming my experience is not singular). –  Arturo Magidin May 23 '11 at 16:17
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.