Recuento de proyecciones con inclusión-exclusión

Question

Calcular el número de funciones suryentes $f : [10] [5]$ utilizando el principio I/E.

Con los números de Stirling del segundo tipo, podemos obtener la respuesta de la siguiente manera $S(10,5)5!$ . ¿Cómo puedo obtener la respuesta con el principio I/E?

Answer 1

Para $1 \leq i \leq n$ , dejemos que $A_i$ sea el conjunto que contiene todas las funciones que no se asignan al elemento $i$ en el codominio.

Por ejemplo, las funciones en $A_1$ puede asignarse a cualquier elemento excepto $1$ , por lo que hay $4^{10}$ dichas funciones. Las funciones en $A_1 \cap A_2$ puede asignarse a cualquier elemento excepto $1$ y $2$ , por lo que hay $3^{10}$ dichas funciones.

A partir de estos ejemplos, tenemos $|A_1 \cap \dots \cap A_j| = (5 - j)^{10}$ que puede subsumirse en el principio de inclusión-exclusión para enumerar todos los no -surjetivas. El número total de surjective por lo tanto, las funciones vendrán dadas por $5^{10} - |A_1 \cup \dots \cup A_5|$ .

Answer 2

El número total de funciones es $5^{10}$ . De ellos, el número de funciones que no toman el valor $1$ , $2$ , $3$ , $4$ o $5$ son $4^{10}$ . El número de funciones que no toman el valor $1$ y $2$ , $3$ y $4$ y así sucesivamente son $3^{10}$ . Ampliando este argumento, obtenemos el número de funciones surjetivas $$S=5^{10}-{5\choose{1}}4^{10}+{5\choose{2}}3^{10}-{5\choose{3}}2^{10}+{5\choose{4}}1^{10}=5103000.$$