Setting up an inclusion-exclusion question

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?

Answer 1

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*}$$

Answer 2

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.