Contar el número de inyecciones y sobreinyecciones

Question

Dejemos que $A$ sea un conjunto con $n$ elementos y $B$ apostar un set con $n+1$ elementos.

Para que sea inyectiva, para cada $b \in B$ hay exactamente una $a \in A$ tal que $f(a)=b$ . Tengo la impresión de que esto sale a $\frac{(n+1)!}{(n+1-n)!}=(n+1)!$ . Sin embargo, me preocupa que esté contando demasiado.

Dejemos que $A$ sea un conjunto con $n+1$ elementos y $B$ apostar un set con $n$ elementos.

Este me preocupa un poco más. Parece que para cada elección de $b$ hay a lo sumo $n+1$ elementos a elegir de $A$ . Parece que hay como máximo $(n+1)^n$ en las funciones.

Answer 1

En cuanto a la inyectividad, tiene razón. Otra forma de obtener ese número es que tienes $n + 1$ opciones para qué elemento de $B$ para fallar, y hay $n!$ opciones para ordenar el $n$ elementos que golpeamos (imagina $A = \{1, 2, \ldots, n\}$ ).

Para la subjetividad puede haber a lo sumo $1$ colisión. Así que hay ${n + 1} \choose 2$ opciones para la colisión y luego $n!$ formas de pedir el $n$ -(combinamos los dos que corresponden al mismo elemento en un solo "grupo"). Esto da como resultado ${{n + 1} \choose 2}\cdot n! = \frac{1}{2}n\cdot(n+1)!$ .