How many ways can $N$ edges be added to a labeled cycle graph with $2N$ vertices to produce a simple cubic graph? Equivalently, how many functions on the set $\{0, 1, 2, ..., 2N-1\}$ satisfy the following conditions?


*

*For all $n$, $f(n) \neq n$.

*For all $n$, $f(n) \neq n+1 ~(\text{mod } 2N)$.

*For all $n$, $f(f(n)) = n$.


If the answer to this question is denoted $F(N)$, I've determined that $F(2) = 1$, $F(3) = 4$, and $F(N) \le \frac{(2N-3)(2N-3)!}{2^{N-2}(N-2)!}$. (Note that the answer is $\frac{(2N)!}{2^N N!}$ if you remove condition 2.) But I don't know how to determine a general solution for $F$.
 A: You can use the principle of inclusion-exclusion.  Let $s(i_1,i_2,\ldots,i_k)$ denote the number of ways to partition $2N$ vertices into $N$ unordered pairs if $\{i_1,i_1+1\}$, $\{i_2,i_2+1\}$, ..., $\{i_k,i_k+1\}$ (with arithmetic performed mod $2N$) are required to be among the pairs.  Observe that this quantity is zero if $i_k=i_j+1 \pmod{2N}$ for any $j$, $k$, since $\{i_j,i_j+1\}$ and $\{i_j+1,i_j+2\}$ cannot both be pairs.  Then the number of partitions in which none of the pairs are edges of the cycle graph is
$$
s()-\sum_i s(i)+\sum_{i&ltj}s(i,j)-\sum_{i&ltj&ltk}s(i,j,k)+\ldots.
$$
Now if $s(i_1,i_2,\ldots,i_k)$ is nonzero then it equals $\dfrac{(2N-2k)!}{2^{N-k}(N-k)!}=(2N-2k-1)!!$ since the pairings are fixed for $2k$ of the vertices, which leaves $2N-2k$ vertices to pair up.  The number of ways of choosing $\{i_1,i_2,\ldots,i_k\}$ so that $i_k\ne i_j+1\pmod{2N}$ holds for all $j$, $k$, is $\binom{2N-k}{k}+\binom{2N-k-1}{k-1}$.  (This is the same as the number of words that can be formed from $k$ Ps and $2N-2k$ Ss or from $k-1$ Ps and $2N-2k$ Ss.  Here P stands for "pair" and S stands for "singleton".  The word PPSPS, for example, corresponds to the $\{i_1,i_2,i_3\}=\{0,2,5\}$.  The $i_j$ are the positions of the Ps, with Ps thought of as occupying two sites and Ss as occupying one.  The first binomial coefficient counts the $\{i_1,i_2,\ldots,i_k\}$ in which none of the $i_j$ equals $2N-1$; the second counts the $\{i_1,i_2,\ldots,i_k\}$ in which one of the $i_j$ equals $2N-1$.)
Putting this all together, the number of partitions in which none of the pairs are edges of the cycle graph is
$$
\sum_{k=0}^N(-1)^k(2N-2k-1)!!\left[\binom{2N-k}{k}+\binom{2N-k-1}{k-1}\right].
$$
For $N=1,2,3,4,\ldots$ we get 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897.  This is A003436 in the Online Encyclopedia of Integer Sequences, which contains many useful references about this sequence.
