Counting the number of restricted forests on the Möbius ladder of length n OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn.

The Challenge

The challenge is to write a program that takes an integer as an input n &gt; 1 and returns A020872(n), the number of restricted forests on the Möbius ladder Mn. This is code-golf, so shortest code wins. 
(An ulterior motive is to perhaps extend the length of this sequence by a bit.)

Definitions

A restricted forest is a partition of the graph such that each part is either a (undirected) path or an isolated vertex.

The Möbius ladder Mn is a graph which can be thought of the 2n-gon with diagonals drawn between all opposite vertices.

Example

Here are the 34 restricted forests on M2 (a square with diagonals drawn). Notice that the first graph is partitioned into four isolated vertices, the second is partitioned into one path and two isolated vertices, etc.
CJam (58 56 chars)

Some characters unprintable, and one is a tab which will be mangled by the StackExchange software:

"¶3¬î¿Á·    7ÛÈmÈÚÚ¡"256b454b212f-{__W%.*A&lt;1b+}qi*-4=


Online demo. This will run online for n=400 in about three seconds.

Encoded by xxd:

0000000: 22b6 0233 93ac eebf c1b7 0609 3794 dbc8  "..3........7...
0000010: 6dc8 1015 dada a122 3235 3662 3435 3462  m......"256b454b
0000020: 3231 3266 2d7b 5f5f 5725 2e2a 413c 3162  212f-{__W%.*A&lt;1b
0000030: 2b7d 7169 2a2d 343d                      +}qi*-4=


Explanation

A Möbius ladder is basically a ladder with two extra edges. Given a restricted forest on a ladder, it can be lifted to between 1 and 4 restricted forests on the Möbius ladder. The edges can be added provided that doesn't create a vertex of degree 3 or a cycle. The degrees of the four corners and their interconnections form 116 classes of restricted forest on the ladder, although some of them are equivalent due to symmetries of the rectangle. I wrote a program to analyse the extensions of a ladder of length n to one of length n+1, and then merged the classes into 26 equivalence classes. This gives a closed form

$$\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1\end{bmatrix}^T
\begin{bmatrix}
    1 &amp; 2 &amp; 2 &amp; 0 \\
    1 &amp; 2 &amp; 1 &amp; 1 \\
    2 &amp; 3 &amp; 4 &amp; 1 \\
    0 &amp; 0 &amp; 1 &amp; 0 \\
\end{bmatrix}^{n-2}
\begin{bmatrix} 0 \\ 1 \\ 0 \\ 0\end{bmatrix} + $$

$$\begin{bmatrix} 2 \\ 2 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 2 \\ 2\end{bmatrix}^T
\begin{bmatrix}
    2 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\
    1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\
    0 &amp; 0 &amp; 2 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\
    1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
    0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
    3 &amp; 2 &amp; 2 &amp; 1 &amp; 1 &amp; 2 &amp; 1 &amp; 4 &amp; 2 \\
    0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 \\
\end{bmatrix}^{n-2}
\begin{bmatrix} 0 \\ 0 \\ 2 \\ 2 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0\end{bmatrix} + $$

$$\begin{bmatrix} 1 \\ 2 \\ 4 \\ 4 \\ 1 \\ 1 \\ 3 \\ 2 \\ 2 \\ 2 \\ 3 \\ 4 \\ 4\end{bmatrix}^T
\begin{bmatrix}
    0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
    0 &amp; 2 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 1 &amp; 2 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\
    1 &amp; 0 &amp; 0 &amp; 4 &amp; 0 &amp; 0 &amp; 3 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 2 &amp; 1 &amp; 0 \\
    0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
    1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 1 &amp; 2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 \\
    0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
    0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 2 &amp; 2 &amp; 0 \\
    0 &amp; 2 &amp; 3 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 2 &amp; 1 &amp; 0 &amp; 1 &amp; 2 &amp; 4 \\
\end{bmatrix}^{n-2}
\begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 2 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 2 \\ 1\end{bmatrix}$$

so values can be computed fast by taking three linear recurrences and then adding them, but this isn't looking very golfy.

However, if we take the irreducible factors of the various characteristic polynomials and multiply together one of each (ignoring multiplicity) we get a polynomial of degree 10 which gives a working single linear recurrence.

Constructive approach (58 chars)

qi:Q2*,Wa*e!{Wa/{_W%e&lt;}%$}%_&amp;{{,1&gt;},2few:~{:-z(Q(%}%0-!},,


Online demo. It will run online for n=2 without problems and for n=3 with a bit of patience. For n=1 it crashes, but since OP has chosen to exclude that case from the requirements it's not a fundamental problem.

Dissection

qi:Q          e# Take input from stdin, parse to int, store in Q
2*,Wa*e!      e# Take all permutations of (0, -1, 1, -1, 2, -1, ..., -1, 2*Q-1)
{             e# Map to canonical form...
  Wa/         e#   Split around the -1s
  {_W%e&lt;}%    e#   Reverse paths where necessary to get a canonical form
  $           e#   Sort paths
}%
_&amp;            e# Filter to distinct path sets
{             e# Filter to path sets with valid paths:
  {,1&gt;},      e#   Ignore paths with fewer than two elements (can't be invalid; break 2ew)
  2few:~      e#   Break paths into their edges
  {:-z(Q(%}%  e#   The difference between the endpoints of an edge should be +/-1 or Q (mod 2Q)
              e#   So their absolute values should be 1, Q, 2Q-1.
              e#   d =&gt; (abs(d)-1) % (Q-1) maps those differences, and no other possible ones, to 0
              e#   NB {:-zQ(%}% to map them all to 1 would save a byte, but wouldn't work for Q=2
  0-!         e#   Test that all values obtained are 0
},
,             e# Count the filtered distinct path sets




A more efficient version takes 98 bytes:

qi2*:Q{a{__0=[1Q2/Q(]f+Qf%_&amp;1$-\f{+E}~}:E~}/]{_W%&gt;!},:MW=0{_{M\f{__3$_@&amp;@:e&lt;@|^{=}{^j}?}1b}{,)}?}j


Online demo

This builds the possible paths by depth-first search, then uses a memoised function which counts the possible restricted forests for a given set of vertices. The function works recursively on the basis that any restricted forest for a given non-empty set of vertices consists of a path containing the smallest vertex and a restricted forest covering the vertices not in that path.