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.
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)!}.$$