Número de funciones posibles que satisfacen las condiciones dadas

Question

Tengo que encontrar el número de funciones $f(x)$ de {1,2,3,4,5} a {1,2,3,4,5} que satisfagan $ f(f(x)) = f(f(f(x)))$ para todos $x$ en {1,2,3,4,5} .

Sin embargo, no consigo entender por dónde empezar. El número de casos que estoy tratando de analizar es demasiado. He intentado clasificarlo en funciones que son onto, que no son onto en las que sólo aparece una imagen dos veces y así sucesivamente, pero me estoy dando cuenta de que la lista se está haciendo demasiado grande. ¿Puede alguien ayudarme con un análisis más sencillo de esta cuestión?

Answer 1

Permítanme comentar la conexión con Combinatoria analítica. Es se sabe que todas las endofunciones en $[n]$ son conjuntos de ciclos de árboles etiquetados etiquetados. Esto se deduce del hecho de que cuando iteramos $f$ obtenemos un camino que termina en un ciclo y se documenta en Cartografía aleatoria Estadísticas de P. Flajolet, donde se derivan las asintóticas. La construcción también apareció en este MSE enlace . La clase combinatoria clase combinatoria viene dada entonces por

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{F} = \textsc{SET}(\textsc{CYC}(\mathcal{T})) \quad\text{where}\quad \mathcal{T} = \mathcal{Z} \textsc{SET}(\mathcal{T}).$$

Ahora bien, en el presente caso no puede haber ciclos de dos o más elementos porque los valores de esos ciclos no cumplirían la condición de que $f(f(x)) = f(f(f(x))).$ Esto deja conjuntos de árboles, siendo la raíz del del árbol es un punto fijo. Obsérvese que cualquier hoja con un camino a la raíz incluyendo la raíz que contiene más de tres nodos también rompe el requisito de que $f(f(x)) = f(f(f(x))).$ Esto restringe la clase de clase de árboles a aquellos en los que el camino de cada hoja a la raíz incluyendo la raíz, contiene como máximo tres nodos. Ahora, para caracterizar estos árboles son, primero, un nodo único (punto fijo) o, segundo un nodo único (también un punto fijo) con un conjunto de subárboles adjuntos a él, que a su vez son hojas o tienen un conjunto de hojas que tienen un conjunto de hojas. Con la clase combinatoria $\mathcal{T}$ de estos árboles obtenemos así

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z})).$$

La clase combinatoria deseada $\mathcal{F}$ es un bosque de estos árboles dado por

$$\mathcal{F} = \textsc{SET}(\mathcal{T}) = \textsc{SET}(\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1} (\mathcal{Z} + \mathcal{Z}\textsc{SET}_{\ge 1}(\mathcal{Z}))).$$

Obsérvese que la distinción entre los nodos que no tienen subárboles y los nodos con un conjunto de subárboles como característica que que aparece durante el estudio de los problemas dados no es esencial aquí y podemos utilizar el hecho conveniente de que

$$\mathcal{E} + \textsc{SET}_{\ge 1}(\mathcal{Q}) = \textsc{SET}(\mathcal{Q}).$$

Así pues, tenemos para la clase en cuestión que es

$$\mathcal{F} = \textsc{SET}(\mathcal{Z}\textsc{SET}(\mathcal{Z} \textsc{SET}(\mathcal{Z}))).$$

Lo que ocurre aquí es que para los árboles enraizados de altura máxima $h$ tenemos $\mathcal{T}_{\le 0} = \mathcal{Z}$ y para $h\ge 1$

$$\mathcal{T}_{\le h} = \mathcal{Z} \textsc{SET}(\mathcal{T}_{\le h-1}).$$

Obtenemos instantáneamente el EGF

$$F(z) = \exp(z\exp(z\exp(z))).$$

Extrayendo los coeficientes aquí encontramos

$$n! [z^n] F(z) = n! [z^n] \sum_{q=0}^n \frac{1}{q!} z^q \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \exp(qz\exp(z)) \\ = n! \sum_{q=0}^n \frac{1}{q!} [z^{n-q}] \sum_{p=0}^{n-q} \frac{1}{p!} q^p z^p \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p [z^{n-q-p}] \exp(pz) \\ = n! \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$

Esta es la fórmula que se presenta en OEIS A000949 . Al parecer, han optado por simplificar omitiendo el término de $q=0$ ( $q^p=1$ sólo cuando $p=0$ pero entonces $p^{n-q-p} = 0$ ) y extrayendo el término para $q=n$ (que se simplifica a $1$ ) para obtener

$$1 + n! \sum_{q=1}^{n-1} \frac{1}{q!} \sum_{p=0}^{n-q} \frac{1}{p!} q^p \frac{p^{n-q-p}}{(n-q-p)!}.$$

Answer 2

Una pista: Si $x=f^2(c)$ para algunos $c$ Entonces, usted tiene $f(x) = x$ . Esto significa que cada $x \in \text{Im}(f^2)$ es un punto fijo de $f$ . ¿Crees que puedes concluir?

---

Podemos construir $f$ de la siguiente manera.

