Matemáticas universitarias — Grado 1 · Bachelor Year 1

2Combinatoria

Contar conjuntos finitos suena elemental — y se vuelve sutil enseguida. Este capítulo define correctamente el cardinal (mediante biyecciones, en el espíritu del Capítulo 1), establece el puñado de principios de recuento de los que se sigue todo lo demás y deduce los recuentos clásicos: listas, permutaciones, subconjuntos, coeficientes binomiales.

2.1 Cardinal de un conjunto finito

Definición 2.1 (Conjunto finito, cardinal)

Para $n \in \N^*$ , se escribe $\intint{1}{n} = \{1, 2, \dots, n\}$ . Un conjunto $E$ es finito cuando $E = \emptyset$ o existe una biyección de $\intint{1}{n}$ sobre $E$ para algún $n \in \N^*$ ; ese $n$ es único (Teorema 2.2) y es el cardinal de $E$ , escrito $\abs{E}$ (con $\abs{\emptyset} = 0$ ).

Teorema 2.2 (El cardinal está bien definido)

Si $m \neq n$ , no existe ninguna biyección de $\intint{1}{m}$ sobre $\intint{1}{n}$ . Con más precisión: si $m > n$ , no existe ninguna inyección de $\intint{1}{m}$ en $\intint{1}{n}$ .

Demostración. Demostramos por inducción sobre $n$ el enunciado: para todo $m > n$ no hay ninguna inyección $\intint{1}{m} \to \intint{1}{n}$ . Para $n = 0$ el conjunto de llegada es vacío y $m \geq 1$ : no existe aplicación alguna. Supongamos el enunciado para $n$ y sea $f \colon \intint{1}{m} \to \intint{1}{n+1}$ una inyección con $m > n + 1$ . Si el valor $n + 1$ no se alcanza, $f$ es una inyección en $\intint{1}{n}$ , en contra de la hipótesis de inducción. En caso contrario, $f(a) = n + 1$ para exactamente un $a$ ; se intercambian $f(a)$ y $f(m)$ (formalmente: se compone con la transposición de los dos valores), de modo que la nueva inyección $g$ cumple $g(m) = n + 1$ . Entonces la restricción de $g$ a $\intint{1}{m-1}$ es una inyección en $\intint{1}{n}$ con $m - 1 > n$ — otra contradicción. ∎

Corolario 2.3 (Principio del palomar)

Si $\abs{E} > \abs{F}$ , ninguna aplicación $f \colon E \to F$ es inyectiva: dos elementos de $E$ comparten imagen.

Demostración. Escríbase $\abs E = m$ , $\abs F = n$ con $m > n$ , y elíjanse biyecciones $u \colon \intint1m \to E$ y $v \colon F \to \intint1n$ . Si $f$ fuese inyectiva, $v \circ f \circ u$ sería una inyección de $\intint1m$ en $\intint1n$ (composición de inyecciones, Proposición 1.26), en contra del Teorema 2.2. ∎

Observación 2.4 (Interludio: ¿por qué el intercambio en la demostración?)

La demostración del Teorema 2.2 contiene el primer paso realmente ingenioso del capítulo, que vale la pena repasar despacio. El obstáculo: para aplicar la hipótesis de inducción se quiere borrar el último punto $m$ de salida y el último punto $n+1$ de llegada, pero $f$ puede enviar otro punto $a$ a $n + 1$ , y entonces borrar el punto de llegada estropea la aplicación en otro sitio. El remedio: componer $f$ con la transposición de los dos valores $f(a)$ y $f(m)$ — una biyección del conjunto de llegada, con lo que la inyectividad se conserva —, tras lo cual el valor problemático $n + 1$ queda en la posición inofensiva $m$ y los dos borrados son limpios. Este patrón de «normalizar primero, cortar después» reaparece: es como la recurrencia de los desarreglos redirige $\sigma^{-1}(n+1)$ en el problema del fin de semana de este capítulo, y como se remiendan las permutaciones en todo el problema del Capítulo 7 sobre el grupo simétrico.

Proposición 2.5 (Inyecciones, sobreyecciones y cardinal)

Sean $E, F$ conjuntos finitos con $\abs{E} = \abs{F}$ , y sea $f \colon E \to F$ . Entonces

f \text{ inyectiva} \iff f \text{ sobreyectiva} \iff f \text{ biyectiva}.

Demostración. Supongamos $f$ inyectiva. Entonces $f$ es una biyección de $E$ sobre $f(E)$ , luego $\abs{f(E)} = \abs{E} = \abs{F}$ . Si $f(E)$ dejase de alcanzar un punto $y_0$ de $F$ , entonces $f$ sería una inyección de $E$ en $F \setminus \{y_0\}$ , un conjunto de cardinal $\abs{F} - 1 < \abs{E}$ — imposible por el principio del palomar. Luego $f(E) = F$ : $f$ es sobreyectiva y, por tanto, biyectiva.

Supongamos $f$ sobreyectiva. Elíjase para cada $y \in F$ una imagen recíproca $s(y) \in E$ ; entonces $f \circ s = \mathrm{id}_F$ , luego $s$ es inyectiva (Proposición 1.26). Por el párrafo anterior aplicado a $s$ (los cardinales son iguales), $s$ es biyectiva. De $f \circ s = \mathrm{id}_F$ se obtiene $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , luego $f$ es biyectiva. Por último, una aplicación biyectiva es por definición inyectiva y sobreyectiva, lo que cierra el ciclo de implicaciones. ∎

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.

Ejemplo 2.7 (La mitad del trabajo, gratis)

Considérese la aplicación $f$ en $\{0, 1, \dots, 6\}$ que envía $k$ al resto de la división de $3k$ por $7$ ; su tabla de valores es

0,\ 3,\ 6,\ 2,\ 5,\ 1,\ 4 .

¿Es $f$ una biyección? Basta con la inyectividad (Proposición 2.5): si $3k$ y $3k'$ dejan el mismo resto, $7$ divide a $3(k - k')$ y, como $7$ es primo y no divide a $3$ , divide a $k - k'$ (lema de Euclides, usado aquí al nivel del volumen anterior y demostrado en el Capítulo 6); con $\abs{k - k'} \leq 6$ esto obliga a $k = k'$ . La sobreyectividad sale gratis — no hace falta resolver $3k \equiv c$ para cada $c$ , aunque la tabla confirme que cada valor aparece exactamente una vez. El atajo es un caballo de batalla: demuestra la invertibilidad de la multiplicación modular (Capítulo 6), sostiene el emparejamiento del teorema de Wilson y vuelve en álgebra lineal como «un endomorfismo de un espacio de dimensión finita es inyectivo si y solo si es sobreyectivo» (Capítulo 19).

2.2 Los principios de recuento

Proposición 2.8 (Reglas de la suma y del producto)

Sean $E, F$ conjuntos finitos.

Si $E \cap F = \emptyset$ , entonces $\abs{E \cup F} = \abs{E} + \abs{F}$ ; más en general, para una partición de $E$ en trozos $E_1, \dots, E_k$ , $\abs{E} = \sum_i \abs{E_i}$ .
En general, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ .
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
El conjunto $F^E$ de todas las aplicaciones de $E$ en $F$ cumple $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

Demostración. (1) Se concatenan enumeraciones: si $E = \{x_1, \dots, x_m\}$ y $F = \{y_1, \dots, y_n\}$ sin repeticiones, entonces $x_1, \dots, x_m, y_1, \dots, y_n$ enumera $E \cup F$ sin repetición (por la disyunción de los dos conjuntos). La inducción lo extiende a $k$ trozos.

