How many injective functions $f:[1,...,m]\to{[1,...,n]}$ has no fixed point? $(m\le n)$

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.

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