Número de funciones sobre un conjunto finito

Question

Si $A$ tiene $n$ elementos, cuántas funciones hay de $A \rightarrow A$ ? ¿Cuántas funciones biyectivas hay desde $A$ a $A$ ?

Mi idea es que hay $n$ posibilidades de $f(a_1)$ , $n$ posibilidades de $f(a_2)$ etc., por lo que debería haber $n^n$ funciones de $A$ a $A$ .

Para que sea biyectiva, debe haber $n$ posibilidades de $f(a_1)$ , $(n-1)$ posibilidades de $f(a_2)$ , $(n-2)$ posibilidades de $f(a_3)$ etc. No sé cómo expresarlo correctamente.

Answer 1

Las funciones totales de A -> A son

$$n^n$$

ya que hay n opciones con las que se puede asignar un elemento del 1er conjunto a n elementos del mismo conjunto de n elementos.

El número de funciones biyectivas es

$$n! = n.(n-1).(n-2)...1$$

como el número de elementos de ambos conjuntos = n, por lo que 1 biyección puede disponerse de n! maneras para obtener otras funciones biyectivas.

Answer 2

Esta idea va acompañada de una bonita convención de anotación. Por ejemplo, si tienes un conjunto $B$ con $n$ elementos y un conjunto $A$ con $m$ elementos, entonces el número de funciones de $A$ a $B$ es $n^m$ .

(Y hay $n\cdot(n-1)\cdots (n-m-1) = \frac{n!}{m!}=\ _nP_m$ funciones inyectivas).

Aquí vemos que la cardinalidad del conjunto de funciones de $A$ a $B$ es $|B|^{|A|}$ . Este conjunto puede ser denotado por $B^A$ . Lo cual tiene sentido de forma independiente, ya que se puede pensar en cada función como un vector en $B^m$ .

Ampliando esta idea, podemos etiquetar el conjunto de secuencias de elementos de $B$ como $B^{\mathbb{N}}$ . Aquí podemos pensar en esto como una colección de funciones de los números naturales a $B$ . Del mismo modo, etiquetamos el conjunto de funciones de $\mathbb{R}$ a $B$ como $B^\mathbb{R}$ .

Finalmente podemos hablar de subconjuntos de los números reales como $2^{\mathbb{R}}$ . Este es el conjunto de funciones de $\mathbb{R}$ al conjunto $\{0,1\}$ . Tenemos una correspondencia con subconjuntos de $\mathbb{R}$ tomando una función $f \in 2^{\mathbb{R}}$ y hacer un conjunto $A_f = \{ x \in \mathbb{R} : f(x) = 1\}$ . Se trata de una correspondencia biyectiva entre estas funciones y los subconjuntos. Por supuesto, esto no se limita a $\mathbb{R}$ .

Lo bueno aquí es que si tomas dos funciones $f, g \in 2^{\mathbb{R}}$ entonces $A_{f\cdot g} = A_f \cap A_g$ . Y tomando $f + g$ para ser la función $(f+g)(x) = max\{f(x), g(x)\}$ entonces tenemos $A_{f+g} = A_f \cup A_g$ .

Sé que esto es un poco por la tangente, pero siempre pensé que era una buena idea.