El número de funciones de $[5]$ $[5]$ tal que $f(f(x)) \neq x $ $ x=1, \ldots 5$ es $44$

Question

Verdadero o falso: El número de funciones de $[5]$ $[5]$tal que $f(f(i)) \neq i $ $ i=1, \ldots 5$ $44.$

(Aquí se $[5] = \{1,2,3,4,5\}.)$

El número de alteraciones en $5$ elementos es$44$, pero las funciones en cuestión claramente no sólo las alteraciones, ya que la existencia de $x, y$ tal que $f(x)=y$ $f(y)=x$ también está prohibido. Además, no hay ninguna restricción en $f$ a ser bijective.

Mi intento: para cada función $f,$ definir $g= f^2$ y el recuento de las funciones de $g: [5] \to [5]$ tal que $g(i) \neq i$ por la inclusión-exclusión de la siguiente manera: $5^5 -\binom{5}{1}(4^4) + \binom{5}{2}(3^3)- \ldots $ y así sucesivamente. El problema es que aunque el conjunto de $g's$ no están en bijective correspondencia con el conjunto de $f's$ y no estoy convencido de que la expresión que he de arriba es correcto porque la respuesta resultante es demasiado grande.

Cualquier ayuda se agradece.

Answer 1

De acuerdo a OEIS del A134362, para $[5]$ debería ser $444$. Una fórmula general para el número de funciones de $f:[n]\to[n]$ tal que para cada $x\in[n]$, $f(f(x)) \not =x$ es $$n!\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\cdot\frac{(n-1)^{n-2k}}{2^k k!(n-2k)!}.$$

P. S. tenga en cuenta que dichas $f$ no son necesariamente inyectiva: $$[1,2,3,4,5]\stackrel{f}{\to} [2, 3, 1, 1, 1]\stackrel{f}{\to} [3, 1, 2, 2, 2]$$

Una prueba de esta fórmula por Marco Riedl es todavia publicado en matemáticas.stackoverflow.

Answer 2

La condición de $f(f(i)) \neq i$ implicará bijectivity. Hay, de hecho, $44$ derrangements de $[5]$, $24$ de los "sabor" $(abcde)$ $20$ de los "sabor" $(ab)(cde)$. El último "sabor" no satisfará a los condtion $f(f(i)) \neq i$. Así que hay $\color{blue}{24}$ funciones $[5]$ cuya segunda iteración mapa también no tiene puntos fijos.

Edit : dos funciones sin puntos fijos.

En un conjunto de tres elementos hay $2$ funciones de la forma $ a \rightarrow b \rightarrow c \rightarrow a $. ($a \neq b \neq c \neq a$)

En $[4]$, $6$ de la forma $ a \rightarrow b \rightarrow c \rightarrow d \rightarrow a$ & no se $24$ de la forma $ a \rightarrow b \rightarrow c \rightarrow d \rightarrow b$. Por lo $30$ in toto.

En $[5]$,

Hay $24$ de la forma $ a \rightarrow b \rightarrow c \rightarrow d \rightarrow e \rightarrow a$

Hay $120$ de la forma $ a \rightarrow b \rightarrow c \rightarrow d \rightarrow e \rightarrow b$

Hay $120$ de la forma $ a \rightarrow b \rightarrow c \rightarrow d \rightarrow e \rightarrow c$

Hay $60$ de la forma $ a \text{ and } b \rightarrow c \rightarrow d \rightarrow e \rightarrow c$

Hay $120$ de la forma $ a \rightarrow c , b \text{ and } c \rightarrow d \rightarrow e \rightarrow c$

Así que hay $444$ in toto.