(2) $E \cup F$ es la unión disjunta de $E$ y $F \setminus E$ , y $F$ es la unión disjunta de $F \cap E$ y $F \setminus E$ ; luego $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} - \abs{E \cap F}$ .

(3) $E \times F$ es la unión disjunta, para $x \in E$ , de los conjuntos $\{x\} \times F$ , cada uno de cardinal $\abs{F}$ ; aplíquese (1).

(4) Una aplicación de $E = \{x_1, \dots, x_m\}$ en $F$ es exactamente la elección de la $m$ -tupla $(f(x_1), \dots, f(x_m)) \in F^m$ ; esta correspondencia es una biyección, y $\abs{F^m} = \abs{F}^m$ por (3) e inducción.

(5) Los subconjuntos de $E$ se corresponden biyectivamente con las aplicaciones $E \to \{0, 1\}$ (envíese $A$ a su función indicadora); aplíquese (4). ∎

Ejemplo 2.9 (Contar por el complementario)

¿Cuántos códigos PIN de $4$ cifras (cifras $0$ – $9$ , el orden importa, se permiten repeticiones) contienen al menos una cifra repetida? Contarlos directamente obliga a manejar los casos «exactamente una pareja, dos parejas, un trío, un cuarteto» — cinco configuraciones que se solapan. Cuéntese en su lugar el complementario: los códigos son $10^4 = 10\,000$ en total (regla del producto) y los códigos con cuatro cifras distintas son $10 \times 9 \times 8 \times 7 = 5\,040$ ( $4$ -variaciones), de modo que la respuesta es

10^4 - 10 \cdot 9 \cdot 8 \cdot 7 = 10\,000 - 5\,040 = 4\,960 .

Casi la mitad de los PIN repiten alguna cifra. La idea clave: siempre que un recuento se formule con «al menos» o «no todos», pruébese primero con el complementario — la regla de la suma garantiza que $\abs{A} = \abs{E} - \abs{\overline A}$ , y el complementario suele ser una sola configuración limpia.

Ejemplo 2.10 (Caminos en una cuadrícula)

Cuéntense los caminos más cortos de la esquina $(0,0)$ a la esquina $(4, 3)$ de una cuadrícula, moviéndose cada vez un paso a la derecha (R) o un paso hacia arriba (A). Todo camino de estos consta exactamente de $7$ pasos, de los cuales $4$ son R y $3$ son A; recíprocamente, toda palabra de longitud $7$ en las letras R y A con cuatro R describe exactamente un camino. Los caminos se corresponden, pues, biyectivamente con las elecciones de las posiciones de las R:

\binom{7}{4} = 35 .

La idea clave es la codificación: el recuento se volvió trivial en cuanto cada camino se tradujo a una palabra, es decir, a un subconjunto de posiciones — una instancia más del lema de que un recuento correcto es una biyección disfrazada (Método 2.19).

Uno de los 74 = 35 caminos más cortos de (0,0) a (4,3): el camino dibujado codifica la palabra RARRARA, es decir, la elección de las posiciones \1,3,4,6\ para la letra R entre los siete pasos. — Uno de los $\binom74 = 35$ caminos más cortos de $(0,0)$ a $(4,3)$ : el camino dibujado codifica la palabra RARRARA, es decir, la elección de las posiciones $\{1,3,4,6\}$ para la letra R entre los siete pasos.

2.3 Listas, permutaciones, subconjuntos

Definición 2.11 (Variaciones, permutaciones, combinaciones)

Sea $E$ un conjunto con $\abs{E} = n$ y sea $0 \leq k \leq n$ .

Una $k$ -variación de $E$ es una $k$ -tupla inyectiva de elementos de $E$ (una selección ordenada sin repetición);
una permutación de $E$ es una biyección de $E$ en sí mismo — equivalentemente, una $n$ -variación;
una $k$ -combinación es un subconjunto de $E$ con $k$ elementos (una selección no ordenada y sin repetición). Su número se escribe $\binom{n}{k}$ , que se lee « $n$ sobre $k$ » .

Teorema 2.12 (Los tres recuentos)

Con $n = \abs{E}$ y $0 \leq k \leq n$ :

el número de $k$ -variaciones de $E$ es $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
el número de permutaciones de $E$ es $n!$ ;
$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

Demostración. (1) Se elige la primera coordenada ( $n$ maneras), después la segunda ( $n - 1$ elecciones restantes), …, y por último la $k$ -ésima ( $n - k + 1$ elecciones). Formalmente, se procede por inducción sobre $k$ . Para $k = 1$ hay $n$ tuplas inyectivas de un término. Supóngase el recuento para $k - 1$ . Cada $k$ -variación $(x_1, \dots, x_k)$ se obtiene a partir de exactamente una $(k-1)$ -variación — su truncamiento $(x_1, \dots, x_{k-1})$ — añadiendo una última coordenada fuera de $\{x_1, \dots, x_{k-1}\}$ , para la cual hay exactamente $n - (k - 1)$ valores disponibles. El truncamiento reparte así las $k$ -variaciones en clases de tamaño común $n - k + 1$ indexadas por las $(k-1)$ -variaciones, y la regla de la suma da

\frac{n!}{(n-k+1)!}\;(n - k + 1) = \frac{n!}{(n-k)!} .

(2) es (1) con $k = n$ .

(3) Cada $k$ -subconjunto se ordena de $k!$ maneras distintas en $k$ -variaciones, y toda $k$ -variación proviene de exactamente un subconjunto: luego $\frac{n!}{(n-k)!} = \binom nk \cdot k!$ . ∎

Ejemplo 2.13 (Mesas redondas: cocientar por una simetría)

¿De cuántas maneras pueden sentarse $n$ invitados alrededor de una mesa redonda, considerando idénticas dos disposiciones cuando cada invitado tiene los mismos vecinos a izquierda y derecha, es decir, salvo rotación? Cada disposición circular corresponde a exactamente $n$ disposiciones lineales (córtese el círculo por cualquiera de los $n$ lugares), de modo que los $n!$ órdenes lineales se agrupan en bloques de $n$ :

\frac{n!}{n} = (n-1)! \quad\text{circular seatings.}

Equivalentemente: siéntese en cualquier sitio a un invitado distinguido (con lo que se elimina la libertad de rotación) y ordénense después los $n - 1$ invitados restantes en el sentido de las agujas del reloj. Para $n = 6$ : $120$ mesas. Las dos soluciones ilustran los dos remedios habituales contra el recuento por exceso: dividir por el número exacto de repeticiones, o romper la simetría fijando un objeto. Ambos exigen que el grupo de repeticiones tenga el mismo tamaño para toda configuración — algo que la demostración anterior de la fórmula $\binom nk = \frac{n!}{k!\,(n-k)!}$ también usó, con $k!$ en lugar de $n$ .

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

(n-1)! - 2\,(n-2)! = (n-2)!\,\bigl((n - 1) - 2\bigr) = (n-3)\,(n-2)!

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.

Proposición 2.15 (Identidades básicas)

Para $0 \leq k \leq n$ :

\binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad (1 \leq k \leq n-1), \qquad \sum_{k=0}^{n} \binom{n}{k} = 2^n .

Demostración. Primera identidad: $A \mapsto E \setminus A$ es una biyección entre los $k$ -subconjuntos y los $(n-k)$ -subconjuntos. Regla de Pascal: fíjese un elemento $a \in E$ ; los $k$ -subconjuntos se reparten entre los que contienen $a$ (elíjanse los $k - 1$ restantes: $\binom{n-1}{k-1}$ ) y los que evitan $a$ ( $\binom{n-1}{k}$ ). Tercera identidad: los dos miembros cuentan todos los subconjuntos de $E$ , repartidos por tamaño en el de la izquierda (Proposición 2.8 (1) y (5)). ∎

