We want to get a recurrence relation, and possibly an explicit formula for the perfect matchings of a 2 x 2 x n graph.
Claim: The number of perfect matchings of a 2 x 2 x n graph is given by the explicit formula
a(n)= (1/3)[(-1)^(n+1) + ((7+4*sqrt(3))/2)*(2+sqrt(3))^n + ((7-4*sqrt(3))/2)*(2-sqrt(3))^n]
and the recurrence
a(n+3) = 3*a(n+2) + 3*a(n+1) - a(n) for n greater than 2, with a(0)=2.
Proof:
First, define A(x) to be the generating function for 2 x 2 x n graphs so A(x) = a(0) + a(1)x + a(2)x^2 + ... = 2 + 9x + 32 x^2 +... where a(n) is the number of perfect matchings of a 2 x 2 x n graph.
Define B(x) to be the generating function for the 2 x 2 x n graph with two adjacent external vertices removed. Then B(x) = b(0) + b(1)x + b(2)x^2 + ... = 1 + 3x + 12x^2 + ... where b(n) is the perfect matchings of a 2 x 2 x n graph with two adjacent external vertices removed.
Claim:
b(n) = b(n-1) + a(n-1), and
a(n) = 2*a(n-1) + 4*b(n-1) + a(n-2).
Proof:
This can be proved pictorially. The first two pictures on the left represent the proof of the first equation. The purple X represents any surface so that we can remain general, and the four red vertices are contained on that surface. There are two ways we can choose the edge of the blue vertex that is further back. If we choose it to be contained in the edge with the other blue vertex, it forces no other sides and the number of perfect matchings is a(n-1). If we choose it to be contained in the edge with the adjacent purple vertex, our choice forces the other green edge that is closer to us in the picture. The number of perfect matchings of the leftover graph is an a(n-1) box with two adjacent external vertices removed, also known as b(n-1). Thus, b(n) = b(n-1) + a(n-1).
The next seven pictures represent the second recurrence relation. The fact that these green edges count all of the perfect matchings of the graph is left to the reader. The first three graphs we get by forcing the back, top blue edge to its adjacent purple vertex give graphs of perfect matchings of a(n-2), b(n-1), and b(n-1) respectively. The next two graphs, obtained by forcing the back, top blue edge to be contained in the edge with the back, bottom blue edge gives graphs of a(n-1) and b(n-1) respectively. The last two graphs, obtained by forcing the last possible edge, gives subgraphs of b(n-1) and a(n-1) respectively. Since these seven graphs contain all the perfect matchings, then a(n) = 2a(n-1) + 4b(n-1) + a(n-2), and the generality of the proof is in tact since we did not do anything to the red vertices.
Now since we have these two recurrences, we can multiply each term by x^n and sum from n=0 to infinity. Since we have A(x) and B(x) already as functions of a(n)x^n and b(n)x^n with n being summed from zero to infinity, we can reindex our terms in our new summed recurrence equation to solve for A(x) and B(x)[since we have two equations and two unknowns]. I will leave the algebra to the reader. We have
A(x) = (2+3x+x^2)/(1-3x-3x^2+x^3) and
B(x) = 1/(1-3x-3x^2+x^3).
We are only interested in A(x), but I post the generating function of B(x) for readers who are interested. Then the denominator of the generating function of A(x) tells us that the recurrence of the sequence is a(n+3) = 3a(n+2) + 3a(n+1) - a(n). Since the power of the numerator is smaller than the power of the denominator, we can conclude that the recurrence starts on the first term possible (in this case a(3)). Also, we can obtain the roots of the denominator of A(x) to get a general formula for a(n). The general formula is
a(n) = ar^n + bs^n +ct^n, where r, s, and t are the three roots of the polynomial. Since these roots are -1, 2+sqrt(3), and 2-sqrt(3), we have a(n) = a(-1)^n + b(2+sqrt(3))^n + c(2-sqrt(3))^n. Knowing that a(0) = 2, a(1) = 9, and a(2) = 32, we can solve for a, b, and c, yielding
a(n)= (1/3)[(-1)^(n+1) + ((7+4*sqrt(3))/2)*(2+sqrt(3))^n + ((7-4*sqrt(3))/2)*(2-sqrt(3))^n]
which is our desired equation.
