Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.