Number of Paths in a Triangle

Question

I recently encountered a much more difficult variation of this problem, but realized I couldn't generate a solution for this very simple case. I searched Stack Overflow but couldn't find a resource that previously answered this.

You are given a triangle ABC, and you must compute the number of paths of certain length that start at and end at 'A'. Say our function f(3) is called, it must return the number of paths of length 3 that start and end at A: 2 (ABA,ACA).

I'm having trouble formulating an elegant solution. Right now, I've written a solution that generates all possible paths, but for larger lengths, the program is just too slow. I know there must be a nice dynamic programming solution that reuses sequences that we've previously computed but I can't quite figure it out. All help greatly appreciated.

My dumb code:

def paths(n,sequence):
    t = ['A','B','C']
    if len(sequence) < n:
        for node in set(t) - set(sequence[-1]):
            paths(n,sequence+node)
    else:
        if sequence[0] == 'A' and sequence[-1] == 'A':
            print sequence

Answer 1

Let PA(n) be the number of paths from A back to A in exactly n steps. Let P!A(n) be the number of paths from B (or C) to A in exactly n steps.

Then:

PA(1) = 1
PA(n) = 2 * P!A(n - 1)

P!A(1) = 0
P!A(2) = 1
P!A(n) = P!A(n - 1) + PA(n - 1)
       = P!A(n - 1) + 2 * P!A(n - 2) (for n > 2) (substituting for PA(n-1))

We can solve the difference equations for P!A analytically, as we do for Fibonacci, by noting that (-1)^n and 2^n are both solutions of the difference equation, and then finding coefficients a, b such that P!A(n) = a*2^n + b*(-1)^n.

We end up with the equation P!A(n) = 2^n/6 + (-1)^n/3, and PA(n) being 2^(n-1)/3 - 2(-1)^n/3.

This gives us code:

def PA(n):
    return (pow(2, n-1) + 2*pow(-1, n-1)) / 3

for n in xrange(1, 30):
    print n, PA(n)

Which gives output:

1 1
2 0
3 2
4 2
5 6
6 10
7 22
8 42
9 86
10 170
11 342
12 682
13 1366
14 2730
15 5462
16 10922
17 21846
18 43690
19 87382
20 174762
21 349526
22 699050
23 1398102
24 2796202
25 5592406
26 11184810
27 22369622
28 44739242
29 89478486