A combinatorial interpretation of the
sequence 1, 1, 2, 6, 21, 77, ...

Reid Barton
REACH

October 26, 2002

What is the sequence?

The sequence $\{b_n\}_{n\ge 0}$ is defined by the recurrence relation

\begin{displaymath}b_0 = b_1 = 1, \quad b_{n+1} b_{n-1} = b_n^2 + b_n\hbox{ for $n \ge 1$ }\end{displaymath}

and begins 1, 1, 2, 6, 21, 77, 286, 1066, ....

Why is it interesting?

What is the combinatorial interpretation?

Construct an infinite ladder graph G shown below; then bn gives the number of paths in this graph from P0 to Pn moving only up and to the right (or moving to the left, in the drawing on the right).


               P_4     .                                          
                  +-+ .                                           
             P_3  | |.                     P_0 P_1 P_2 P_3 P_4    
                +-+-+-+                     *   *   *   *   *     
           P_2  | |/| |                    / \ / \ / \ / \ / \    
              +-+-+-+-+                   *   *   *   *   *   *   
         P_1  | |/| |                      \ / \ / \ / \ / \ /    
            +-+-+-+-+                   ... *---*---*---*---* ... 
       P_0  | |/| |                        / \ / \ / \ / \ / \    
          +-+-+-+-+                       *   *   *   *   *   *   
          | |/| |                          \ / \ / \ / \ / \ /    
          +-+-+-+                           *   *   *   *   *     
           .| |                                                   
          . +-+                                                   
         .

Why does it work?

I'll complete this section later, but for now, just an sketch of the proof: We prove the $3 \times 3$ determinant relation (1) by applying the Gessel-Viennot Theorem (ref?) to the graph above with left endpoints (P0, P1, P2) and right endpoints (Pn+4, Pn+3, Pn+2). The key point is that there exists exactly one way of joining P0 to Pn+4, P1 to Pn+3 and P2 to Pn+2 by three vertex-disjoint paths in G. This determinant relation together with the initial cases b0 = b1 = 1, b2 = 2, b3 = 6 (which can be checked by hand) uniquely determine the sequence bn.

What does it mean?



Reid W Barton
2002-10-26