Conjuntos y funciones contadas

Funciones entre conjuntos finitos: el principio multiplicativo

Sean $A$ y $B$ conjuntos finitos con $|A| = m$ y $|B| = n$. Una función $f: A \to B$ asigna a cada elemento de $A$ exactamente un elemento de $B$.

Para contar el número total de funciones $f: A \to B$: para cada uno de los $m$ elementos de $A$, hay $n$ elecciones posibles (cualquier elemento de $B$), y estas elecciones son independientes. Por el principio multiplicativo, el total es $n^m$.

Ejemplo: el número de palabras de longitud $m$ con alfabeto de $n$ letras es $n^m$. El número de secuencias de $m$ lanzamientos de un dado de $n$ caras es $n^m$.

Interpretación como recurrencia: si $f_m$ denota el número de funciones de un conjunto de $m$ elementos a $B$, entonces $f_m = n \cdot f_{m-1}$ con $f_0 = 1$ (la única función del conjunto vacío). Esto da $f_m = n^m$.

Funciones inyectivas: permutaciones parciales

Una función $f: A \to B$ es inyectiva si elementos distintos de $A$ van a elementos distintos de $B$. Para que existan funciones inyectivas, necesitamos $m \le n$.

Para contar las funciones inyectivas: el primer elemento de $A$ tiene $n$ opciones en $B$, el segundo tiene $n-1$ (cualquiera menos el ya elegido), el tercero tiene $n-2$, y así sucesivamente. El total es:

$n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}$.

Esta cantidad se denota $P(n,m)$ o $n^{\underline{m}}$ (potencia factorial descendente) y cuenta las permutaciones parciales de $m$ elementos elegidos de un conjunto de $n$.

Caso especial $m = n$: el número de biyecciones $f: A \to B$ (cuando $|A| = |B| = n$) es $n!$ — el número de permutaciones de $n$ elementos. Esto conecta las biyecciones con las permutaciones aprendidas en capítulos anteriores.

Funciones sobreyectivas: el principio de inclusión-exclusión

Una función $f: A \to B$ es sobreyectiva (o "sobre") si todo elemento de $B$ tiene al menos una preimagen. Contar las funciones sobreyectivas requiere el principio de inclusión-exclusión (PIE).

Sea $A_i$ el conjunto de funciones $f: A \to B$ tales que el $i$-ésimo elemento de $B$ no está en la imagen (es decir, $f$ "omite" al elemento $b_i$). Una función no sobreyectiva pertenece a algún $A_i$.

Por el PIE, el número de funciones que omiten al menos un elemento de $B$ es:

$|A_1 \cup \cdots \cup A_n| = \sum_i |A_i| - \sum_{i < j} |A_i \cap A_j| + \cdots$.

$|A_i|$ = funciones de $A$ a $B \setminus \{b_i\}$ = $(n-1)^m$. En general, $|A_{i_1} \cap \cdots \cap A_{i_k}|$ = $(n-k)^m$ (funciones que evitan $k$ elementos fijos de $B$). Hay $\binom{n}{k}$ formas de elegir esos $k$ elementos. Luego el número de funciones sobreyectivas es:

$S(m, n) \cdot n! = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^m$.

Aquí $S(m,n)$ es el número de Stirling de segunda especie: el número de particiones del conjunto $A$ (de $m$ elementos) en $n$ bloques no vacíos. La fórmula dice que cada sobreyección de $A$ a $B$ corresponde a una partición de $A$ en $n$ bloques (los "niveles" de $f$) seguida de una asignación de los $n!$ órdenes de $B$.

Números de Stirling y particiones de conjuntos

El número de Stirling de segunda especie $S(m, n)$ (o $\left\{\begin{smallmatrix}m\\n\end{smallmatrix}\right\}$) cuenta el número de formas de particionar un conjunto de $m$ elementos en exactamente $n$ bloques no vacíos.

Recurrencia: para construir una partición de $\{1, 2, \ldots, m\}$ en $n$ bloques, considera el elemento $m$. Puede estar en un bloque solo (lo que equivale a particionar $\{1,\ldots,m-1\}$ en $n-1$ bloques: $S(m-1, n-1)$ formas) o puede estar en un bloque con otros elementos (lo que equivale a agregar $m$ a alguno de los $n$ bloques de una partición de $\{1,\ldots,m-1\}$ en $n$ bloques: $n \cdot S(m-1, n)$ formas). Luego:

$S(m, n) = S(m-1, n-1) + n \cdot S(m-1, n)$.

Casos base: $S(m, 1) = 1$ para $m \ge 1$ (todos los elementos en un solo bloque), $S(m, m) = 1$ (cada elemento en su propio bloque), $S(m, n) = 0$ para $n > m$.

Tabla de valores pequeños: $S(3,2) = 3$, $S(4,2) = 7$, $S(4,3) = 6$. Verificación de $S(3,2) = 3$: las 3 particiones de $\{1,2,3\}$ en 2 bloques son $\{\{1\},\{2,3\}\}$, $\{\{2\},\{1,3\}\}$, $\{\{3\},\{1,2\}\}$. ✓

Aplicaciones directas en problemas olímpicos

Muchos problemas de la ONEM regional que parecen de distribución o asignación son en realidad preguntas sobre funciones. La traducción es: "distribuir $m$ objetos distinguibles en $n$ cajas" = contar funciones de un conjunto de $m$ objetos a un conjunto de $n$ cajas.

Si las cajas pueden quedar vacías: $n^m$ funciones. Si las cajas no pueden quedar vacías: $S(m,n) \cdot n!$ funciones (sobreyectivas). Si cada caja recibe a lo sumo un objeto: $\frac{n!}{(n-m)!}$ funciones (inyectivas, requiere $m \le n$).

Ejemplo de problema: ¿de cuántas formas se pueden repartir 4 premios distintos entre 3 estudiantes distintos de modo que cada estudiante reciba al menos un premio? Esto es contar sobreyecciones de un conjunto de 4 elementos a un conjunto de 3. La respuesta es $\sum_{k=0}^{3} (-1)^k \binom{3}{k}(3-k)^4 = 3^4 - 3 \cdot 2^4 + 3 \cdot 1^4 - 0 = 81 - 48 + 3 = 36$. Alternativamente: $S(4,3) \cdot 3! = 6 \cdot 6 = 36$. ✓