Teorema 2.16 (Teorema del binomio)

Para todos $a, b$ de un anillo conmutativo (por ejemplo $\R$ o $\C$ ) y todo $n \in \N$ :

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{\,n-k} .

Demostración. Al desarrollar $(a+b)(a+b)\cdots(a+b)$ por distributividad se obtiene un término por cada elección, en cada factor, de $a$ o de $b$ : el término $a^k b^{n-k}$ aparece una vez por cada manera de elegir cuáles $k$ de los $n$ factores aportan $a$ — es decir, $\binom nk$ veces. (Alternativamente: inducción sobre $n$ usando la regla de Pascal.) ∎

Ejemplo 2.17

Dos especializaciones clásicas: $a = b = 1$ recupera $\sum_k \binom nk = 2^n$ ; $a = -1$ , $b = 1$ da $\sum_{k} (-1)^k \binom nk = 0$ para $n \geq 1$ : entre los subconjuntos de un conjunto no vacío, exactamente la mitad tienen cardinal par.

Ejemplo 2.18 (Una identidad, dos demostraciones)

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

\sum_{k=0}^{n} \binom nk\,2^k = 3^n .

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.

Método 2.19 (¿Qué recuento se aplica?)

Antes de calcular, respóndanse dos preguntas sobre la selección: ¿importa el orden?, ¿se permiten repeticiones?

	importa el orden	no importa el orden
sin repetición	$\dfrac{n!}{(n-k)!}$	$\dbinom{n}{k}$
[6pt] con repetición	$n^k$	(Ejercicio 2.10)

Búsquese después una biyección o una partición que reduzca el problema a estos recuentos modelo; un recuento correcto es una biyección disfrazada.

Observación 2.20 (Errores frecuentes al contar)

Sumar casos no disjuntos. La regla de la suma exige una partición; si una configuración puede cumplir dos casos a la vez, se cuenta dos veces — el remedio es la inclusión–exclusión (Teorema 2.24) o un reparto de casos más fino.
Ordenado frente a no ordenado. Elegir «un comité de dos» es $\binom n2$ , no $n(n-1)$ : decídase antes de calcular si la selección lleva un orden y, si el recuento ordenado resulta más fácil, divídase al final por el número de ordenaciones — pero solo cuando cada objeto no ordenado provenga del mismo número de objetos ordenados.
Elecciones por etapas que no son independientes. La regla del producto exige que el número de opciones de cada etapa no dependa de las elecciones anteriores. «Elíjase un capitán y después un subcapitán distinto» está bien ( $n(n-1)$ ); «elíjanse dos jugadores que se lleven bien» no es un producto por etapas en absoluto.
Contar dos veces por construcción. Construir cada objeto dos veces — por ejemplo, contar las manos con al menos un as como (elegir un as) $\times$ (elegir $4$ cartas más) — cuenta de más las manos con dos ases. «Al menos» pide casi siempre el complementario (Ejemplo 2.9).

Ejemplo 2.21 (Un recuento de póquer)

De una baraja de $52$ cartas, el número de manos de $5$ cartas es $\binom{52}{5} = 2\,598\,960$ . Manos con exactamente un as: elíjase el as ( $4$ maneras) y después $4$ cartas entre las $48$ que no son ases: $4 \binom{48}{4} = 778\,320$ . La regla del producto se aplica porque la elección se reparte en etapas independientes.

Método 2.22 (Doble recuento)

Para demostrar una identidad entre dos expresiones combinatorias, búsquese un único conjunto finito que ambos miembros cuenten —típicamente un conjunto de pares— y evalúese su cardinal de dos maneras distintas. El prototipo es el lema de los apretones de manos: en una fiesta, cuéntense los pares (persona, mano estrechada). Sumando sobre las personas se obtiene $\sum_p d_p$ (el número de apretones de cada persona $p$ ); sumando sobre los apretones se obtiene el doble del número de apretones (cada uno involucra a dos personas). Luego $\sum_p d_p$ es par — de modo que el número de personas que dieron un número impar de apretones es siempre par, conclusión nada trivial obtenida sin fórmula alguna. El mismo motor mueve el Ejercicio 2.12 y varias preguntas del problema del fin de semana.

Ejemplo 2.23 (El subconjunto medio)

¿Cuál es el cardinal medio de un subconjunto de un conjunto $E$ de $n$ elementos, siendo los $2^n$ subconjuntos igualmente probables? Cuéntense dos veces los pares $(A, a)$ con $a \in A$ : sumando sobre los subconjuntos se obtiene $\sum_A \abs A$ , el total buscado; sumando sobre los elementos se obtiene $n \cdot 2^{n-1}$ (cada uno de los $n$ elementos está exactamente en la mitad de los subconjuntos — emparéjese cada $A$ que contiene $a$ con $A \setminus \{a\}$ ). Por tanto

\frac{1}{2^n}\sum_{A \subseteq E} \abs A = \frac{n\,2^{n-1}}{2^n} = \frac n2 :

los subconjuntos están, en promedio, medio llenos — como también predice la simetría $A \leftrightarrow \overline A$ (que empareja los tamaños $k$ y $n - k$ ). Dos demostraciones, una sola respuesta, y ambas evitan el cálculo directo $\sum_k k\binom nk$ del Ejercicio 2.5: un emparejamiento bien elegido sustituye a menudo a una identidad.

2.4 Inclusión–exclusión

Teorema 2.24 (Inclusión–exclusión)

Para conjuntos finitos $A_1, \dots, A_p$ :

\Bigl|\, \bigcup_{i=1}^{p} A_i \,\Bigr| = \sum_{\emptyset \neq I \subseteq \intint{1}{p}} (-1)^{\abs{I}+1} \Bigl|\, \bigcap_{i \in I} A_i \,\Bigr| .

Para $p = 3$ : $\abs{A \cup B \cup C} = \abs A + \abs B + \abs C - \abs{A \cap B} - \abs{A \cap C} - \abs{B \cap C} + \abs{A \cap B \cap C}$ .

Demostración. Fíjese un elemento $x$ de la unión y cuéntese su contribución al miembro derecho. Sea $J = \{i : x \in A_i\}$ , de cardinal $m \geq 1$ . El elemento $x$ se cuenta una vez en $\abs{\bigcap_{i \in I} A_i}$ exactamente cuando $\emptyset \neq I \subseteq J$ , con signo $(-1)^{\abs I + 1}$ ; su contribución total es

\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1} = 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1

por el Ejemplo 2.17. Así pues, cada elemento de la unión se cuenta exactamente una vez. ∎

Ejemplo 2.25 (Contar enteros coprimos)

¿Cuántos enteros de $\intint1{120}$ son coprimos con $120 = 2^3 \times 3 \times 5$ ? Un entero comparte un factor con $120$ exactamente cuando es divisible por $2$ , $3$ o $5$ , así que se cuenta el complementario de $A_2 \cup A_3 \cup A_5$ , donde $A_d$ reúne los múltiplos de $d$ . Dentro de $\intint1{120}$ , los múltiplos de $d$ son $120/d$ siempre que $d$ divida a $120$ — sin necesidad de partes enteras — y $A_2 \cap A_3 = A_6$ , etc. Inclusión–exclusión:

