Funciones sobreyectivas usando inclusión-exclusión.
Contar funciones suprayectivas (sobreyectivas) es un problema fundamental en la combinatoria enumerativa, ya que sirve como la base matemática para repartir objetos distinguibles en cajas distinguibles de modo que ninguna caja se quede vacía. Aunque contar el número total de funciones entre dos conjuntos es fácil ($n^m$), poner la condición de que a cada elemento del codominio le tiene que llegar al menos una flecha mete bastante complejidad. Un enfoque constructivo directo suele ser difícil porque tienes que ir checando qué elementos ya fueron "alcanzados" por la función.
El Principio de Inclusión-Exclusión (PIE) da una solución elegante al atacar el problema desde la dirección opuesta. En lugar de contar las funciones que le pegan a cada elemento del objetivo, toma el conjunto total de todas las funciones posibles y réstale las que fallan en pegarle a al menos un elemento. Como los conjuntos de funciones que fallan en elementos específicos se traslapan (una función podría fallar en dos o más elementos), una resta simple contaría de más las exclusiones. El PIE corrige esto sumando y restando sistemáticamente las cuentas de las funciones que fallan en varias combinaciones de elementos.
Esta técnica es clave para resolver problemas avanzados de repartición en olimpiadas de matemáticas, como encontrar de cuántas formas puedes asignar tareas a trabajadores donde a cada trabajador le toca al menos una, o colorear una cuadrícula de modo que uses todos los colores. También sirve para obtener