Notes on A030186 and A033505
N. J. A. Sloane 
Feb 13 2002

Let L_n = ladder graph P_1 X P_n
so that L_0, L_1, L_2 are

o    o---o    o---o---o
|    |   |    |   |   |   
|    |   |    |   |   | 
|    |   |    |   |   |  
o    o---o    o---o---o

respectively. 

The following result is well-known:

Claim: Let t(n) = number of matchings in L_n. Then t_n satisfies

     t(n) = 3t(n-1) + t(n-2) - t(n-3).                ... (*)

Proof.  Let a(n) be the number of matchings of L_n which
have at the right end just one branch, as shown here with === to denote
an edge, and xxx to denote a non-edge:

...o---o---o===o
   |   |   |   |   
   |   |   |   | 
   |   |   |   |  
...o---o---oxxxo

Similarly, let b(n) be the number of matchings of L_n which
have at the right end 

...o---o---o===o
   |   |   |   |   
   |   |   |   | 
   |   |   |   |  
...o---o---o===o

Let c(n) be the number of matchings of L_n which
have at the right end 

...o---o---oxxxo
   |   |   |   ||
   |   |   |   ||
   |   |   |   || 
...o---o---oxxxo

Let d(n) be the number of matchings of L_n which
have at the right end 

...o---o---oxxxo
   |   |   |   x
   |   |   |   x
   |   |   |   x 
...o---o---oxxxo

Then we have the following initial values:

n   0   1   2   3   4   5
a       1   3  10  32 103
b       1   2   7  22  71
c       2   7  22  71 228
d       2   7  22  71 228
t   2   7  22  71 228 733


and the obvious recurrences:

a(n) = a(n-1) + t(n-2)
b(n) = t(n-2)
c(n) = t(n-1)
d(n) = t(n-1)
t(n) = 2a(n) + b(n) + c(n) + d(n)

Also define t(-1) = 1.

Iterating we get 

t(n) = t(n-2) + 2*Sum_{i=-1..n-1} t(i)

and

t(n) = t(n-2) + 2a(n+1)

and

a(n) = Sum_{i=-1..n-2} t(i)

So if T(x) = 1 + 2x + 7x^2 + 22x^3 + ...

           = Sum_{i=-1..inf} t(i) x^(i+1)

then T satisfies

T = xT + 2xT/(1-x) + 1

Hence T = (1-x)/(1-3*x-x^2+x^3)

which implies (*).

The sequence {t(n)} is A030186 and {a(n)) is A033505.