\abs{A_2 \cup A_3 \cup A_5} = 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,

luego $120 - 88 = 32$ enteros son coprimos con $120$ . Es instructivo reagrupar el cálculo como un producto:

120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 - \frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 32 :

desarrollar los tres paréntesis reproduce exactamente los ocho términos con signo de la inclusión–exclusión, uno por cada subconjunto de $\{2, 3, 5\}$ . Esta forma de producto define la función indicatriz de Euler, cuyo papel aritmético asoma con las congruencias del Capítulo 6 y se desarrolla en el volumen del segundo año.

Ejemplo 2.26 (Desarreglos)

Un desarreglo es una permutación sin puntos fijos. Sea $A_i$ el conjunto de las permutaciones de $\intint{1}{n}$ que fijan $i$ ; entonces $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ , y la inclusión–exclusión cuenta las permutaciones con al menos un punto fijo; los desarreglos son

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .

Como $\sum (-1)^k / k! \to \eu^{-1}$ (véase el Capítulo 17), alrededor del $37\,\%$ de todas las permutaciones son desarreglos, sea cual sea $n$ .

Observación 2.27 (Dónde se usa este capítulo)

Los coeficientes binomiales son los objetos más reutilizados de este capítulo: mueven el teorema del binomio en el Capítulo 8 (desarrollo de $(X + a)^n$ ), la fórmula de Leibniz para la derivada $n$ -ésima de un producto en el Capítulo 14 y los coeficientes de los desarrollos de Taylor en el Capítulo 16. Las permutaciones vuelven como grupo — con la signatura construida a partir del recuento de inversiones — en el Capítulo 7, y la signatura define a su vez los determinantes en el Capítulo 22. La inclusión–exclusión y los principios de recuento son el esqueleto finito de la probabilidad discreta, desarrollada en el volumen del segundo año; los números de desarreglos del Ejemplo 2.26 se estudian a fondo en el problema del fin de semana.

2.5 Ejercicios

Ejercicio 2.1 ★

Una matrícula consta de dos letras (A–Z), después tres cifras y después dos letras. ¿Cuántas matrículas son posibles? ¿Y cuántas sin ninguna letra repetida entre las cuatro?

Solución

Solución de Ejercicio 2.1.

Etapas independientes y regla del producto: $26^2 \times 10^3 \times 26^2 = 26^4 \times 1000 = 456\,976\,000$ matrículas. Con las cuatro letras distintas dos a dos, las etapas de letras forman una $4$ -variación del alfabeto: $26 \times 25 \times 24 \times 23 = 358\,800$ maneras, luego $358\,800 \times 1000 = 358\,800\,000$ matrículas.

Ejercicio 2.2 ★

¿Cuántos anagramas (reordenaciones de las letras, con sentido o sin él) tiene la palabra cuerpo? ¿Y banana?

Solución

Solución de Ejercicio 2.2.

cuerpo tiene $6$ letras distintas: $6! = 720$ anagramas. banana tiene $6$ letras con repeticiones ( $3$ aes, $2$ enes, $1$ be): cada anagrama queda determinado por las posiciones de las aes ( $\binom 63$ elecciones) y después por las de las enes entre los $3$ huecos restantes ( $\binom 32$ ), ocupando la be el último hueco: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ anagramas (equivalentemente, $6!/(3!\,2!\,1!) = 60$ ).

Ejercicio 2.3 ★

Se elige un comité de $4$ personas entre $7$ mujeres y $5$ hombres. ¿Cuántos comités hay en total? ¿Cuántos con exactamente $2$ mujeres? ¿Cuántos con al menos un hombre?

Solución

Solución de Ejercicio 2.3.

Total: $\binom{12}{4} = 495$ . Exactamente $2$ mujeres: se eligen ellas ( $\binom 72 = 21$ ) y $2$ hombres ( $\binom 52 = 10$ ): $210$ comités. Al menos un hombre: complementario de «ningún hombre», $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$ .

Ejercicio 2.4 ★

Demuéstrese que en cualquier grupo de $13$ personas dos comparten mes de nacimiento, y que entre $n + 1$ enteros cualesquiera elegidos de $\intint{1}{2n}$ hay dos consecutivos. (Palomar las dos veces: nómbrense las cajas.)

Solución

Solución de Ejercicio 2.4.

Cumpleaños: las cajas son los $12$ meses; $13$ personas en $12$ cajas obligan a que dos caigan en la misma (Corolario 2.3).

Enteros consecutivos: las cajas son las $n$ parejas $\{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\}$ , que parten $\intint{1}{2n}$ . Al elegir $n + 1$ enteros, dos caen en la misma pareja, y los dos elementos de una pareja son consecutivos.

Ejercicio 2.5 ★

Calcúlese $\sum_{k=0}^{n} k \binom{n}{k}$ . Indicación: derívese $(1 + x)^n$ , o úsese $k \binom nk = n \binom{n-1}{k-1}$ (demuéstrese).

Solución

Solución de Ejercicio 2.5.

Para $1 \leq k \leq n$ ,

k \binom nk = k\,\frac{n!}{k!\,(n-k)!} = n\,\frac{(n-1)!}{(k-1)!\,(n-k)!} = n \binom{n-1}{k-1}.

Sumando y reindexando con $j = k - 1$ :

\sum_{k=0}^{n} k \binom nk = n \sum_{j=0}^{n-1} \binom{n-1}{j} = n\, 2^{n-1}

por la Proposición 2.15. (Alternativa: derívese $(1+x)^n = \sum_k \binom nk x^k$ y hágase $x = 1$ .)

Ejercicio 2.6 ★★

¿Cuántas aplicaciones estrictamente crecientes hay de $\intint{1}{k}$ en $\intint{1}{n}$ ? Dedúzcase el número de aplicaciones crecientes (no necesariamente en sentido estricto). Indicación para el segundo recuento: $f$ creciente $\mapsto$ $g(i) = f(i) + i - 1$ .

Solución

Solución de Ejercicio 2.6.

Una aplicación estrictamente creciente $f \colon \intint{1}{k} \to \intint{1}{n}$ queda determinada por su imagen, un $k$ -subconjunto de $\intint{1}{n}$ (basta listar el subconjunto en orden creciente); recíprocamente, cada $k$ -subconjunto da exactamente una aplicación así. Luego hay $\binom nk$ aplicaciones estrictamente crecientes.

Si $f$ es solo creciente, póngase $g(i) = f(i) + i - 1$ . Entonces $g$ es estrictamente creciente (entre dos argumentos consecutivos, $f$ gana $\geq 0$ e $i - 1$ gana $1$ ) con valores en $\intint{1}{n + k - 1}$ ; y $f(i) = g(i) - i + 1$ recupera $f$ a partir de cualquier $g$ estrictamente creciente en $\intint{1}{n+k-1}$ . Es una biyección, luego hay $\binom{n + k - 1}{k}$ aplicaciones crecientes.

Ejercicio 2.7 ★★

(Vandermonde) Demuéstrese, contando los $k$ -subconjuntos de un conjunto repartido en dos bloques de tamaños $m$ y $n$ :

\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j} .

Dedúzcase $\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$ .

Solución

Solución de Ejercicio 2.7.

Repártase un conjunto $E$ de $m + n$ elementos en dos bloques $M$ ( $m$ elementos) y $N$ ( $n$ elementos). Un $k$ -subconjunto de $E$ contiene $j$ elementos de $M$ ( $0 \leq j \leq k$ ) y $k - j$ de $N$ ; para $j$ fijo hay $\binom mj \binom{n}{k-j}$ subconjuntos así, y los casos $j = 0, \dots, k$ parten los $k$ -subconjuntos. La regla de la suma da la identidad de Vandermonde.

