Número de funciones

Question

Que $A$ establecerse tal que $n(A)=5$. ¿Cuántas funciones podemos definir en la propiedad $A$ $(f\circ f)(x)=x$? Creo que la función de identidad funciona, pero ¿qué acerca de otros? ¿Si $f$ tiene una inversa? Creo que permutaciones pueden estar involucradas, pero no sé cómo avanzar.

Answer 1

Hay $26$ tales funciones.

Desde $f\bigl(f(x)\bigr)=x$cada $x$ %, $f$ es uno a uno y sobreyectiva; en otras palabras, es una biyección. Sin embargo, en otras palabras, es una permutación.

¿Cuántas permutaciones $f$ $\{1,2,3,4,5\}$ ¿hay que $f\circ f=\operatorname{id}$?

• la identidad: $1$;
• las transposiciones: $10$;
• la composición de dos transposiciones disjuntos (por ejemplo $(12)(35)$): $15$.

Answer 2

Sugerencia:

Usted está en lo correcto en la función identidad, que asigna a cada elemento de a sí, ya, pero considere la siguiente función:

$1 \mapsto 2$

$2 \mapsto 1$

$3 \mapsto 3$

$4 \mapsto 4$

$5 \mapsto 5$

¿Qué sucede cuando se redacta la función anterior con la misma? Intente mira más situaciones similares a la de arriba y el resto debe comienzan a ser claro.

Edit: Ya que estoy en mi laptop me puede dar una mejor respuesta ahora!

Por lo tanto, si usted ha mirado mi sugerencia, usted probablemente ha descubierto usted puede intercambiar dos elementos con su función y $(f \circ f)(x)=x$. Así que vamos a contar todas las maneras que usted puede intercambiar exactamente dos elementos; se trata, básicamente, de cuántas maneras se puede escoger dos elementos a partir de los cinco? Cinco elegir dos!

$${5 \choose 2} = \dfrac{5!}{2!(5-2)!}=10.$$

Así que ¿de cuántas maneras distintas podemos intercambiar dos. Pero aún hay más! Podemos cambiar cuatro elementos. Es decir, usted puede intercambiar dos de ellos en una esquina, y luego swap otras dos en la otra esquina. (¿Puedes adivinar por qué nosotros no podemos hacer eso con tres?)

Así que vamos a usar combinaciones para encontrar que como bien. En primer lugar, vamos a intercambiar dos elementos. Así que eso es ${5 \choose 2}$ nuevo -- entonces tenemos tres elementos a la izquierda y nos vamos a recoger dos y cambiar esas, así que de ${3 \choose 2}$. Pero! No queremos accidentalmente cuentan las cosas dos veces! (Ver Trevor Gunn comentario) Que nos da:

$${5 \choose 2} \cdot {3 \choose 2} \cdot \frac{1}{2} = \dfrac{5!}{2!(5-2)!} \cdot \dfrac{3!}{2!(3-2)!} \cdot \frac{1}{2} =10\cdot 3 \cdot \frac{1}{2}=30 \cdot \frac{1}{2} = 15.$$

(Multiplicamos ellos, porque cada vez que recoger dos de nuestro grupo, nosotros, a continuación, elija tres de las restantes, por lo que es un proceso repetitivo, y lo de la operación de los gritos de la repetición?)

Así que en resumen trayendo en que uno de la identidad de la función que tenía en el banquillo, la cantidad total es:

$$1+{5 \choose 2} +{5 \choose 2} \cdot {3 \choose 2} \cdot \frac{1}{2}=1+10+30 \cdot \frac{1}{2}=26.$$

:)

Answer 3

Los componentes conectados de la funcional de caracteres especiales para tales funciones parecen todas

$$ x \to x = f(x)$$

o

$$ x \to f(x) \to f(f(x)) = x $$

El primero es un bucle y ha de generación de función $\frac{x^1}{1!}$. El segundo es un $2$-ciclo y ha de generación de función $\frac{x^2}{2!}$. Para ir desde conectado a la que posiblemente sea desconectado, tomamos $\exp$. Por lo tanto la generación de la función es

$$ \exp(x + x^2/2) = \sum_{n \ge 0} a_n \frac{x^n}{n!} $$

donde $a_n$ es el número de funciones de un conjunto de tamaño $n$ a sí mismo con la propiedad de que $f(f(x)) = x$.

Esto le da

\begin{align} a_n &= n! \left[ x^n \right] \exp(x + x^2/2) \\ &= n! \left[ x^n \right] e^{x^2/2}e^x \\ &= n! \left[ x^n \right] \sum_{k} \frac{x^{2k}}{2^kk!} e^{x} \\ &= \sum_{k} \frac{n!}{2^k k!} \left[ x^{n - 2k} \right] e^{x} \\ &= \sum_{k = 0}^{\lfloor n/2 \rfloor} \frac{n!}{2^k k!(n - 2k)!} \end{align}

Lo que da

$$ a_5 = \sum_{k = 0}^{2} \frac{5!}{2^k k!(5 - 2k)!} = \frac{5!}{5!} + \frac{5!}{2 \cdot 3!} + \frac{5!}{2^3} = 1 + 10+15 = 26. $$

---

Tenga en cuenta que

$$ \frac{n!}{2^k k!(n - 2k)!} $$

cuenta el número de elementos de a $S_n$ que se puede escribir como un producto de $k$ dos ciclos y $n - 2k$ uno de los ciclos.

Answer 4

Esto se puede resolver utilizando recursividad. Deje $u_n$ el número de involuciones de $\{1,\dotsc,n\}$.

Para hacer las cosas concretas, consideraremos $u_5$. Vamos a proceder por preguntar lo $5$ está asignado. A $5$ o algo más. Si es asignado a $5$ hay $u_4$ más continuaciones. Por otro lado, si $5$ obtiene asignada a algunos otros $k$, puede quitar $5$ $k$ a partir del conjunto, y re-etiquetar los elementos restantes $\{1,\dotsc,3\}$.

Ergo, tenemos que $u_5 = u_4 + 4\times u_3$.

En general, tendremos la siguiente relación de recurrencia: $$u_n = u_{n-1} + (n-1)u_{n-2}\\u_1 = 1 \\u_2 = 2$$. This recurrence defines the telephone numbers. The answer to your question is thus $u_5 = 26$.