0
$\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?

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is a bit out of the scope, of what I was looking at. Is there a solution using inclusion and exclusion principles? $\endgroup$ – Brownie Apr 20 at 21:05
  • $\begingroup$ Yes the expression can be derived by inclusion/exclusion principle. I would expect that you find the derivation in the given reference. $\endgroup$ – user Apr 20 at 21:09
  • $\begingroup$ 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. $\endgroup$ – Brownie Apr 20 at 21:20
  • $\begingroup$ 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. $\endgroup$ – Brownie Apr 20 at 21:48

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.