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?
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)
|$A_{i}$| has (2n-2)!
|$A_{i} \cap A_{j} $| has (2n-3)!
|$A_{i} \cap A_{j} \cap A_{k}$| has (2n-4)!
thus
|$A_{i} \cap A_{j} \cap A_{k} ... \cap \ A_{n}$| = (n-1)!
I think I might've done this part wrong, but continuing ...
The total number of one to one functions is $\frac{(2n-1)!}{(n-1)!}$, and so taking what we know we can subtract the following from the total number of functions to get the final answer.
$\frac{(2n-1)!}{(n-1)!}$ - $ n \choose 1$ (2n-2)! + $n \choose 2$ (2n-3)! - $n \choose 3$ (2n-4)! + … + $(-1)^{n+1}$ ${n \choose n}^{(n-n)!}$
Now i strongly feel like I have made a mistake, and I'm pretty sure it was in the quote section, I'm really a beginner and so I wasn't sure behind how this works, and went off of my best guess.
This is a good approach but not executed correctly. $|A_i|=\frac {(2n-2)!}{(n-1)!}$ because after you fix $f(i)$ you have $2n-2$ choices for the image of the first element, $2n-3$ for the second, on to $n$ choices for the last one. Similarly $|A_i\cap A_j|=\frac {(2n-3)!}{(n-1)!}$. All your sizes should be divided by $(n-1)!$ because you only have $n$ elements in the domain. Once you do that your expression is the correct implementation of the inclusion-exclusion principle.