TITLE: What is the number of one-to-one functions from the set $\{1, 2,\dots , n\}$ to the set $\{1, 2, \dots , 2n\}$
QUESTION [0 upvotes]: What is the number of one-to-one functions from the set $\{1, 2,\dots , n\}$ to the set $\{1, 2, \dots , 2n\}$ so that $2i − 1$ and $2i$ on the right-hand set are not mapped at the same time for all $1 \leq i \leq n$?
So, I know that between a set with $n$ elements and a set with $m$ elements there will be $n!$ one-to-one functions.
I don't know how to expand that on to this question. If you could explain the steps to solving this problem I'd appreciate it.

REPLY [3 votes]: To get a one-to-one function $f$ from $\{1,\ldots,n\}$ to $\{1,\ldots,2n\}$ such that the range does not include both $2i-1$ and $2i$ for any $i$, first choose for each $i \in \{1,\ldots,n\}$ which of $2i-1$ and $2i$ should be in the range.  That can be done in $2^n$ ways.  Then map $\{1,\ldots,n\}$ to 
your $n$ choices, which can be done in $n!$ ways.  So the answer is $2^n \; n!$.
{"set_name": "stack_exchange", "score": 0, "question_id": 3154954}