Con $m = n = k$ : $\binom{2n}{n} = \sum_{j=0}^{n} \binom nj \binom{n}{n-j} = \sum_{j=0}^{n} \binom nj^2$ , usando $\binom{n}{n-j} = \binom nj$ .

Ejercicio 2.8 ★★

¿Cuántos enteros de $\intint{1}{1000}$ son divisibles por $2$ , por $3$ o por $5$ ? (Inclusión–exclusión; $\lfloor 1000/6 \rfloor$ cuenta los múltiplos de $6$ , etc.)

Solución

Solución de Ejercicio 2.8.

Sea $A_d$ el conjunto de los múltiplos de $d$ en $\intint{1}{1000}$ , de modo que $\abs{A_d} = \lfloor 1000/d \rfloor$ . Inclusión–exclusión (Teorema 2.24) con $A_2, A_3, A_5$ , teniendo en cuenta que $A_2 \cap A_3 = A_6$ , etc.:

500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 .

Luego $734$ enteros son divisibles por $2$ , $3$ o $5$ .

Ejercicio 2.9 ★★

Cuéntense las sobreyecciones de un conjunto de $4$ elementos sobre un conjunto de $2$ elementos; después, sobre uno de $3$ elementos. Indicación: cuéntense las aplicaciones no sobreyectivas con inclusión–exclusión sobre los valores no alcanzados.

Solución

Solución de Ejercicio 2.9.

Sobre $2$ elementos: todas las $2^4 = 16$ aplicaciones salvo las $2$ constantes: $14$ sobreyecciones.

Sobre $3$ elementos: por inclusión–exclusión sobre los valores no alcanzados, el número de aplicaciones de un conjunto de $4$ elementos en uno de $3$ que dejan de alcanzar al menos un valor es $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ ; aplicaciones en total, $3^4 = 81$ ; sobreyecciones: $81 - 45 = 36$ . (Comprobación: una sobreyección de $4$ sobre $3$ elementos repite exactamente un valor: elíjase el valor repetido ( $3$ ), la pareja que va a él ( $\binom 42 = 6$ ) y una biyección para el resto ( $2$ ): $3 \times 6 \times 2 = 36$ .)

Ejercicio 2.10 ★★

(Estrellas y barras) Demuéstrese que el número de selecciones de $k$ objetos entre $n$ con repetición, sin tener en cuenta el orden —equivalentemente, el número de $(x_1, \dots, x_n) \in \N^n$ con $x_1 + \dots + x_n = k$ — es $\binom{n + k - 1}{k}$ . Indicación: codifíquese una solución como una fila de $k$ estrellas y $n - 1$ barras.

Solución

Solución de Ejercicio 2.10.

Una solución de $x_1 + \dots + x_n = k$ en $\N^n$ se codifica como una fila de $k$ estrellas y $n - 1$ barras: escríbanse $x_1$ estrellas, una barra, $x_2$ estrellas, una barra, …, terminando con $x_n$ estrellas. Esto es una biyección sobre las palabras de longitud $k + n - 1$ con $k$ estrellas y $n - 1$ barras, y esas palabras quedan determinadas por las posiciones de las estrellas: $\binom{n + k - 1}{k}$ . Las selecciones con repetición se corresponden con las soluciones de la ecuación ( $x_i$ = número de copias del objeto $i$ ), así que el recuento es el mismo.

Ejercicio 2.11 ★★★

Demuéstrese con detalle la fórmula del Ejemplo 2.26 para $D_n$ y dedúzcase $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (demuéstrese esta identidad también de forma directa, clasificando las permutaciones por su conjunto de puntos fijos).

Solución

Solución de Ejercicio 2.11.

Con $A_i = \{\sigma : \sigma(i) = i\}$ , una permutación de $\bigcap_{i \in I} A_i$ fija todos los $i \in I$ y permuta libremente los otros $n - \abs I$ puntos: $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ . Inclusión–exclusión:

\Bigl|\bigcup_i A_i\Bigr| = \sum_{k=1}^{n} (-1)^{k+1} \binom nk (n-k)! = \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} ,

pues hay $\binom nk$ subconjuntos $I$ de tamaño $k$ . Por tanto

D_n = n! - \Bigl|\bigcup_i A_i\Bigr| = n!\Bigl(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\Bigr) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .

Para la segunda identidad: clasifíquense las permutaciones $\sigma$ de $\intint{1}{n}$ por su conjunto de puntos fijos $F(\sigma)$ . Para un $k$ -subconjunto $F$ fijo, las permutaciones con $F(\sigma) = F$ son exactamente los desarreglos del complementario: hay $D_{n-k}$ . Sumando sobre las $\binom nk$ elecciones de $F$ para cada $k$ : $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$ .

Ejercicio 2.12 ★★★

Para $n \in \N^*$ , demuéstrese mediante un doble recuento de pares (subconjunto, elemento marcado):

\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1}, \qquad\text{y después}\qquad \sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .

Para la segunda: cuéntense los pares de elementos marcados, iguales o no.

Solución

Solución de Ejercicio 2.12.

Primera identidad. Cuéntense los pares $(A, a)$ con $A \subseteq E$ ( $\abs E = n$ ) y $a \in A$ . Por tamaño de $A$ : $\sum_k \binom nk k$ pares. Eligiendo primero el elemento marcado: $n$ elecciones para $a$ y después cualquier subconjunto de los $n - 1$ elementos restantes para completar $A$ : $n\,2^{n-1}$ pares.

Segunda identidad. Cuéntense las ternas $(A, a, b)$ con $a, b \in A$ (posiblemente $a = b$ ). Por tamaño: $\sum_k k^2 \binom nk$ . Directamente: o bien $a = b$ ( $n\,2^{n-1}$ ternas, recuento anterior), o bien $a \neq b$ ( $n(n-1)$ elecciones ordenadas y después cualquier subconjunto de los otros $n - 2$ elementos: $n(n-1)\,2^{n-2}$ ). En total

n\,2^{n-1} + n(n-1)\,2^{n-2} = n\,2^{n-2}\,(2 + n - 1) = n(n+1)\,2^{n-2} .

2.6 Problema: desarreglos, o las cartas mal repartidas

Problema 2.1

Una secretaria mete $n$ cartas al azar en $n$ sobres con destinatario: ¿qué probabilidad hay de que nadie reciba su carta? Esta pregunta clásica (Montmort, 1708) conduce a los números de desarreglos $D_n$ del Ejemplo 2.26. La fórmula de inclusión–exclusión es solo la jugada de apertura: este problema desarrolla las recurrencias que calculan $D_n$ , dos demostraciones independientes más de la fórmula, el llamativo teorema de que $D_n$ es el entero más próximo a $n!/\eu$ , la distribución completa de los puntos fijos de una permutación aleatoria y la curiosa aritmética de la sucesión $(D_n)$ . En todo el problema, $D_n$ denota el número de desarreglos (permutaciones sin puntos fijos) de $\intint1n$ , con el convenio $D_0 = 1$ (la permutación vacía no tiene puntos fijos).

Parte I — Casos pequeños y censo de puntos fijos.

Calcúlense $D_1, D_2, D_3$ directamente, y $D_4$ enumerando los desarreglos de $\{1, 2, 3, 4\}$ agrupados según el valor de $\sigma(1)$ . (Debe salir $D_4 = 9$ .)
Para $0 \leq k \leq n$ , pruébese que el número $P_k(n)$ de permutaciones de $\intint1n$ con exactamente $k$ puntos fijos es $\binom nk D_{n-k}$ .
Compruébese el censo para $n = 4$ : calcúlense $P_0(4), \dots, P_4(4)$ y véase que suman $4! = 24$ . ¿Qué es más probable con cuatro cartas: ningún acierto o exactamente un acierto?
Mediante un doble recuento (Método 2.22) de los pares $(\sigma, i)$ con $\sigma(i) = i$ , pruébese que

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

en promedio, una permutación aleatoria tiene exactamente un punto fijo, sea cual sea $n \geq 1$ .

Parte II — Dos recurrencias y dos demostraciones nuevas de la fórmula.

Demuéstrese combinatoriamente, para $n \geq 1$ :

$D_{n+1} = n\,(D_n + D_{n-1}) .$

(Clasifíquense los desarreglos $\sigma$ de $\intint1{n+1}$ según $j = \sigma(n+1)$ y después según si $\sigma(j) = n + 1$ ; en el caso $\sigma(j) \neq n+1$ , constrúyase una biyección con los desarreglos de $\intint1n$ redirigiendo hacia $j$ la imagen recíproca de $n + 1$ .) Compruébese la recurrencia numéricamente hasta $D_6$ .
Poniendo $u_n = D_n - n D_{n-1}$ , dedúzcase de la pregunta 5 que $u_{n+1} = -u_n$ , y conclúyase la segunda recurrencia:

$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$
A partir de la pregunta 6, demuéstrese por inducción la fórmula del Ejemplo 2.26,

$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$

— una demostración totalmente independiente de la inclusión–exclusión.
(Inversión binomial) Sean $(a_n)$ y $(b_n)$ dos sucesiones tales que $a_n = \sum_{k=0}^n \binom nk b_k$ para todo $n$ . Demuéstrese que

$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k \qquad (n \in \N).$

(Establézcase primero la identidad trinomial $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$ y úsese después la suma alternada de una fila del Ejemplo 2.17.)
Aplíquese la pregunta 8 a la identidad $n! = \sum_k \binom nk D_{n-k}$ del Ejercicio 2.11 para obtener una tercera demostración de la fórmula de $D_n$ .

Parte III — El entero más próximo a $n!/\eu$ . Admítase en esta parte — la teoría se construye en el Capítulo 17 — que $\eu^{-1} = \lim_{n \to \infty} s_n$ , donde $s_n = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ , con la cota estricta de series alternadas $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ para todo $n$ .

Pruébese que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ para todo $n \in \N$ .
Dedúzcase el teorema estrella: para todo $n \geq 1$ , $D_n$ es el entero más próximo a $n!/\eu$ . ¿Por qué necesita el argumento que $n \geq 1$ ?
Determínese el signo del error: pruébese que $D_n > n!/\eu$ exactamente cuando $n$ es par. (Localícese el primer término despreciado de la serie alternada.)
Calcúlense $D_7$ hasta $D_{10}$ con la recurrencia de la pregunta 5 y compruébese después $D_{10}$ frente a $10!/\eu$ ( $10! = 3\,628\,800$ , $\eu \approx 2.718281828$ ).
(La probabilidad del guardarropa) Sea $p_n = D_n/n!$ la probabilidad de que una permutación tomada al azar uniformemente sea un desarreglo. Pruébese que $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ y calcúlese $p_6$ con cinco decimales. Coméntese: ¿por qué la respuesta a la pregunta de Montmort es esencialmente independiente de $n$ , ya con una docena de cartas?

Parte IV — La distribución de los puntos fijos.

Fíjese $k \in \N$ . Pruébese que la proporción de permutaciones de $\intint1n$ con exactamente $k$ puntos fijos cumple

$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!} \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$

