Notes on A030186 and A033505 N. J. A. Sloane Feb 13 2002 Let L_n = ladder graph P_1 X P_n so that P_0, P_1, P_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.