¿Qué es Variaciones, permutaciones, combinaciones?

Ejemplo 2.14 (Añadir una restricción)

Sigamos con la mesa redonda: entre las $(n-1)!$ mesas de $n \geq 3$ invitados, ¿cuántas sientan separados (no contiguos) a dos invitados dados $A$ y $B$? Cuéntese el complementario. Mesas en las que $A$ y $B$ se sientan juntos: péguense en un solo bloque — quedan $n - 1$ objetos alrededor de la mesa, es decir, $(n-2)!$ disposiciones circulares — y ordénese después la pareja dentro de su bloque ($2$ maneras): $2\,(n-2)!$ mesas con ellos contiguos. Por tanto

mesas los mantienen separados. Comprobaciones: $n = 3$ da $0$ (alrededor de un triángulo todos se tocan) y $n = 4$ da $2$, fáciles de enumerar a mano. El truco del pegado — tratar un bloque forzado como un solo objeto y contar después sus disposiciones internas — es el remedio estándar para las restricciones de contigüidad, lineales o circulares.

Ejemplo 2.18 (Una identidad, dos demostraciones)

La especialización $a = 2$, $b = 1$ del teorema del binomio dice

He aquí la misma identidad sin nada de álgebra. El miembro derecho cuenta las palabras de longitud $n$ sobre el alfabeto $\{0, 1, 2\}$ (regla del producto). Clasifíquese cada palabra por el conjunto $K$ de las posiciones que llevan una letra no nula: elegir $K$ con $\abs K = k$ cuesta $\binom nk$, y después cada posición de $K$ lleva independientemente $1$ o $2$: $2^k$ maneras. La regla de la suma sobre $k$ da el miembro izquierdo. Más allá del placer de que coincidan, las dos demostraciones tienen virtudes distintas: la algebraica se generaliza a cualquier valor de $a$; la combinatoria explica la fórmula y se adapta a restricciones (prohibir la letra $2$ en la última posición, por ejemplo) que ninguna sustitución captura. Mantener vivas las dos técnicas es la destreza práctica que entrena este capítulo.

Ejemplo 2.6 (La finitud es esencial)

Sobre un conjunto finito, la Proposición 2.5 es un atajo poderoso: toda aplicación inyectiva de $E$ en sí mismo es automáticamente una permutación de $E$ — la mitad de la biyectividad sale gratis. Las dos implicaciones se derrumban en los conjuntos infinitos: $n \mapsto n + 1$ es inyectiva de $\N$ en $\N$ pero no alcanza $0$, y la aplicación $\N \to \N$ que envía $0 \mapsto 0$ y $n \mapsto n - 1$ para $n \geq 1$ es sobreyectiva pero no inyectiva. Siempre que se invoca esta proposición, la hipótesis de finitud está haciendo un trabajo real — un tema que el problema del fin de semana del Capítulo 1 explora desde el otro lado, donde los conjuntos infinitos son precisamente los que admiten tales aplicaciones de un conjunto en sí mismo.