8
$\begingroup$

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?

$\endgroup$
2

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Apr 23, 2013 at 14:53
  • $\begingroup$ 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$. $\endgroup$ Apr 23, 2013 at 16:00
  • $\begingroup$ @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. $\endgroup$
    – Aryabhata
    Apr 23, 2013 at 16:14
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .