Return to Answer

CJam (58 chars)

qi:Q2*,Wa*e!{Wa/{_W%e<}%$}%_&{{,1>},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.

Also at 58 chars, but some unprintable:

"ÔrfxO÷·U nf"256b454b212f-A/~:B;{_B.*1b+(;}qi*6=

Online demo. This will run online for n=1000 in a second or two.

0000000: 22d4 7266 784f f7b7 9296 9055 206e 078a  ".rfxO.....U n..
0000010: 829d 9f86 661f 2232 3536 6234 3534 6232  ....f."256b454b2
0000020: 3132 662d 412f 7e3a 423b 7b5f 422e 2a31  12f-A/~:B;{_B.*1
0000030: 622b 283b 7d71 692a 363d                 b+(;}qi*6=

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.

Further notes: a closed form is

$$\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1\end{bmatrix}^T \begin{bmatrix} 1 & 2 & 2 & 0 \\ 1 & 2 & 1 & 1 \\ 2 & 3 & 4 & 1 \\ 0 & 0 & 1 & 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 3 & 2 & 2 & 1 & 1 & 2 & 1 & 4 & 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 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 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 4 & 0 & 0 & 3 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 0 \\ 0 & 2 & 3 & 0 & 1 & 1 & 0 & 2 & 1 & 0 & 1 & 2 & 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.

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<1b+}qi*-4=

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

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<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 & 2 & 2 & 0 \\ 1 & 2 & 1 & 1 \\ 2 & 3 & 4 & 1 \\ 0 & 0 & 1 & 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 3 & 2 & 2 & 1 & 1 & 2 & 1 & 4 & 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 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 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 4 & 0 & 0 & 3 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 0 \\ 0 & 2 & 3 & 0 & 1 & 1 & 0 & 2 & 1 & 0 & 1 & 2 & 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<}%$}%_&{{,1>},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.

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.

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

Also at 58 chars, but some unprintable:

"ÔrfxO÷·U nf"256b454b212f-A/~:B;{_B.*1b+(;}qi*6=

Online demo. This will run online for n=1000 in a second or two.

Encoded by xxd:

0000000: 22d4 7266 784f f7b7 9296 9055 206e 078a  ".rfxO.....U n..
0000010: 829d 9f86 661f 2232 3536 6234 3534 6232  ....f."256b454b2
0000020: 3132 662d 412f 7e3a 423b 7b5f 422e 2a31  12f-A/~:B;{_B.*1
0000030: 622b 283b 7d71 692a 363d                 b+(;}qi*6=

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.

Further notes: a closed form is

$$\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1\end{bmatrix}^T \begin{bmatrix} 1 & 2 & 2 & 0 \\ 1 & 2 & 1 & 1 \\ 2 & 3 & 4 & 1 \\ 0 & 0 & 1 & 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 3 & 2 & 2 & 1 & 1 & 2 & 1 & 4 & 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 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 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 4 & 0 & 0 & 3 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 0 \\ 0 & 2 & 3 & 0 & 1 & 1 & 0 & 2 & 1 & 0 & 1 & 2 & 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.