Enunciado

Considere los conjuntos A = {1, 2, 3, ..., 10} y B = {1, 2, 3, 4, 5, 6, 7}. ¿Cuántas funciones f : A → B satisfacen |f(A)| ≤ 3?

Ideas de solución

• Necesitamos contar funciones donde la imagen tenga a lo sumo 3 elementos.

• Esto significa que la función debe mapear los 10 elementos de A hacia un subconjunto de B que tenga 1, 2 o 3 elementos.

• Podemos usar el Principio de Inclusión-Exclusión:

  • Primero, contamos cuántas formas hay de seleccionar subconjuntos de B de tamaño i (i = 1, 2, 3).
  • Para cada subconjunto de tamaño i, contamos cuántas funciones sobreyectivas hay de A hacia ese subconjunto: Sob(10, i).
  • Aplicamos regla del producto, y luego regla de la suma barriendo en i = 1, 2, 3.