$\quad\mathbf{(1)}$ : $f$ debe contener exactamente $k$ puntos fijos en $\{1,2,\dots,5\}$ para algunos $k$ con $1\leqslant k\leqslant 5$ .

$\quad\quad\mathbf{(1.1)}$ : Si $k=5$ Entonces sólo hay una posibilidad: $f$ es la identidad.

$\quad \mathbf{(2)}$ : Para $k<5$ , considere el conjunto $S$ de puntos que no son fijos y que están asignados a uno de los $k$ puntos fijos. No está vacío, ya que de lo contrario podríamos iterar algunos puntos no fijos $x$ en $f$ y encontrar una contradicción con $f^2 = f^3$ . Sea $j=|S|$ para que $1\leqslant j\leqslant 5-k$ .

$\quad \mathbf{(3)}$ : Los puntos restantes, si los hay, deben asignarse a uno de los $j$ puntos en $S$ . En efecto, dejemos que $x$ sea uno de esos puntos, y considere $f(x)$ . Tenemos que $f(f(x)) = f^2(x)$ es un punto fijo de $f$ $($ porque $f^2 = f^3)$ Así que, o bien $f(x)\in S$ o $f(x)$ es a su vez un punto fijo. Esto último implicaría a su vez $x\in S$ o bien $x$ es a su vez un punto fijo, pero hemos excluido estas posibilidades (el "restante puntos).

Por lo tanto, tenemos

$$1 + \sum_{k=1}^4\left(\binom{5}{k}\cdot\sum_{j=1}^{5-k}\,\binom{5-k}{j}k^jj^{5-k-j}\right) = 756$$

posibilidades. Vamos a explicar la fórmula.

• El único $1$ antes de la suma sobre $k$ es la identidad $\mathbf{(1.1)}$ .
• $\binom{5}{k}$ es el número de formas de elegir $k$ de los puntos en $\{1,2,\dots,5\}$ para arreglar.
• $\binom{5-k}{j}$ es el número de formas de elegir $j$ de los restantes $5-k$ para que sean los puntos en $\mathbf{(2)}$ que mapean a los puntos fijos.
• $k^j$ es el número de formas de elegir, para cada una de las $j$ puntos anteriores, a cuál de los $k$ puntos fijos que se mapea.
• $j^{5-k-j}$ es el número de formas de elegir, para cada una de las restantes $5-k-j$ puntos, a cuál de los $j$ puntos en $\mathbf{(2)}$ está mapeado.

Observa que las cancelaciones conducen a la fórmula de la respuesta de Somos, así que aquí tienes una interpretación combinatoria de la misma.

---

Es fácil generalizar este procedimiento para otros valores de $m$ con $f^m = f^{m+1}$ Y esto es básicamente un enfoque escalonado. Para algunos $x\in\text{Dom}(f)$ , dejemos que $\text{ord}(x)$ sea el menor número entero no negativo $n$ con $f^n(x) = f^{n+1}(x)$ , donde $f^0(x) = x$ . Entonces es fácil comprobarlo:

• $\text{ord}(x) = 0 \iff f(x) = x$
• $0 < \text{ord}(x) < \infty \implies \text{ord}(f(x)) = \text{ord}(x) - 1$
• $\text{ord} \leqslant m$

De este modo, podemos construir $f$ desde el principio. Imitando los puntos anteriores, procedemos de la siguiente manera:

• Comenzamos con los $x$ con $\text{ord}(x) = 0$ , es decir, los puntos fijos.
• Si hemos definido $f$ en el conjunto de puntos con $\text{ord} \leqslant k < m$ podemos definir $f$ en el conjunto de puntos con $\text{ord} = k+1$ asignando cada uno de esos puntos a algún punto con $\text{ord} = k$ .
• Este procedimiento debe terminar, porque $\text{ord} \leqslant m$ .

Answer 3

El problema de la enumeración se resuelve con Secuencia OEIS A000949 . El comentario dice "Equivalentemente, el número de mapeos desde un conjunto de n elementos hacia sí mismo donde f(f(x)) = f(f(x)))". La función generadora exponencial es $\, \exp(x \exp(x \exp(x))). \,$ Una fórmula como suma es $$\, a(n) = 1 + n! \sum_{m=1}^{n-1} \frac1{m!} \sum_{k=1}^{n-m} \frac{k^{n-m-k} m^k}{k! (n-m-k)!}. \,$$

Answer 4

Esta es una mala respuesta. No hay matemáticas en absoluto. Sólo como una comprobación de cualquier solución que usted termina con, parece que la respuesta es 756.

Fuerza bruta Python.

def funcs(N):
  "Construct a list of all N-tuples of elements of range(N):"
  res = [()]
  for j in range(N):
    res = [(a,) + f for a in range(N) for f in res]
  return res

def check(f,N):
  "Test whether f^2=f^3 for a given f"
  for j in range(N):
    if not(f[f[j]] == f[f[f[j]]]): return 0
  return 1

count =  0
for f in funcs(5):
  if check(f,5):
    count = count + 1

print count