The word ABRACADABRA is written as a triangle, one letter per row, the first row holding one A, the second...

combinatorics/abracadabra New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

The word ABRACADABRA is written as a triangle, one letter per row, the
first row holding one A, the second two B's, and so on down to eleven
A's.  Starting from the top A, and moving each time to one of the (up
to three) adjoining letters in the row below, how many ways are there
to spell ABRACADABRA?

[ Editor: problem statement reconstructed from the postings. ]

Show solution

dushoff@gate.sinica.edu.tw (Jonathan Dushoff) wrote:
>Using the rules suggested by Dave Gates, there are 17,303 ways to spell
>abracadabra.

The arithmetic brute force method works, and is not too cumbersome
here.  Here's the pyramid, with each number representing the total
possible paths which end in it.  Each is the sum of the three numbers
above (or two, or one):

A                                              1
B                                         1    1
R                                    1    2    2
A                               1    3    5    4
C                          1    4    9   12    9
A                     1    5   14   25   30   21
D                1    6   20   44   69   76   51
A            1   7   27   70  133  189  196  127
B        1   8  35  104  230  392  518  512  323
R      1 9  44 147  369  726 1140 1422 1353  835
A  1 10 54 200 560 1242 2235 3288 3915 3610 2188 --> which sums to 17,303

-- Tim Firman <firman@dabulls.chem.wisc.edu>

For a word of length n+1, the bottom row of the table will be
the first (positive) half of the sequence of coefficients of
(x^2-1)*(x^2+x+1)^n, while the total will be the x^n coefficient of
(x+1)*(x^2+x+1)^n.  These totals comprise sequence 5773 in N.J.A.Sloane's
online sequence encyclopedia  http://www.research.att.com/sequences,
which gives the generating function  [sqrt((1+t)/(1-3t)) - 1] / 2
for the n-th term.

-- Noam D. Elkies <elkies@math.harvard.edu [Editor: "harvard:edu" in the original]>