# 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:

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

2. 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?

-
en.wikipedia.org/wiki/Derangement this is for $m = n$. – xyzzyz Apr 20 '13 at 21:28
This is A076731 in OEIS. – David Bevan Apr 23 '13 at 18:07

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.

-
This recursion doesn't appear to give the correct result. For example, with $a=1$, $D_3=12$ whereas there are only $11$ no-fixed-point injections from $[3]$ into $[4]$, the images of $123$ being $214, 231, 234, 241, 312, 314, 341, 342, 412, 431, 432$. – David Bevan Apr 23 '13 at 14:53
It appears that the required recurrence is $D_m =(m+a−1)D_{ m−1} +(m-1)D_{ m−2 }$ or equivalently, $I(m,n)=(n-1)I(m-1,n-1)+(m-1)I(m-2,n-2)$ with $I(1,n)=n-1$ and $I(2,n)=n^2-3n+3$. – David Bevan Apr 23 '13 at 16:00
@DavidBevan: Yes, you are right! The case $1$ maps to $j \gt m$, we don't have a $D_{m-2}$ case. Thanks for pointing that out. Corrected. – Aryabhata Apr 23 '13 at 16:14

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

-