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

$\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)!}$