Asignación de la función de desafío

Question

Para un conjunto dado $A=\{1, 2, 3, 4, \ldots, n\}$, hallar el número de no-constante asignaciones (asociaciones ) $f$ $A$ $A$tal que $f(k) \leq f(k + 1)$ y $f(k) = f(f(k + 1))$.

Este es el texto del problema. Pero no entiendo ¿cómo podemos tener $f(k)$, cuando no se nos dan una función?

Asignación constante es un mapeo $f$ tal que para algún C, $f(k)$=C para todo k. Gracias a @ferson2020 para la explicación

Answer 1

Podemos describir la capacidad de las secuencias de la siguiente manera. Para algunas constantes $k$ y un valor de $r<n$ tenemos $f(x)=k$$1 \le x \le r$, mientras que $f(x)>k$ $x>r.$ (necesitamos $r<n$ aquí para evitar una constante de la secuencia.) Hasta ahora esto satisface $f(x)=f(f(x+1))$ ya que es constante. Ahora consideremos lo que sucede si definimos $f(r+1)=y.$ Luego de $$k=f(r)=f(f(r+1))=f(y)$$ vemos que $y \le r$ (sólo la primera $r$ enteros de $\{1,...,n\}$ mapa a $k$), y al mismo tiempo tenemos $y>k$ desde $r$ es el mayor entero asignación a $k$ $y=f(r+1).$ Tenemos pues, para las elecciones de el valor de $y$, la única restricción $$k+1 \le y \le r.$$ Así que hay $r-k$ opciones para $y$. Tomamos nota también de que tenemos $k<r$ mediante la combinación de las anteriores $k<y$$y \le r$.

Una vez que el mapa se define en $[1,r+1]$ mediante la asignación de $[1,r]$ $k$ $r+1$a una de las opciones para $y$, los valores de $f$ $r+2,...,n$ son determinadas por el uso de $f(x)=f(f(x+1))$ y en este rango de $f(x)=x-1$ es forzado.

Así que tenemos que añadir, para todas las opciones de $k,r$$1 \le k<r<n$, el número de opciones de $r-k$ para el valor de $y$.

A continuación, el número de mapas es el doble de la suma de la $$\sum_{r=2}^{n-1} \sum_{k=1}^{r-1}(r-k).$$ El interior de la suma aquí es$\binom{n}{2},$, y sumando que da el recuento final como $\binom{n}{3}$