Encontrar el número de funciones de un conjunto a tal que $f(f(x)) = x$

Question

Las preguntas de los estados que $f: A\rightarrow A$ es una función que satisface $f(f(x)) = x.$ Tenemos que encontrar el número de tales funciones con $A = \left\{1,2,3,4\right\}$.

La condición dada indica claramente que la función es la inversa de la misma. Desde el set $A$ fue dado para ser tan pequeña, la primera vez que traté de pensar de algunas funciones familiares que podrían encajar. Yo me vine con $f(x) = x$$f(x) = 5-x$. Pero la respuesta estaba en ninguna parte cerca de $2$.

Creo que tiene que ser un método general para encontrar el no. de las funciones que cumplen una determinada condición, en lugar de golpear y juicio y contando con los dedos. Pero yo no soy capaz de averiguar lo que es.

Answer 1

El número de tales funciones es el número de maneras de dividir a nuestro conjunto, en este caso $\{1,2,3,4\}$ a $1$ o $2$ elemento subconjuntos. Por tal subdivisión, podemos definir a la $f(x)$ $x$ si $x$ es un singleton en la subdivisión, y por $f(x)=y$, $f(y)=x$ si en la subdivisión $x$ $y$ son una "pareja". Por el contrario, una función de $f$ tal que $f(f(x))=x$ todos los $x$ determina una subdivisión de $\{1,2,3,4\}$ a solteros y parejas.

Deje que nosotros nos ocupamos de que el número de maneras de dividir un $n$-element set, decir $\{1,2,\dots,n\}$, en singles y/o parejas. Llame a este número de maneras $a_n$.

Tenga en cuenta que $a_{n+1}=a_n+na_{n-1}$. Por si queremos añadir un nuevo elemento $n+1$$\{1,2,\dots,n\}$, puede ser por sí mismo, en cuyo caso no se $a_n$ maneras de dividir el resto en grupos de a $1$ y/o $2$, o puede ser emparejado con uno de los anteriores elementos, en cuyo caso el resto se puede subdividir en singles y/o parejas en $a_{n-1}$ maneras. Hemos obtenido la recurrencia $$a_{n+1}=a_n+na_{n-1}.$$ Está claro que $a_1=1$$a_2=2$. Por lo tanto, por la recurrencia, se han $a_3=a_2+2a_1=4$, $a_4=a_3+3a_2=10$, $a_5=26$, y así sucesivamente.

No es agradable la forma cerrada conocido por $a_n$.

Answer 2

Tenga en cuenta que una función no necesariamente han cerrado la expresión que la define. que es que usted no necesariamente necesita para expresar lo $f(x)=5-x$ o $f(x)=x$, pero es algo que debemos estado, donde cada elemento de ir. Así que una función es si $f(1)=4, f(4)=1, f(2)=3, f(3)=2$.

Cada función que satisface la condición anterior, debe ser de la forma $f(x)=y$ si y sólo si $f(y)=x$.

Podemos Optar $f(1)$ 4 diferentes maneras.

• Si $f(1)\neq 1$, luego tenemos a la izquierda para elegir donde los dos elementos que no son de 1 o $f(1)$ debe ser asignado, y esto lo podemos hacer de 2 formas diferentes. Este si $f(1)\neq 1$ tenemos 2 opciones.
• Si $f(1)=1$ tenemos 3 opciones de algún otro elemento que debe ser mapeada a sí mismo. A continuación, el resto de los elementos pueden ser asignadas a ellos mismos o en los demás. Esto nos da 4 opciones en total, 3 en el que los elementos se asignan a cada uno de los otros y 1, donde todos los elementos están obsesionados.

3 maneras de obtener el caso 1 que indujo 2 opciones, y tuvimos 1 camino para llegar a el caso 2 que indujo 4 opciones. Así llegamos $3\cdot 2 + 1\cdot 4 = 10$ tales funciones.

Answer 3

Esto puede me preguntó, como una teoría de grafos problema: ¿cuántos de gráficas con los vértices $\{a,b,c,d\}$ existe tal que cada vértice se encuentra en exactamente un ciclo de longitud en la mayoría de las $2$?

Caso 1: Todos los ciclos de longitud 1. Esto es equivalente a la función identidad, que sabemos que es único. Sin embargo, a partir de una gráfica teórica punto de vista, esta es igual a $\binom{4}{4}$ porque estamos eligiendo 4 vértices tener la longitud del ciclo uno (observe que el orden no importa, porque los ciclos comienzan y terminan en el mismo lugar, y si dos funciones tienen la misma ciclos, independientemente del orden en que son iguales). $\binom{4}{4} = 1$, consistente con lo que sabemos acerca de la identidad.

Caso 2: Un ciclo de longitud 2, y 2 son de longitud uno. Sabemos que los dos de la longitud de uno son elegidos por $\binom{4}{2}$ y el ensanchamiento de los dos vértices son las fuerzas en los ciclos de la longitud de los dos (o son "elegidos" por $\binom{2}{2}$).

Caso 3: 2 ciclos de longitud 2, que es la misma cantidad de opciones como en el anterior, ya que los dos que quedan son forzados a ser el ciclo. Tenemos que dividir por el número de formas que hay para organizar el 2 $2$-ciclos, que es $2!$

Suma las cantidades de las funciones de los tres casos se obtiene $10$.