Cuántas funciones inyectiva $f:[1,...,m]\to{[1,...,n]}$ no tiene ningún punto fijo? $(m\le n)$

Question

Cuántas funciones inyectiva $f:[1,...,m]\to{[1,...,n]}$ no tiene ningún punto fijo? $(m\le n)$

Pensé acerca de lo siguiente:

$f(x_1)\neq x_1$, Significa que puede elegir para $x_1$ - (n-1) opciones,

Pero entonces, por $x_2$, hay dos opciones:

1. Si elijo $f(x_1)=x_2$ $x_2$ todavía tengo (n-1) opciones.

2. Si elijo $f(x_1)\ne x_2$ $x_2$ voy a tener (n-2) opciones.

Entonces, ¿cómo puedo cuidar de que? O estoy mirando la cuestión totalmente equivocado?

Answer 1

Fijar un número entero $a \ge 0$.

Tratamos de dar una recurrencia para el número de no-punto fijo-inyecciones $$f: \{1,2,3, \dots, m\} \to \{1,2, \dots, m, m+1, \dots, m+a\}$$

Por $a$, la cantidad de $m$$D_m$. Tenemos que $D_1 = a$ $D_2 = a^2 + a +1 $ (si no se han calculado correctamente, pero debe ser fácil de calcular).

Tenemos la recurrencia

$$ D_m = (m+a-1)D_{m-1} + (m-1)D_{m-2}$$

exactamente de la misma manera podemos obtener la recurrencia para el caso de $a=0$: Suponga $f(1) = j$. A continuación, cualquiera de $j \le m$ $f(j) = 1$ (corresponde a $D_{m-2}$) o $f(j) \neq 1\; \text{or}\; j \gt m$ (corresponde a $D_{m-1}$).

Ahora los métodos estándar(como la generación de funciones) debe ser capaz de dar una fórmula.

Answer 2

Si representamos un no-fijo-punto de inyección de $f$ por un etiquetado dígrafo con un borde de $x$ $f(x)$por cada $x\in[m]$, entonces el dígrafo consta sólo de rutas y orientado a los ciclos (de longitud de, al menos,$2$).

Utilizando el "método simbólico" (ver Flajolet y Sedgewick, especialmente la Sección II.$5$ para este enfoque), la combinatoria de la clase $\mathcal{J}$ de los bigramas puede ser especificado por $$ \mathcal{J} \;=\; \mathrm{SET}[\mathrm{CYC}_{\geqslant2}[\mathcal{UZ}] \:+\: \mathcal{\mathcal{Z}} \estrellas \mathrm{SEQ}[\mathcal{UZ}]] $$ donde $\mathcal{Z}$ marca el número de $n$ de los vértices en el dígrafo (el tamaño de la codominio) y $\mathcal{U}$ marca el número de $m$ de las aristas en el dígrafo (el tamaño del dominio).

Esta especificación inmediatamente nos da la (bivariado) exponencial en la generación de la función de la clase de los bigramas: $$ 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)}.$$ El coeficiente de $j_{m,n}$ overcounts sin punto fijo inyecciones por un factor de $\binom{n}{m}$ porque sólo queremos los casos en los que el $m$ vértices con grado $1$ son etiquetados $1,\dots,m$. Por tanto, el número de sin punto fijo inyecciones está dada por $$ i_{m,n}\;=\;m!(n-m)![u^mz^n]J(u,z) $$ donde $[u^mz^n]J(u,z)$ significa que el coeficiente de $u^mz^n$$J(u,z)$. No estoy al tanto de cualquier forma cerrada para $i_{m,n}$. Aquí una tabla de valores para las pequeñas $m$$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

Este es A076731 en OEIS, donde los siguientes criterios de inclusión-exclusión formulario: $$ i_{m,n}\;=\;\frac{1}{(n-m)!}\sum_{j=0}^{m} (-1)^j(n-j)!\binom{m}{j}. $$