Permutation & Combination : 002

How many paths are there from A to B which do not pass through any vertex twice and which move only downwards or sideways, never up?

Answer
2⁶6! = 46080
 
Solution
If the large triangle has side n and top vertex A, let a_n be the number of ways of getting from A to the bottom row (the path stops as soon as it gets to the bottom row). Note that a_n is also the number of ways of getting from A to the bottom left-hand vertex, because having reached the bottom row there is only one allowed path to the bottom left-hand vertex. Obviously, a₁ = 2.
Now consider an+1. There are an ways to get to the bottom row but one. Now there is just one way of getting to any vertex on the bottom row and there are then 2 ways to get to the row below. So a_n+1 = 2(n+1)a_n. Hence a₆ = 2⁵6!a₁ = 2⁶6!.