(Estos valores límite, que suman $1$ , forman la distribución de Poisson de parámetro $1$ , objeto central del curso de probabilidad del volumen del segundo año.)
Mediante un doble recuento de las ternas $(\sigma, i, j)$ con $i \neq j$ fijados ambos por $\sigma$ , pruébese que $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\, (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ para $n \geq 2$ . Combinado con la pregunta 4: el promedio de $\abs{\mathrm{Fix}}^2$ es $2$ , de modo que la «dispersión» (varianza) del número de puntos fijos vale $1$ — de nuevo independiente de $n$ , de nuevo acorde con la ley de Poisson.
Calcúlese la proporción de permutaciones con al menos un punto fijo para $n = 4, 5, 6$ (como fracciones y con cuatro decimales) y compárese con $1 - \eu^{-1} \approx 0.6321$ .
Pruébese directamente — sin necesidad de límites — que $s_{n+2} - s_n = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , y dedúzcase que las probabilidades $p_n = s_n$ de la pregunta 14 oscilan: $p_0 > p_2 > p_4 > \dots$ y $p_1 < p_3 < p_5 < \dots$ , decreciendo los valores pares (resp. creciendo los impares) hacia el límite común $\eu^{-1}$ .
(Amigo invisible) $n$ personas sacan cada una un nombre de una bolsa; si alguien saca su propio nombre, todo el sorteo se repite desde cero. Usando el hecho estándar de que un suceso de probabilidad $p$ requiere en promedio $1/p$ intentos, estímese el número medio de sorteos completos necesarios y conclúyase que el procedimiento cuesta en promedio unos $\eu \approx 2.72$ sorteos, esencialmente con independencia de $n$ .

Parte V — La aritmética de $D_n$ , y una síntesis.

Refínese la pregunta 5: pruébese que, para $j \in \intint2n$ fijo, los desarreglos de $\intint1n$ con $\sigma(1) = j$ son exactamente $D_{n-1} + D_{n-2}$ , independientemente de $j$ . Dedúzcase que $n - 1$ divide a $D_n$ para todo $n \geq 2$ .
Demuéstrese que $D_n$ es impar si y solo si $n$ es par. (Trabájese módulo $2$ en la recurrencia de la pregunta 6.)
Demuéstrese que $D_n \equiv (-1)^n \pmod n$ para $n \geq 1$ y compruébese la congruencia en la última cifra de $D_{10}$ .
Pruébese, a partir de la pregunta 6, que $\dfrac{D_n}{D_{n-1}} = n + \dfrac{(-1)^n}{D_{n-1}}$ para $n \geq 3$ , de modo que el cociente de dos números de desarreglos consecutivos es casi exactamente $n$ ; explíquese en una frase por qué esto es coherente con $D_n \approx n!/\eu$ .
¿Dónde ha usado exactamente este problema: (i) las reglas de la suma y del producto; (ii) el doble recuento; (iii) el teorema del binomio; (iv) la cota admitida de series alternadas? Una frase para cada uno.
Síntesis. La fórmula de $D_n$ tiene ya tres demostraciones (inclusión–exclusión, recurrencia más inducción, inversión binomial). En un párrafo breve, compárese qué explica cada una: cuál calcula más rápido, cuál se generaliza a otros recuentos de puntos fijos y cuál revela por qué aparece $\eu$ en un problema sobre sobres.

Solución

Solución de Problema 2.1.

1. $D_1 = 0$ (la única permutación fija $1$ ), $D_2 = 1$ (el intercambio), $D_3 = 2$ (en notación de una línea: $231$ y $312$ ). Para $n = 4$ , agrupando por $\sigma(1)$ : con $\sigma(1) = 2$ los desarreglos son $2143$ , $2341$ , $2413$ ; con $\sigma(1) = 3$ : $3142$ , $3412$ , $3421$ ; con $\sigma(1) = 4$ : $4123$ , $4312$ , $4321$ . Tres en cada grupo: $D_4 = 9$ .

2. Una permutación con exactamente $k$ puntos fijos queda determinada por la elección de su conjunto de puntos fijos $F$ ( $\binom nk$ maneras) junto con su restricción al complementario, que debe ser una permutación de $n - k$ puntos sin ningún punto fijo ( $D_{n-k}$ maneras). Las dos elecciones son independientes y la correspondencia es biyectiva: $P_k(n) = \binom nk D_{n-k}$ .

3. $P_0(4) = D_4 = 9$ ; $P_1(4) = \binom41 D_3 = 4 \times 2 = 8$ ; $P_2(4) = \binom42 D_2 = 6$ ; $P_3(4) = \binom43 D_1 = 0$ (tres puntos fijos obligan a un cuarto); $P_4(4) = 1$ . Suma: $9 + 8 + 6 + 0 + 1 = 24 = 4!$ . Ningún acierto ( $9$ casos) gana a exactamente un acierto ( $8$ casos) — por poco.

4. Cuéntense los pares $(\sigma, i)$ con $\sigma(i) = i$ . Para $i$ fijo, las permutaciones que fijan $i$ son las permutaciones de los otros $n - 1$ puntos: hay $(n-1)!$ . Luego el número de pares es $n \cdot (n-1)! = n!$ , y ese número es también $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$ . Dividiendo por el número $n!$ de permutaciones: el número medio de puntos fijos es exactamente $1$ , para todo $n \geq 1$ .

5. Sea $\sigma$ un desarreglo de $\intint1{n+1}$ y $j = \sigma(n+1) \in \intint1n$ : $n$ valores posibles. Caso $\sigma(j) = n+1$ : los puntos $j$ y $n+1$ se intercambian, y $\sigma$ restringido a los $n - 1$ puntos restantes es un desarreglo arbitrario de ellos: $D_{n-1}$ posibilidades. Caso $\sigma(j) \neq n+1$ : sea $i_0 = \sigma^{-1}(n+1)$ ; aquí $i_0 \neq j$ e $i_0 \leq n$ . Defínase $\tau$ en $\intint1n$ por $\tau(i) = \sigma(i)$ para $i \neq i_0$ y $\tau(i_0) = j$ . Entonces $\tau$ es una permutación de $\intint1n$ (el valor $n+1$ se ha sustituido por el valor ausente $j$ ) y es un desarreglo: $\tau(i_0) = j \neq i_0$ , y $\tau(i) = \sigma(i) \neq i$ en los demás puntos. Recíprocamente, a partir de un desarreglo $\tau$ de $\intint1n$ y del valor $j$ se recupera $\sigma$ poniendo $\sigma(n+1) = j$ , $\sigma(\tau^{-1}(j)) = n+1$ y $\sigma = \tau$ en el resto: una biyección, que da $D_n$ posibilidades. Sumando sobre $j$ : $D_{n+1} = n(D_n + D_{n-1})$ . Numéricamente: $D_5 = 4(9 + 2) = 44$ , $D_6 = 5(44 + 9) = 265$ .

6. De la pregunta 5, $D_{n+1} = nD_n + nD_{n-1}$ , luego

u_{n+1} = D_{n+1} - (n+1)D_n = nD_n + nD_{n-1} - (n+1)D_n = -(D_n - nD_{n-1}) = -u_n .

Como $u_1 = D_1 - 1 \cdot D_0 = -1$ , la inducción da $u_n = (-1)^n$ , es decir, $D_n = nD_{n-1} + (-1)^n$ para $n \geq 1$ .

7. Inducción sobre $n$ . Base: $D_0 = 1 = 0!\,s_0$ . Paso: suponiendo $D_{n-1} = (n-1)!\,s_{n-1}$ ,

D_n = nD_{n-1} + (-1)^n = n!\,s_{n-1} + (-1)^n = n!\Bigl(s_{n-1} + \frac{(-1)^n}{n!}\Bigr) = n!\,s_n ,

que es la fórmula. No se ha usado la inclusión–exclusión: solo la recurrencia combinatoria de la pregunta 5.

8. Identidad trinomial, por factoriales:

\binom nk \binom kj = \frac{n!}{k!\,(n-k)!} \cdot \frac{k!}{j!\,(k-j)!} = \frac{n!}{j!\,(n-j)!} \cdot \frac{(n-j)!}{(k-j)!\,(n-k)!} = \binom nj \binom{n-j}{k-j} .

Sustitúyase ahora $a_k = \sum_j \binom kj b_j$ e intercámbiense las dos sumas finitas:

\sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k = \sum_{j=0}^{n} b_j \binom nj \sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j} = \sum_{j=0}^{n} b_j \binom nj \sum_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} .

La suma interior es el desarrollo de $(1 + (-1))^{n-j} = 0^{n-j}$ (teorema del binomio, Teorema 2.16): se anula para $j < n$ y vale $1$ para $j = n$ . Solo sobrevive $j = n$ , y el miembro derecho es $b_n$ , como se afirmaba.

9. Por la simetría $\binom nk = \binom n{n-k}$ , la identidad del Ejercicio 2.11 se reescribe como $n! = \sum_{k=0}^n \binom nk D_k$ . Aplíquese la pregunta 8 con $a_n = n!$ y $b_k = D_k$ :

D_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk k! = \sum_{k=0}^{n} (-1)^{n-k} \frac{n!}{(n-k)!} = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} ,

reindexando con $j = n - k$ : la fórmula por tercera vez.

10. $D_n = n!\,s_n$ (pregunta 7), luego

\Bigl| D_n - \frac{n!}{\eu} \Bigr| = n!\,\abs{s_n - \eu^{-1}} < \frac{n!}{(n+1)!} = \frac1{n+1} .

11. Para $n \geq 1$ se tiene $\frac1{n+1} \leq \frac12$ , y la desigualdad de la pregunta 10 es estricta: $D_n$ está de $n!/\eu$ a distancia $< \frac12$ , luego es el único entero más próximo. Para $n = 0$ la cota solo da distancia $< 1$ , y en efecto la afirmación falla ahí: el entero más próximo a $0!/\eu \approx 0.368$ es $0$ , mientras que $D_0 = 1$ .

12. $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ es una serie alternada de términos estrictamente decrecientes, de modo que su signo es el de su primer término $(-1)^{n+1}/(n+1)!$ . Por tanto $s_n - \eu^{-1}$ tiene el signo de $(-1)^n$ : para $n$ par, $s_n > \eu^{-1}$ y $D_n = n!\,s_n > n!/\eu$ ; para $n$ impar, $D_n < n!/\eu$ .

13. $D_7 = 6(265 + 44) = 6 \times 309 = 1854$ ; $D_8 = 7(1854 + 265) = 7 \times 2119 = 14\,833$ ; $D_9 = 8(14\,833 + 1854) = 8 \times 16\,687 = 133\,496$ ; $D_{10} = 9(133\,496 + 14\,833) = 9 \times 148\,329 = 1\,334\,961$ . Comprobación: $10!/\eu = 3\,628\,800 / 2.718281828 \approx 1\,334\,960.92$ , cuyo entero más próximo es $1\,334\,961$ — y $D_{10} > 10!/\eu$ , como predice la pregunta 12 para $n$ par.

