---
title: "Combinatoria"
book: "Matemáticas universitarias — Grado 1"
subject: math
language: es
chapter: 2
exercises: 12
source: https://one-course.com/books/math/3/es/chapter/2-combinatoria
---

# Capítulo 2 — Combinatoria

Contar [conjuntos finitos](#def-b1-counting-card) suena elemental — y se vuelve sutil enseguida. Este capítulo define correctamente el [cardinal](#def-b1-counting-card) (mediante biyecciones, en el espíritu del [Capítulo 1](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#ch-b1-logic)), 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](#def-b1-counting-objects).

## 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $E$ es *finito* cuando $E = \emptyset$ o existe una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $\intint{1}{n}$ sobre $E$ para algún $n \in \N^*$; ese $n$ es único ([Teorema 2.2](#thm-b1-counting-welldef)) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $\intint{1}{m}$ sobre $\intint{1}{n}$. Con más precisión: si $m > n$, no existe ninguna [inyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $\intint{1}{m}$ en $\intint{1}{n}$.

**Demostración.** Demostramos por inducción sobre $n$ el [enunciado](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-statement): *para todo $m > n$ no hay ninguna [inyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) $\intint{1}{m} \to \intint{1}{n}$*. Para $n = 0$ el [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de llegada es vacío y $m \geq 1$: no existe [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) alguna. Supongamos el [enunciado](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-statement) para $n$ y sea $f \colon
\intint{1}{m} \to \intint{1}{n+1}$ una [inyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) con $m > n + 1$. Si el valor $n + 1$ no se alcanza, $f$ es una [inyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) $g$ cumple $g(m) = n + 1$. Entonces la restricción de $g$ a $\intint{1}{m-1}$ es una [inyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) $f \colon E \to F$ es [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj): 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj), $v \circ f \circ u$ sería una [inyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $\intint1m$ en $\intint1n$ (composición de inyecciones, [Proposición 1.26](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#prop-b1-logic-comp)), en contra del [Teorema 2.2](#thm-b1-counting-welldef). ∎

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

La demostración del [Teorema 2.2](#thm-b1-counting-welldef) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) en otro sitio. El remedio: componer $f$ con la transposición de los dos *valores* $f(a)$ y $f(m)$ — una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) del [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de llegada, con lo que la [inyectividad](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures) sobre el grupo simétrico.

**Proposición 2.5 (Inyecciones, sobreyecciones y cardinal).**

Sean $E, F$ [conjuntos finitos](#def-b1-counting-card) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj). Entonces $f$ es una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $E$ en $F \setminus \{y_0\}$, un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de [cardinal](#def-b1-counting-card) $\abs{F} - 1 < \abs{E}$ — imposible por el principio del palomar. Luego $f(E) = F$: $f$ es [sobreyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) y, por tanto, [biyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj).

Supongamos $f$ [sobreyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj). Elíjase para cada $y \in F$ una [imagen recíproca](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) $s(y) \in E$; entonces $f \circ s = \mathrm{id}_F$, luego $s$ es [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) ([Proposición 1.26](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#prop-b1-logic-comp)). Por el párrafo anterior aplicado a $s$ (los [cardinales](#def-b1-counting-card) son iguales), $s$ es [biyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj). De $f \circ s = \mathrm{id}_F$ se obtiene $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$, luego $f$ es [biyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj). Por último, una [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) [biyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) es por definición [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) y [sobreyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj), lo que cierra el ciclo de implicaciones. ∎

**Ejemplo 2.6 (La finitud es esencial).**

Sobre un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) *[finito](#def-b1-counting-card)*, la [Proposición 2.5](#prop-b1-counting-injsur) es un atajo poderoso: toda [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $E$ en sí mismo es automáticamente una [permutación](#def-b1-counting-objects) de $E$ — la mitad de la [biyectividad](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) sale gratis. Las dos implicaciones se derrumban en los [conjuntos](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) infinitos: $n \mapsto n + 1$ es [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de $\N$ en $\N$ pero no alcanza $0$, y la [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) $\N \to \N$ que envía $0 \mapsto 0$ y $n \mapsto n - 1$ para $n \geq 1$ es [sobreyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) pero no [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj). 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#ch-b1-logic) explora desde el otro lado, donde los [conjuntos](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) infinitos son precisamente los que admiten tales aplicaciones de un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) en sí mismo.

**Ejemplo 2.7 (La mitad del trabajo, gratis).**

Considérese la [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) $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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj)? Basta con la [inyectividad](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) ([Proposición 2.5](#prop-b1-counting-injsur)): 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](https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros#ch-b1-arith)); con $\abs{k - k'} \leq 6$ esto obliga a $k = k'$. La [sobreyectividad](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros#ch-b1-arith)), sostiene el emparejamiento del teorema de Wilson y vuelve en álgebra lineal como «un endomorfismo de un espacio de dimensión finita es [inyectivo](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) si y solo si es [sobreyectivo](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj)» ([Capítulo 19](https://one-course.com/books/math/3/es/chapter/19-dimension-finita#ch-b1-findim)).

## 2.2 Los principios de recuento

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

Sean $E, F$ [conjuntos finitos](#def-b1-counting-card).

1. Si $E \cap F = \emptyset$ , entonces $\abs{E \cup F} = \abs{E} +  \abs{F}$ ; más en general, para una [partición](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#thm-b1-logic-partition) de $E$ en trozos $E_1, \dots, E_k$ , $\abs{E} = \sum_i \abs{E_i}$ .
2. En general, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap  F}$ .
3. $\abs{E \times F} = \abs{E} \times \abs{F}$ .
4. El [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $F^E$ de todas las aplicaciones de $E$ en $F$ cumple $\abs{F^E} = \abs{F}^{\abs{E}}$ .
5. $\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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets)). 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $\{x\} \times F$, cada uno de [cardinal](#def-b1-counting-card) $\abs{F}$; aplíquese (1).

(4) Una [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj), 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) disfrazada ([Método 2.19](#met-b1-counting-which)).

![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.](https://one-course.com/images/onecourse/chapters/math-3/b1-counting/fig-6b232add30ef.svg)

*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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) con $\abs{E} = n$ y sea $0 \leq k \leq n$.

- Una *$k$-variación* de $E$ es una $k$ -tupla [inyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) de elementos de $E$ (una selección ordenada sin repetición);
- una *permutación* de $E$ es una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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$:

1. el número de $k$ -variaciones de $E$ es $n (n-1) \cdots  (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
2. el número de permutaciones de $E$ es $n!$ ;
3. $\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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](#prop-b1-counting-rules) (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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) no vacío, exactamente la mitad tienen [cardinal](#def-b1-counting-card) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $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](#exo-b1-counting-10)) |

Búsquese después una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) o una [partición](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#thm-b1-logic-partition) que reduzca el problema a estos recuentos modelo; un recuento correcto es una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) disfrazada.

**Observación 2.20 (Errores frecuentes al contar).**

1. *Sumar casos no disjuntos.* La regla de la suma exige una [partición](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#thm-b1-logic-partition) ; 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](#thm-b1-counting-inclexcl) ) o un reparto de casos más fino.
2. *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.
3. *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.
4. *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](#ex-b1-counting-complement) ).

**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](#def-b1-counting-card) que ambos miembros cuenten —típicamente un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de *pares*— y evalúese su [cardinal](#def-b1-counting-card) 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](#exo-b1-counting-12) y varias preguntas del problema del fin de semana.

**Ejemplo 2.23 (El subconjunto medio).**

¿Cuál es el [cardinal](#def-b1-counting-card) medio de un subconjunto de un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $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](#exo-b1-counting-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](#def-b1-counting-card) $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](#def-b1-counting-card) $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](#ex-b1-counting-binomial). 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](https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros#ch-b1-arith) y se desarrolla en el volumen del segundo año.

**Ejemplo 2.26 (Desarreglos).**

Un *desarreglo* es una [permutación](#def-b1-counting-objects) sin puntos fijos. Sea $A_i$ el [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) 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](https://one-course.com/books/math/3/es/chapter/17-series-numericas#ch-b1-series)), 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](#def-b1-counting-objects) son los objetos más reutilizados de este capítulo: mueven el teorema del binomio en el [Capítulo 8](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly) (desarrollo de $(X + a)^n$), la fórmula de Leibniz para la derivada $n$-ésima de un producto en el [Capítulo 14](https://one-course.com/books/math/3/es/chapter/14-derivacion#ch-b1-derivative) y los coeficientes de los desarrollos de Taylor en el [Capítulo 16](https://one-course.com/books/math/3/es/chapter/16-formulas-de-taylor-y-desarrollos-asintoticos#ch-b1-taylor). Las permutaciones vuelven como grupo — con la signatura construida a partir del recuento de inversiones — en el [Capítulo 7](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures), y la signatura define a su vez los determinantes en el [Capítulo 22](https://one-course.com/books/math/3/es/chapter/22-determinantes-y-sistemas-lineales#ch-b1-det). La inclusión–exclusión y los principios de recuento son el esqueleto [finito](#def-b1-counting-card) de la probabilidad discreta, desarrollada en el volumen del segundo año; los números de desarreglos del [Ejemplo 2.26](#ex-b1-counting-derangement) 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 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 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 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 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](#cor-b1-counting-pigeonhole)).

*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 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](#prop-b1-counting-identities). (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 de Ejercicio 2.6.**

Una [aplicación](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj), luego hay $\binom{n + k - 1}{k}$ aplicaciones crecientes.

**Ejercicio 2.7 ★★.**

(Vandermonde) Demuéstrese, contando los $k$-subconjuntos de un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) 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 de Ejercicio 2.7.**

Repártase un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) $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 de Ejercicio 2.8.**

Sea $A_d$ el [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) 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](#thm-b1-counting-inclexcl)) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de $4$ elementos sobre un [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de $2$ elementos; después, sobre uno de $3$ elementos. *Indicación: cuéntense las aplicaciones no [sobreyectivas](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) con inclusión–exclusión sobre los valores no alcanzados.*

**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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](#ex-b1-counting-derangement) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de puntos fijos).

**Solución de Ejercicio 2.11.**

Con $A_i = \{\sigma : \sigma(i) = i\}$, una [permutación](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) 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 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](#ex-b1-counting-derangement). 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](#def-b1-counting-objects) 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](#def-b1-counting-objects) vacía no tiene puntos fijos).

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

1. 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$ .)
2. 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}$ .
3. 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?
4. Mediante un doble recuento ([Método 2.22](#met-b1-counting-doublecount)) de los pares $(\sigma, i)$ con $\sigma(i) = i$, pruébese que $$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$$ en promedio, una [permutación](#def-b1-counting-objects) aleatoria tiene *exactamente un* punto fijo, sea cual sea $n \geq 1$.

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

5. 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) con los desarreglos de $\intint1n$ redirigiendo hacia $j$ la [imagen recíproca](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) de $n + 1$.) Compruébese la recurrencia numéricamente hasta $D_6$.
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).$$
7. A partir de la pregunta 6, demuéstrese por inducción la fórmula del [Ejemplo 2.26](#ex-b1-counting-derangement), $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$$ — una demostración totalmente independiente de la inclusión–exclusión.
8. (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](#ex-b1-counting-binomial).)
9. Aplíquese la pregunta 8 a la identidad $n! = \sum_k \binom nk D_{n-k}$ del [Ejercicio 2.11](#exo-b1-counting-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](https://one-course.com/books/math/3/es/chapter/17-series-numericas#ch-b1-series) — 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$.

10. Pruébese que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ para todo $n \in \N$ .
11. 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$ ?
12. 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.)
13. 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$ ).
14. (La probabilidad del guardarropa) Sea $p_n = D_n/n!$ la probabilidad de que una [permutación](#def-b1-counting-objects) 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.**

15. 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.)
16. 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.
17. 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$ .
18. 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}$ .
19. (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.**

20. 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$ .
21. 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.)
22. 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}$ .
23. 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$ .
24. ¿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.
25. 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 de Problema 2.1.**

**1.** $D_1 = 0$ (la única [permutación](#def-b1-counting-objects) 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](#def-b1-counting-objects) con exactamente $k$ puntos fijos queda determinada por la elección de su [conjunto](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) de puntos fijos $F$ ($\binom nk$ maneras) junto con su restricción al complementario, que debe ser una [permutación](#def-b1-counting-objects) de $n - k$ puntos *sin* ningún punto fijo ($D_{n-k}$ maneras). Las dos elecciones son independientes y la correspondencia es [biyectiva](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj): $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](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj), 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](#thm-b1-counting-binomial)): 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](#exo-b1-counting-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](#def-b1-counting-objects) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-map) $i_0 = \sigma^{-1}(1)$ exactamente como en la pregunta 5; esto es una [biyección](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) 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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-statement) transparente «el entero más próximo a $n!/\eu$» (preguntas 10–14).

**25.** La inclusión–exclusión ([Ejemplo 2.26](#ex-b1-counting-derangement) y [Ejercicio 2.11](#exo-b1-counting-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](https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones#def-b1-logic-sets) «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.