# Is this the correct solution to find a number of one-to-one functions?

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.

• Regardless of correct or incorrect, I appreciate that you took a shot at solving it and presented your work here. +$1$ – Clayton Apr 20 at 23:34

## 1 Answer

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.

• Great and just to confirm my understanding, the part I marked incorrect was actually the part where I made the mistake? So in my final answer if I swap out the (2n-2)! ..and all of those for the corrected form, my answer is correct? Also for |$A_{i} \cap A_{j} \cap A_{k} ... \cap \ A_{n}$|, does this now equal 1? – Brownie Apr 21 at 0:01
• Yes, it now equals $1$ because you require every element $x$ to go to $2x-1$ so there is only one function in the intersection of all the $A_i$ – Ross Millikan Apr 21 at 0:27