14. $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} < \frac1{(n+1)!}$ . Para $n = 6$ : $p_6 = 265/720 = 0.36806$ (cinco decimales), frente a $\eu^{-1} = 0.36788$ ; la diferencia queda por debajo de $1/7! = 1/5040 < 2 \times 10^{-4}$ . La cota $1/(n+1)!$ se desploma tan deprisa que la probabilidad queda fijada con muchos decimales ya para una docena de cartas: la respuesta «alrededor del $36.8\,\%$ » es, a todos los efectos prácticos, independiente de $n$ — la famosa sorpresa del problema.

15. Por la pregunta 2 y $D_m = m!\,s_m$ :

\frac{P_k(n)}{n!} = \frac{\binom nk D_{n-k}}{n!} = \frac{D_{n-k}}{k!\,(n-k)!} = \frac{s_{n-k}}{k!} \;\longrightarrow\; \frac{\eu^{-1}}{k!}

cuando $n \to \infty$ con $k$ fijo, ya que $s_{n-k} \to \eu^{-1}$ . Los valores límite $\eu^{-1}/k!$ ( $k \in \N$ ) son los pesos de la distribución de Poisson de parámetro $1$ .

16. Cuéntense las ternas $(\sigma, i, j)$ con $i \neq j$ , $\sigma(i) = i$ , $\sigma(j) = j$ . Eligiendo primero el par ordenado: $n(n-1)$ maneras; las permutaciones que fijan $i$ y $j$ son las permutaciones de los $n - 2$ puntos restantes: hay $(n-2)!$ . En total: $n(n-1)(n-2)! = n!$ . Sumando en cambio primero sobre $\sigma$ se cuentan, para cada $\sigma$ , los pares ordenados de puntos fijos distintos: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$ . De ahí la identidad enunciada; dividiendo por $n!$ , el promedio de $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ es $1$ , luego el promedio de $\abs{\mathrm{Fix}}^2$ es $1 + 1 = 2$ y la varianza es $2 - 1^2 = 1$ .

17. Las proporciones $1 - p_n$ : para $n = 4$ , $1 - \frac 9{24} = \frac{15}{24} = 0.6250$ ; para $n = 5$ , $1 - \frac{44}{120} = \frac{76}{120} = 0.6333$ ; para $n = 6$ , $1 - \frac{265}{720} = \frac{455}{720} = 0.6319$ . Todas a menos de un uno por ciento de $1 - \eu^{-1} \approx 0.6321$ , oscilando a su alrededor.

18. Directamente:

s_{n+2} - s_n = \frac{(-1)^{n+1}}{(n+1)!} + \frac{(-1)^{n+2}}{(n+2)!} = (-1)^{n+1}\Bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\Bigr),

y el paréntesis es $> 0$ . Para $n$ par la diferencia es negativa: $s_{n+2} < s_n$ , luego $p_0 > p_2 > p_4 > \dots$ ; para $n$ impar es positiva: $p_1 < p_3 < p_5 < \dots$ Combinado con la pregunta 12 (los pares por encima de $\eu^{-1}$ , los impares por debajo) y con la pregunta 14 (la distancia a $\eu^{-1}$ tiende a $0$ ): las dos escaleras aprisionan a $\eu^{-1}$ entre ellas.

19. Un sorteo completo es una permutación aleatoria uniforme, válida cuando es un desarreglo: probabilidad $p_n \approx \eu^{-1}$ . Por el hecho citado, el número medio de sorteos hasta el éxito es $1/p_n$ , y la pregunta 14 da $1/p_n \approx \eu$ salvo un error ya despreciable para $n$ pequeño. Así pues, un amigo invisible con reinicios cuesta en promedio unos $\eu \approx 2.72$ sorteos completos — tanto si la oficina tiene $6$ personas como si tiene $600$ .

20. Fíjese $j \geq 2$ y hágase la clasificación de la pregunta 5 sobre el valor $\sigma(1) = j$ . Si $\sigma(j) = 1$ : los $n - 2$ puntos restantes llevan un desarreglo arbitrario, $D_{n-2}$ maneras. Si $\sigma(j) \neq 1$ : rediríjase hacia $j$ la imagen recíproca $i_0 = \sigma^{-1}(1)$ exactamente como en la pregunta 5; esto es una biyección con los desarreglos de los $n - 1$ puntos $\{2, \dots, n\}$ : $D_{n-1}$ maneras. En total $D_{n-1} + D_{n-2}$ , lo mismo para cada $j$ . Sumando sobre los $n - 1$ valores de $j$ : $D_n = (n-1)(D_{n-1} + D_{n-2})$ , que exhibe el factor $n - 1$ : $(n-1) \mid D_n$ .

21. Afirmación: $D_n$ es impar si y solo si $n$ es par. Inducción usando $D_n = nD_{n-1} + (-1)^n$ , es decir, $D_n \equiv nD_{n-1} + 1 \pmod 2$ . Base: $D_1 = 0$ es par y $n = 1$ es impar: la afirmación se cumple. Si $n$ es par, $nD_{n-1}$ es par y $D_n \equiv 1$ : impar, como se afirmaba. Si $n$ es impar, entonces $n - 1$ es par, luego $D_{n-1}$ es impar por hipótesis, y $D_n \equiv D_{n-1} + 1 \equiv 0$ : par. La inducción se cierra.

22. Reducir $D_n = nD_{n-1} + (-1)^n$ módulo $n$ mata el primer término: $D_n \equiv (-1)^n \pmod n$ . Para $n = 10$ : $(-1)^{10} = 1$ , y en efecto $D_{10} = 1\,334\,961$ acaba en la cifra $1$ .

23. Para $n \geq 3$ se tiene $D_{n-1} \geq 1$ , y dividir la recurrencia de la pregunta 6 por $D_{n-1}$ da $D_n/D_{n-1} = n + (-1)^n/D_{n-1}$ , con $\abs{(-1)^n/D_{n-1}} \leq 1$ y tendiendo rápidamente a $0$ . Coherencia: si $D_n \approx n!/\eu$ , entonces $D_n/D_{n-1} \approx n!/(n-1)! = n$ — el factor $\eu$ se cancela en el cociente, y la recurrencia lo confirma con precisión $1/D_{n-1}$ .

24. (i) Las reglas de la suma y del producto sostienen todos los recuentos: las preguntas 2 y 5 parten conjuntos de permutaciones en etapas independientes. (ii) El doble recuento dio la media (pregunta 4) y la varianza (pregunta 16) del número de puntos fijos sin ninguna fórmula para $D_n$ . (iii) El teorema del binomio evaluó la suma interior alternada $(1-1)^{n-j}$ que hace funcionar la inversión binomial (pregunta 8). (iv) La cota admitida de series alternadas convirtió la suma exacta pero opaca $n!\,s_n$ en el enunciado transparente «el entero más próximo a $n!/\eu$ » (preguntas 10–14).

25. La inclusión–exclusión (Ejemplo 2.26 y Ejercicio 2.11) es la demostración conceptual: explica la suma alternada como una corrección del recuento por exceso y se generaliza literalmente al recuento de los elementos que evitan cualquier familia de conjuntos «malos». La vía de la recurrencia (preguntas 5–7) es la que más rápido calcula —tiempo lineal, aritmética entera exacta, sin factoriales— y es la fuente de los hechos aritméticos de la parte V. La inversión binomial (preguntas 8–9) sitúa la fórmula dentro de una transformación general que reaparecerá siempre que se enfrenten dos sistemas triangulares de identidades. Y la aparición de $\eu$ la explica mejor la propia fórmula: la proporción de desarreglos es la suma parcial $s_n$ de la serie de $\eu^{-1}$ , de modo que los sobres de Montmort ya estaban calculando el número $\eu$ tres décadas antes de la notación de Euler.