2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brownie Apr 21 at 0:01
  • $\begingroup$ 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$ $\endgroup$ – Ross Millikan Apr 21 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.