Setting up an inclusion-exclusion question What is the number of one-to-one functions $f$ from the set $\{1,2,...,n\}$ to the set $\{1,2,...,2n\}$ so that $f(x) \neq x$ and $f(x) \neq 2n - x + 1$ for all $x$?
I'm getting that the number of such functions is total number of one-to-one functions here (which is $(2n)!/n!$) - $|A_1 \cup A_2 \cup \ldots \cup A_n|$ where $A_i$ is the set of one-to-one functions such that $f(x)=x$ or $f(x)=2n-x+1$ for some $x$. 
Where do I go from there?
 A: I’ll work this one out in detail to give you a model for similar problems.
As usual, $[n]=\{1,2,\ldots,n\}$. The inclusion-exclusion principle says that
$$\left|\bigcup_{k=1}^nA_k\right|=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}A_k\right|\;,$$
so the first step is to figure out what $\left|\bigcap_{k\in I}A_k\right|$ is for an arbitrary non-empty subset $I$ of $[n]$.
Clearly 
$$|A_k|=\frac{2(2n-1)!}{n!}$$
for each $k\in[n]$: there are $2$ choices for $f(k)$ and $\frac{(2n-1)!}{n!}$ for the rest of $f$. More generally, suppose that $\varnothing\ne I\subseteq[n]$. There are $2$ choices for $f(k)$ for each $k\in I$, so
$$\left|\bigcap_{k\in I}A_k\right|=\frac{2^{|I|}(2n-|I|)!}{n!}\;,$$
and therefore 
$$\begin{align*}
\left|\bigcup_{k=1}^nA_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\frac{2^{|I|}(2n-|I|)!}{n!}\\
&=\sum_{k=1}^n\binom{n}k(-1)^{k+1}\frac{2^k(2n-k)!}{n!}\\
&=\frac1{n!}\sum_{k=1}^n\binom{n}k(-1)^{k+1}2^k(2n-k)!\;.
\end{align*}$$
Thus, the total number of functions with the desired properties is
$$\begin{align*}
\frac{(2n)!}{n!}-\frac1{n!}\sum_{k=1}^n\binom{n}k(-1)^{k+1}2^k(2n-k)!&=\frac{(2n)!}{n!}+\frac1{n!}\sum_{k=1}^n\binom{n}k(-1)^k2^k(2n-k)!\\
&=\frac1{n!}\sum_{k=0}^n\binom{n}k(-1)^k2^k(2n-k)!\;.
\end{align*}$$
A: Perhaps an explanation in words can be helpful here.
The answer is
$$\sum_{q=0}^n {n\choose q} (-1)^q 2^q 
{2n-q\choose n-q} (n-q)!$$
We start by computing the number of functions having at least $q\ge 1$
special points with a forbidden  assignment.  That means we must first
choose the $q$ slots:
$${n\choose q}$$
There are two possibilities for each slot, giving
$$2^q$$
Once the  special points are  assigned there are $2n-q$  elements left
over from which  we must select $n-q$ to fill  out the function. These
$n-q$ elements can occur in any order, so we have
$${2n-q\choose n-q}\times (n-q)!$$
Now  we want  to  assign a  weight  $\alpha_q$ to  the  counts of  the
functions having at least $q$ special points so that a function having
at  least one  special  point has  total  weight equal  to minus  one,
corresponding  to  subtraction  from  the  total  of  the  ${2n\choose
n}\times n!$  functions.  Suppose it  has $p$ special points.   Such a
function contributes to all $q\le p.$ The cumulative weight is
$$\sum_{q=1}^p {p\choose q} \alpha_q.$$
Choosing $\alpha_q = (-1)^q$ we get
$$\sum_{q=1}^p {p\choose q} (-1)^q = -1.$$
With this choice of weight,  functions with at least one special point
are counted zero times in the sum
$${2n\choose n} \times n!
+  \sum_{q=1}^n {n\choose q} (-1)^q 2^q 
{2n-q\choose n-q} (n-q)!$$
because they are counted once in  the first term.  We absorb this term
into the sum and obtain the formula given at the beginning.
For Maple enthusiasts I present the Maple code to compute the first
few  values of  this sequence  by  total enumeration  and compare  the
result to the closed form expression.

with(combinat);

Q :=
proc(n)
    option remember;
    local comb, perm, func, pos, res;

    res := 0;

    comb := firstcomb(2*n, n);

    while type(comb, `set`) do
        perm := firstperm(n);

        while type(perm, `list`) do
            func :=
            [seq(op(perm[ind], comb), ind = 1..n)];

            for pos to n do
                if func[pos] = pos or
                func[pos] = 2*n+1-pos then
                    break;
                fi;
            od;

            if pos = n+1 then
                res := res + 1;
            fi;

            perm := nextperm(perm);
        od;

        comb := nextcomb(comb, 2*n);
    od;

    res;
end;

S := n-> add(binomial(n,q)*(-1)^q*2^q*
             binomial(2*n-q,n-q)*(n-q)!, q=0..n);

Remark. To be precise about it what we are computing with the $\alpha_q$ is of course the Möbius function of the poset of the subsets of [n] ordered by set inclusion which is $(-1)^q$ where $q$ is the number of elements in the subset.
