3
$\begingroup$

Find the number of injective functions (from finite set to finite set):

$$ f:\{ 1,2,3,4,5,6,7\} \rightarrow \{ 1,2,3,4,5,6,7,8,9\} $$

with the following property: $$ f(i) \neq f(j)+1\ \text{ for all } \ 1\leq i < j \leq 7. $$

Help me with mathematical decision (I can count this number on computer). Thank you.

  • 0
    The total number of injective functions is $\frac{9!}{2!}$ because there are $9$ choices for $f(1)$, $8$ for $f(2)$, etc. Injecting (seems like a good choice of word) the required property makes it much harder. Maybe inclusion-exclusion?2012-11-15
  • 0
    If I found the answer, what should I do? Can I just delete this question?2012-11-15
  • 1
    Idea of decision is - $f:\{ 1,..,n \} \rightarrow \{ 1,..,n+2 \}$. Every "Injecting" divide set $\{ 1,..,n+2 \}$ into $3$ subsets. So we can placed $n$ numbers at any of this three subsets by $3^n$ ways.2012-11-15
  • 1
    If you find the answer, you are encouraged to write it up as an answer and accept it.2012-11-15

0 Answers 0