How many injective functions $f:[1,...,m]\to{[1,...,n]}$ has no fixed point? $(m\le n)$ How many injective functions  $f:[1,...,m]\to{[1,...,n]}$ has no fixed point? $(m\le n)$
I thought about the next thing:
$f(x_1)\neq x_1$, Means i can choose for $x_1$ - (n-1) options,
But then, for $x_2$, there are two options:


*

*If i choose $f(x_1)=x_2$ then for $x_2$ i still have (n-1) options.

*If i choose $f(x_1)\ne x_2$ then for $x_2$ i'll have (n-2) options.
So how can i take care of that? Or am i looking the question totally wrong?
 A: Fix an integer $a \ge 0$. 
We try to give a recurrence for the number of no-fixed-point-injections $$f: \{1,2,3, \dots, m\} \to \{1,2, \dots, m, m+1, \dots, m+a\}$$
For given $a$, let the number for $m$ be $D_m$. We have that $D_1 = a$ and $D_2 = a^2 + a +1 $ (if I have computed correctly, but it should be easy to compute).
We get the recurrence
$$ D_m = (m+a-1)D_{m-1} + (m-1)D_{m-2}$$
exactly the same way we get the recurrence for the case $a=0$: Assume $f(1) = j$. Then either $j \le m$ and $f(j) = 1$ (corresponds to $D_{m-2}$) or $f(j) \neq 1\; \text{or}\; j \gt m$ (corresponds to $D_{m-1}$).
Now standard methods(like generating functions) should be able to give a formula.
A: If we represent a no-fixed-point injection $f$ by a labelled digraph with an edge from $x$ to $f(x)$ for each $x\in[m]$, then the digraph consists just of directed paths and oriented cycles (of length at least $2$). 
Using the "symbolic method" (see Flajolet and Sedgewick, especially Section II.$5$ for this approach), the combinatorial class $\mathcal{J}$ of such digraphs can be specified by
$$
\mathcal{J} \;=\;
\mathrm{SET}[\mathrm{CYC}_{\geqslant2}[\mathcal{UZ}] \:+\: \mathcal{\mathcal{Z}} \star \mathrm{SEQ}[\mathcal{UZ}]]
$$
where $\mathcal{Z}$ marks the number $n$ of vertices in the digraph (the size of the codomain)
and $\mathcal{U}$ marks the number $m$ of edges in the digraph (the size of the domain).
This specification immediately gives us the (bivariate) exponential generating function for the class of digraphs:
$$
J(u,z)\;=\;\sum_{m,n\geqslant0}\frac{1}{n!}j_{m,n}u^mz^n\;=\;
\frac{1}{{1-u z}
}{\exp\left({\frac{z\, (1-u+u^2 z)}{1-u z}}\right)}.$$
The coefficient $j_{m,n}$ overcounts 
no-fixed-point injections by a factor of $\binom{n}{m}$ because we only want the cases in which the $m$ vertices with out-degree $1$ are labelled $1,\dots,m$. Thus the number of 
no-fixed-point injections
is given by
$$
i_{m,n}\;=\;m!(n-m)![u^mz^n]J(u,z)
$$
where $[u^mz^n]J(u,z)$ means the coefficient of $u^mz^n$ in $J(u,z)$. I'm not aware of any closed form for $i_{m,n}$. Here's a table of values for small $m$ and $n$:
          0   1   2    3    4     5      6       7
              1   3    7   13    21     31      43
                  2   11   32    71    134     227
                       9   53   181    465    1001
                           44   309   1214    3539
                                265   2119    9403
                                      1854   16687
                                             14833

This is A076731 in OEIS, where the following inclusion-exclusion form is given:
$$
i_{m,n}\;=\;\frac{1}{(n-m)!}\sum_{j=0}^{m}
(-1)^j(n-j)!\binom{m}{j}.
$$
A: $\newcommand{\nPr}[2]{\,_{#1}P_{#2}} % nPr$
We can think of an approach using Inclusion-Exclusion principle.
Note that we can count the number of injective functions $N$ from $$A = \{1,2,3,\dots,m\} \rightarrow B = \{1,2,3,\dots, n\}$$ such that $\exists ~ i. f(i) = i$ and subtract this result from total number of injective functions from $A \rightarrow B$ which is $\nPr{n}{m}= \binom{n}{m} ~ m!$.
Let $S_i$ denote set of functions which have $f(i) = i$.
By Inclusion-Exclusion,
\begin{align*}
N = & + |S_1| + |S_2| + \dots + |S_m| \\
& - |S_1 \cap S_2| - |S_1 \cap S_3| - |S_1 \cap S_3| - \dots \\
& + |S_1 \cap S_2 \cap S_3| + |S_1 \cap S_2 \cap S_4| + \dots \\
& ~ ~ \vdots \\
& + (-1)^{m+1} |S_1 \cap S_2 \cap \dots \cap S_m| \\ 
= & \binom{m}{1} \nPr{n-1}{m-1} - \binom{m}{2} \nPr{n-2}{m-2} + \dots + (-1)^{m+1} 1 \\
= & \sum _{i=1} ^m (-1)^{i+1} \binom{m}{i} \nPr{n-i}{m-i}
\end{align*}
Hence, our answer is
$$\lambda _{m, n} = \nPr{n}{m} - \sum _{i=1} ^m (-1)^{i+1} \binom{m}{i} \nPr{n-i}{m-i}$$
Note -
$\nPr{n}{r}$ is the notation for permutations and $\nPr{n}{r} = \binom{n}{r} ~ r! = \frac{n!}{(n-r)!}$
A: We can delete the fixed point $F$, in which place we can view it an injection $[m]\setminus F\to [n] \setminus F$. By counting the fixed point, we have 
$$\sum_{i=0}^m \binom{m}{i}f(m-i,n-i)=\binom{n}{m}m!$$
Let $k=n-m$, then
$$\sum_{i=0}^m \binom{m}{m-i}f(m-i,m+k-i)
=\sum_{i=0}^m\binom{m}{j}f(j,k+j)
=\binom{m+k}{m}m!$$
Then
$$f(m,k+m)=\sum_{i=1}^m(-1)^{m-i}\binom{m}{i}\binom{i+k}{i}i!$$
By the lemma below. That is
$$f(m,n)=\sum_{i=1}^m(-1)^{m-i}\binom{m}{i}\binom{i+n-m}{i}i!
=\frac{1}{(n-m)!}\sum_{i=1}^m(-1)^{i}\binom{m}{j}(n-j)!$$
Lemma. For two sequences $\{a_n\}, \{b_n\}$, then
$$a_n=\sum_{i=0}^n(-1)^i\binom{n}{i}b_i\iff b_n=\sum_{i=0}^n(-1)^i\binom{n}{i}a_i$$ 
Pf. We can compute that
$$\sum_{k=0}^n(-1)^{k+m}\binom{n}{k}\binom{k}{m}
=\binom{n}{m}\sum_{k=0}^n (-1)^{k-m}\binom{n-i}{k-m}
=\delta_{nm}$$
