Encuentre el número de funciones $f : [\![1,n]\!] \to [\![0,n]\!]$ tal que $\forall k \in [\![1,n]\!], \exists k' \in \Bbb N, f^{k'}(k)=0 $ .

Question

Encuentre el número de funciones $f : [\![1,n]\!] \to [\![0,n]\!]$ tal que $\forall k \in [\![1,n]\!], \exists k' \in \Bbb N, f^{k'}(k)=0$ .

Por supuesto, aquí $f^{k'}(k)=f(f(\cdots(k)\cdots))$ .

He estudiado los casos $n=1$ ( $f=0$ es la única solución) y $n=2$ ( $3$ soluciones). Tenía la sensación de que podía haber algo relacionado con los ciclos disjuntos, pero no es el caso en general (si tomamos $f : (1,2,3) \mapsto (2,0,2)$ tenemos $f=(1 \to 2 \to 0)(3 \to 2 \to 0)$ ).

Answer 1

Su interpretación de los "ciclos disjuntos" son esencialmente caminos que van desde los nodos no accesibles (los elementos que no están en la imagen de su función) hasta $0.$ Demuestre que estos son, pictóricamente, árboles enraizados en el sentido de que hay una raíz(el número que va a $0$ ) y no puede haber ciclos, de lo contrario, los elementos de esos ciclos nunca llegan a $0$ .

Esto significa que Teorema de Cayley se aplica y hay $(n+1)^{n-1}$ de dichas funciones. Convénzase dibujando en esta forma pictórica las funciones que obtuvo para $n=3.$ Obsérvese que el $n+1$ proviene de la colocación de $0$ como la raíz de este árbol (probablemente a esto se refería la insinuación de Mike).