sequence 1, 1, 2, 6, 21, 77, ...

**Reid Barton
REACH**

**October 26, 2002**

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

- It gives the numbers appearing in the ``number fence'' table

where the top two rows are filled with ones and each number is the determinant of the matrix formed by the four numbers touching it. In other words, the matrix satisfies the recurrence

It turns out that if we apply this recurrence relation to a table whose top two rows are filled with formal indeterminates

then the entries in this table are (apparently) Laurent polynomials in the*x*_{j}and*y*_{j}in which every monomial has coefficient +1. Thus*b*_{n}counts the number of monomials in this polynomial. - It satisfies the relation

This property is actually equivalent to the recurrence relation above; see David Speyer's writeup on the determinant recurrence. - We can write
*b*_{n}=*c*_{n}*c*_{n+1}, where is a new sequence defined by

which begins 1, 1, 1, 2, 3, 7, 11, 26, .... This sequence counts several things: for example,*c*_{2n}is the number of domino tilings of a rectangle. Again, see Speyer's writeup for more details. - The sequence
also satisfies a linear recurrence

*b*_{n}= 5*b*_{n-1}- 5*b*_{n-2}+*b*_{n-3}

and hence has a rational generating function

Construct an infinite ladder graph *G* shown below; then *b*_{n} gives
the number of paths in this graph from *P*_{0} to *P*_{n} 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 | |/| | / \ / \ / \ / \ / \ +-+-+-+-+ * * * * * * | |/| | \ / \ / \ / \ / \ / +-+-+-+ * * * * * .| | . +-+ .

- The one-dimensional nature of the paths counted by
*b*_{n}makes it clear that the sequence, originally defined by a quadratic recurrence, will in fact satisfy a linear recurrence. Looking at the drawing of*G*on the left, if we define a 5-tuple*p*_{n}as the number of paths from*P*_{0}to each of the five vertices on the row containing*P*_{n}, then there exists a fixed matrix*M*such that*p*_{n+1}=*Mp*_{n}; the Cayley-Hamilton theorem then tells us that the*p*_{n}satisfy a linear recurrence. - As mentioned above,
*b*_{n}counts the monomials appearing in the Laurent polynomials given by the ``number fence'' recurrence ; a combinatorial understanding of the sequence is thus a natural first step in understanding the combinatorics of this recurrence relation.