What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $$\neq$$ 2x − 1 for all x?

Alright so I did see this question, but it really didn't cover it for me so I'm asking myself.

Check my math - Number of one-to-one functions $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, 2n-1\}$ such that $f(x) \neq 2x - 1$ for all $x$

So i'm new to this, and need to solve this using inclusion and exclusion. Here's what I got, but I"m not sure how to progress.

Going off of my notes, here's what I got ..

If we take $$A_{i}$$ to be a set of one-to one functions so f(x) = 2x − 1

$$A_{1} \cup A_{2} \cup A_{3} .... \cup A_{n}$$; is the set of one to functions so f(x)= 2x-1 for some x (complement of our original)

Now the next step according to my notes is to find intersections, but I'm a little confused on how to progress.

I think

|$$A_{i}$$| has I think (2n-1)! intersections

|$$A_{i} \cap A_{j}$$| has (2n-2)! intersections

|$$A_{i} \cap A_{j} \cap A_{k}$$| has (2n-3)! intersections

This work might be completely wrong

What we want is the total # of one to one functions minus |$$A_{1} \cup A_{2} \cup A_{3} .... \cup A_{n}$$|

I think, but I'm not sure how to get there, and I"m a beginner so if you could help I'd appreciate it.

The question is similar to finding a number of permutations having no fixed elements. Such permutations are known as derangements.

The proof from wikipedia can be adapted for your case as follows:

For $$1\leq k \leq n$$ we define $$S_k$$ to be the set of permutations of $$n$$ objects that map $$k\mapsto 2k-1$$. Any intersection of a collection of $$i$$ of these sets fixes a particular set of $$i$$ objects and therefore contains $$\frac{(2n-1-i)!}{(n-1)!}$$ functions. There are $${n\choose i}$$ such collections, so the inclusion–exclusion principle yields

\begin{align}|S_1\cup\cdots\cup S_n| &=\sum_{i=1}^n (-1)^{i-1}{n\choose i}\frac {(2n-1-i)!}{(n-1)!} \end{align}

and since none of the $$n$$ objects fixed, we get

$$\frac {(2n-1)!}{(n-1)!} - |S_1\cup\cdots\cup S_n|=\sum_{i=0}^n (-1)^i{n \choose i} \frac {(2n-1-i)!}{(n-1)!}.$$

• This is a bit out of the scope, of what I was looking at. Is there a solution using inclusion and exclusion principles? – Brownie Apr 20 at 21:05
• Yes the expression can be derived by inclusion/exclusion principle. I would expect that you find the derivation in the given reference. – user Apr 20 at 21:09
• Thanks for the help, but I think this a little out side of my skill level, and I'm not exactly sure how to progress with you proposed method. – Brownie Apr 20 at 21:20
• So derangement's are something I haven't even heard of, but the way I was looking to solve it was like so.... the following is from my notes. |$A_{1} \cup A_{2} \cup A_{3} .... \cup A_{n}$| = $n \choose 1$ (n-1)! - $n \choose 2$ (n-2)! + ... + $(-1)^{n+1}$ $((n \choose n)) ^{(n-n)!}$. Then you would subtract that from the total number of functions n! in this case. This particular solution is for a different problem but I'm trying to apply it to this situation. I'm having trouble progressing from finding number of intersections for |$A_{i}$|, because I'm still trying to understand. – Brownie Apr 20 at 21:48