1
$\begingroup$

I have a question about counting the number of injective (one-to-one) and surjective (onto) functions from $\{1,2,...,n\}$ to itself that satisfy $|f(i)-i| \leq 1, \forall i\in \{1,2,...,n\}$. I appreciate any help.

Thanks in advance and happy new year to you all

$\endgroup$
  • 1
    $\begingroup$ What is your question? What have you tried? $\endgroup$ – Brandon Thomas Van Over Dec 31 '15 at 23:42
  • $\begingroup$ I've tried to solve the problem by creating a recursive sequence but I couldn't figure out how to create the sequence. Mr JMoravitz gave an interesting solution to the problem below ... $\endgroup$ – Shahram Khazaie Jan 1 '16 at 0:09
6
$\begingroup$

If $f$ is a function from a finite set to itself and it is surjective, then it is necessarily also injective.

If $f$ is a function from a finite set to itself and it is injective, then it is necessarily also surjective.

See Rigorous proof that surjectivity implies injectivity for finite sets

Both questions are then the same and we are asked to count the number of bijections from $\{1,2,\dots,n\}$ to itself.

Now... note that the only choice for $f(1)$ is $1$ or $2$.

In the case that $f(1)=2$, since $f$ must be a bijection, $f(2)\neq 2$. This leaves $f(2)=1$ or $f(2)=3$. Note, however, that if $f(2)=3$, then $f(n)=1$ for some $n\geq 3$ which is a contradiction since that would imply $|f(n)-n|=|1-n|\geq 2$. Thus, if $f(1)=2$ then $f(2)=1$.

Continue via a recurrence relation using the previous observation.

Letting $a_n=$#of bijective functions from $\{1,2,\dots,n\}$ to itself, from the earlier observation we have the recurrence $a_n=a_{n-1}+a_{n-2}$ with initial conditions $a_1=1$ and $a_2=2$.

You should then recognize this as being the fibonacci sequence and can find the closed form using traditional methods if you so choose.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much. I really appreciate your help. $\endgroup$ – Shahram Khazaie Jan 1 '16 at 0:02
  • $\begingroup$ @JMoravitz I am having trouble extrapolating the recurrence relation. Can you elaborate? $\endgroup$ – Jai T Mar 22 '17 at 14:28
  • $\begingroup$ Made some progress : f(n) has two possibilities n or n-1. When f(n) = n then f maps {1,....,n-1} to {1,....,n-1}, which gives me $a_{n-1}$ part of the recurrence relation. However i m having trouble when f(n) equals n-1. $\endgroup$ – Jai T Mar 22 '17 at 14:48
  • $\begingroup$ @JaiT if f maps n to n-1, what options are available for n-1 to map to? Remember that the function must be bijective. $\endgroup$ – JMoravitz Mar 22 '17 at 17:26
  • $\begingroup$ if f = n-1 then maps {1,...,n-1} to {1,...,n-2,n} ? $\endgroup$ – Jai T Mar 23 '17 at 3:23

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.