Matemáticas universitarias — Grado 1 · Bachelor Year 1

2Cálculo

Contar conjuntos finitos suena elemental y rápidamente se vuelve sutil. Este capítulo define cardinalidad correctamente (a través de biyecciones, en el espíritu de Capítulo 1), establece el puñado de conteos principios de los cuales todo se sigue, y deriva el clásico recuentos: listas, permutaciones, subconjuntos, coeficientes binomiales.

2.1 Cardinalidad de conjuntos finitos

Definición 2.1 (Conjunto finito, cardinalidad)

Para $n \in \N^*$ , escriba $\intint{1}{n} = \{1, 2, \dots, n\}$ . A conjunto $E$ es finito cuando $E = \emptyset$ o hay una biyección de $\intint{1}{n}$ a $E$ para algunos $n \in \N^*$ ; este $n$ es único (Teorema 2.2) y es el cardinalidad de $E$ , escrito $\abs{E}$ (con $\abs{\emptyset} = 0$ ).

Teorema 2.2 (La cardinalidad está bien definida)

Si $m \neq n$ , no hay biyección de $\intint{1}{m}$ hacia $\intint{1}{n}$ . Más precisamente, si $m > n$ hay sin inyección de $\intint{1}{m}$ en $\intint{1}{n}$ .

Demostración. Probamos por inducción en $n$ el enunciado: for all $m > n$ , there is no injection $\intint{1}{m} \to \intint{1}{n}$ . Para $n = 0$ el objetivo está vacío y $m \geq 1$ : no aplicación existe en absoluto. Supongamos que enunciado es $n$ y supongamos que $f \colon \intint{1}{m} \to \intint{1}{n+1}$ es un inyección con $m > n + 1$ . Si no se alcanza el valor $n + 1$ , $f$ es una inyección en $\intint{1}{n}$ , contradiciendo la hipótesis de inducción. De lo contrario $f(a) = n + 1$ para exactamente un $a$ ; intercambiar $f(a)$ y $f(m)$ (formalmente: componer con la transposición de los dos valores), de modo que la nueva inyección $g$ tenga $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$ — contradicción nuevamente. ∎

Corolario 2.3 (Principio de encasillamiento)

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

Demostración. Escribe $\abs E = m$ , $\abs F = n$ con $m > n$ y elige biyecciones. $u \colon \intint1m \to E$ y $v \colon F \to \intint1n$ . Si $f$ Si fuera inyectivo, $v \circ f \circ u$ sería una inyección de $\intint1m$ en $\intint1n$ (una composición de inyecciones, Proposición 1.26), contradiciendo Teorema 2.2. ∎

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

La prueba de Teorema 2.2 contiene la El primer movimiento realmente inteligente del capítulo, que vale la pena repetir lentamente. El obstáculo: para aplicar la hipótesis de la inducción uno quiere eliminar el último punto $m$ de la fuente y el último punto $n+1$ del objetivo, pero $f$ puede enviar algún otro punto $a$ a $n + 1$ , y luego eliminar el punto objetivo daña la aplicación. en otro lugar. La cura: componer $f$ con la transposición del dos valores $f(a)$ y $f(m)$ — una biyección de la objetivo, por lo que se preserva la inyectividad — después de lo cual el El valor problemático $n + 1$ se encuentra en la posición inofensiva $m$ , y Ambas eliminaciones están limpias. Esto "normaliza primero, luego corta" El patrón se repite: así es como la recurrencia del trastorno redirige $\sigma^{-1}(n+1)$ en el problema de fin de semana de este capítulo, y cómo se parchean permutaciones en todas partes El problema de Capítulo 7 en el grupo simétrico.

Proposición 2.5 (Inyecciones, sobreyecciones y cardinalidad)

Sea $E, F$ conjuntos finitos con $\abs{E} = \abs{F}$ y $f \colon E \to F$ . entonces

f \text{ injective} \iff f \text{ surjective} \iff f \text{ bijective}.

Demostración. Supongamos $f$ inyectivo. Entonces $f$ es una biyección de $E$ a $f(E)$ , Entonces $\abs{f(E)} = \abs{E} = \abs{F}$ . Si $f(E)$ perdió un punto $y_0$ de $F$ , entonces $f$ sería una inyección de $E$ en $F \setminus \{y_0\}$ , un conjunto de cardinalidad $\abs{F} - 1 < \abs{E}$ — imposible por el principio de casillero. Entonces $f(E) = F$ : $f$ es sobreyectivo, por lo tanto biyectivo.

Supongamos $f$ sobreyectivo. Elija para cada $y \in F$ un imagen inversa $s(y) \in E$ ; entonces $f \circ s = \mathrm{id}_F$ , entonces $s$ es inyectivo (Proposición 1.26). Por el párrafo anterior aplicado a $s$ (las cardinalidades son iguales), $s$ es biyectivo. De $f \circ s = \mathrm{id}_F$ obtenemos $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , entonces $f$ es biyectivo. Finalmente, un biyectivo aplicación es por definición ambos inyectivo y sobreyectivo, con lo que se cierra el ciclo de implicaciones. ∎

Ejemplo 2.6 (La finitud es esencial)

En un finito conjunto, Proposición 2.5 es un poderoso acceso directo: cualquier inyectivo aplicación de $E$ a sí mismo es automáticamente un permutación de $E$ — la mitad de la biyectividad viene libre. ambos implicaciones colapsan en infinito conjuntos: $n \mapsto n + 1$ es inyectivo de $\N$ a $\N$ pero falta $0$ y aplicación $\N \to \N$ enviar $0 \mapsto 0$ y $n \mapsto n - 1$ para $n \geq 1$ es sobreyectivo pero no inyectivo. Siempre que se invoca esta proposición, la hipótesis de la finitud está haciendo un trabajo real, un tema que el El problema del fin de semana de Capítulo 1 explora desde el otro lado, donde infinitos conjuntos son precisamente los que admiten tal automorfismos.

Ejemplo 2.7 (La mitad del trabajo, libre)

Considere la aplicación $f$ en $\{0, 1, \dots, 6\}$ enviando $k$ al resto de $3k$ tras la división por $7$ ; su tabla de valores es

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

¿ $f$ es una biyección? La inyectividad por sí sola es suficiente (Proposición 2.5): si $3k$ y $3k'$ tienen el mismo resto, $7$ divide $3(k - k')$ , y como $7$ es primo y no divide a $3$ , divide a $k - k'$ (lema de Euclides, utilizado en Nivel de Bachillerato aquí y acreditado en Capítulo 6); con $\abs{k - k'} \leq 6$ esto obliga a $k = k'$ . Llega la sobrejetividad libre — no es necesario resolver $3k \equiv c$ para cada $c$ , aunque el La tabla confirma que cada valor aparece exactamente una vez. El atajo es un caballo de batalla: demuestra la invertibilidad de lo modular multiplicación (Capítulo 6), potencia el emparejamiento en teorema de Wilson, y regresa en álgebra lineal como "un el endomorfismo de un espacio de dimensión finita es inyectivo si y solo sobreyectivo” (Capítulo 19).

2.2 Los principios de conteo

Proposición 2.8 (Reglas de suma y producto)

Sea $E, F$ conjuntos finitos.

Si $E \cap F = \emptyset$ , entonces $\abs{E \cup F} = \abs{E} + \abs{F}$ ; de manera más general, para un dividir de $E$ en pedazos $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 todos los aplicaciones desde $E$ hasta $F$ satisface $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

Demostración. (1) Concatenar enumeraciones: si $E = \{x_1, \dots, x_m\}$ y $F = \{y_1, \dots, y_n\}$ sin repetición, entonces $x_1, \dots, x_m, y_1, \dots, y_n$ enumera $E \cup F$ sin repetición (desarticulación). La inducción extiende esto a piezas $k$ .

(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$ ; entonces $\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, sobre $x \in E$ , de los conjuntos $\{x\} \times F$ , cada uno de cardinalidad $\abs{F}$ ; aplicar (1).

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

(5) Los subconjuntos de $E$ se corresponden de modo biyectivo con las aplicaciones $E \to \{0, 1\}$ (enviar $A$ a su función indicadora); aplicar (4). ∎

Ejemplo 2.9 (Conteo del complemento)

¿Cuántos códigos PIN de $4$ dígitos (dígitos $0$ – $9$ , el orden importa, repetición permitida) contienen al menos un dígito repetido? Contarlos directamente obliga a manejar los casos “exactamente un par, dos pares, un triple, un cuádruple” — cinco configuraciones que se solapan. Cuéntese en su lugar el complemento: todos los códigos $10^4 = 10\,000$ (regla de producto), los códigos con cuatro distintos número de dígitos $10 \times 9 \times 8 \times 7 = 5\,040$ ( $4$ -arreglos), entonces la respuesta es

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

Casi la mitad de todos los PIN repiten un dígito. La idea: siempre que un cuenta está redactado con "al menos" o "no todos", pruebe el complemento primero — la regla de la suma garantiza que $\abs{A} = \abs{E} - \abs{\overline A}$ , y el complemento es a menudo una única configuración limpia.

Ejemplo 2.10 (Caminos de celosía)

Cuente los caminos más cortos desde la esquina $(0,0)$ hasta la esquina $(4, 3)$ de una cuadrícula, moviéndose solo un paso hacia la derecha (R) o un paso hacia arriba (U) a la vez. Cada uno de estos caminos toma exactamente $7$ pasos, de los cuales $4$ son R y $3$ son U; por el contrario, cualquier palabra de longitud $7$ en el Las letras R, U con cuatro R describen exactamente un camino. los caminos por lo tanto corresponden biyectivamente a las elecciones de las posiciones de las R:

\binom{7}{4} = 35 .

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

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

2.3 Listas, permutaciones, subconjuntos

Definición 2.11 (Arreglos, permutaciones, combinaciones)

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

Un $k$ -acuerdo de $E$ es una tupla inyectivo $k$ de elementos de $E$ (una selección ordenada sin repetición);
a permutación de $E$ es una biyección de $E$ a sí mismo — equivalentemente, un arreglo $n$ ;
a $k$ -combinación es un subconjunto de $E$ con elementos $k$ (una selección desordenada sin repetición). Su número es escrito $\binom{n}{k}$ , lea “ $n$ elija $k$ ” .

Teorema 2.12 (Los tres cargos)

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

el número de arreglos $k$ 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) Elija la primera coordenada ( $n$ caminos), luego la segunda ( $n - 1$ opciones restantes), …, luego $k$ -ésima (opciones $n - k + 1$ ). Formalmente, incorporación al $k$ . Para $k = 1$ hay $n$ de un término inyectivo tuplas. Suponga el recuento de $k - 1$ . cada uno $k$ -el arreglo $(x_1, \dots, x_k)$ se obtiene exactamente de uno $(k-1)$ -disposición — su truncamiento $(x_1, \dots, x_{k-1})$ — agregando una última coordenada fuera de $\{x_1, \dots, x_{k-1}\}$ , para la cual están disponibles exactamente los valores $n - (k - 1)$ . Los arreglos $k$ se dividen así, por truncamiento, en clases de tamaño común $n - k + 1$ indexadas por el arreglos $(k-1)$ , 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 subconjunto $k$ ordena en $k!$ arreglos $k$ distintos, y cada arreglo $k$ surge exactamente de un subconjunto: entonces $\frac{n!}{(n-k)!} = \binom nk \cdot k!$ . ∎

Ejemplo 2.13 (Mesas redondas: cocientes por simetría)

¿De cuántas maneras pueden sentarse los invitados $n$ alrededor de una mesa redonda, dos? Los asientos son idénticos cuando cada invitado tiene el mismo lado izquierdo y derecho. vecinos correctos — es decir, ¿hasta la rotación? Cada asiento circular corresponde exactamente a los asientos lineales $n$ (cortar el círculo en cualquier de los lugares $n$ ), por lo que las órdenes lineales $n!$ colapsan en grupos de $n$ :

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

Equivalentemente: sentar a un invitado distinguido en cualquier lugar (matando al libertad de rotación), luego ordene los invitados $n - 1$ restantes en el sentido de las agujas del reloj. Para tablas $n = 6$ : $120$ . Las dos soluciones ilustran Las dos curas estándar para el conteo excesivo: dividir por el número exacto. número de repeticiones, o romper la simetria fijando una objeto hacia abajo. Ambos requieren que el tamaño del grupo de repeticiones sea el lo mismo para cada configuración — que la prueba de la fórmula $\binom nk = \frac{n!}{k!\,(n-k)!}$ arriba usado también, con $k!$ en lugar de $n$ .

Ejemplo 2.14 (Agregar una restricción)

Continuando con la mesa redonda: entre las mesas $(n-1)!$ de invitados $n \geq 3$ , ¿cuántos asientos tienen dos invitados dados $A$ y $B$ aparte? (no adyacente)? Cuente el complemento. Tablas donde $A$ y $B$ sentarse juntos: pegarlos en un solo bloque — $n - 1$ objetos alrededor de la mesa, es decir, $(n-2)!$ arreglos circulares — entonces ordenar el par dentro de su bloque ( $2$ formas): $2\,(n-2)!$ adyacente mesas. Por lo tanto

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

las mesas los mantienen separados. Comprobaciones de cordura: $n = 3$ da $0$ (alrededor un triangulo, todos tocan a todos) y $n = 4$ le da $2$ , listado fácilmente a mano. El truco del pegado: tratar un bloque forzado como un objeto, luego cuente sus arreglos internos — es el Cura estándar para restricciones de adyacencia, 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 Subconjuntos $k$ y subconjuntos $(n-k)$ . Regla de Pascal: arreglar un elemento $a \in E$ ; los subconjuntos $k$ se dividen en aquellos que contienen $a$ (elija los otros $k - 1$ : $\binom{n-1}{k-1}$ ) y aquellos que evitan $a$ ( $\binom{n-1}{k}$ ). Tercera identidad: ambos lados cuentan todos los subconjuntos de $E$ , dividido por tamaño a la izquierda (Proposición 2.8 (1) y (5)). ∎

Teorema 2.16 (Teorema del binomio)

Para todos los $a, b$ en un anillo conmutativo (digamos $\R$ o $\C$ ) y $n \in \N$ :

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

Demostración. Expandir $(a+b)(a+b)\cdots(a+b)$ distributivamente produce un término por elección, en cada factor, de $a$ o $b$ : el término $a^k b^{n-k}$ aparece una vez para cada forma de elegir cuál factor $k$ de los $n$ contribuye $a$ — es decir, $\binom nk$ veces. (Alternativamente: inducir en $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 tiene incluso cardinalidad.

Ejemplo 2.18 (Una identidad, dos pruebas.)

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

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

Aquí está la misma identidad sin ningún álgebra. el lado derecho cuenta las palabras de longitud $n$ sobre el alfabeto $\{0, 1, 2\}$ (regla del producto). Clasifica cada palabra por el conjunto $K$ de posiciones llevar una letra distinta de cero: elegir $K$ con costos $\abs K = k$ $\binom nk$ , entonces cada posición de $K$ lleva de forma independiente $1$ o $2$ : $2^k$ formas. La regla de la suma sobre $k$ da el lado izquierdo. Más allá del placer del acuerdo, las dos pruebas tienen diferentes virtudes: el algebraico generaliza a cualquier valor de $a$ , el combinatoria explica la fórmula y se adapta a restricciones (prohibir la letra $2$ en la última posición, digamos) que sin capturas de sustitución. Mantener ambas técnicas activas es la habilidad práctica que este capítulo entrena.

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

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

	order matters	order does not matter
no repetition	$\dfrac{n!}{(n-k)!}$	$\dbinom{n}{k}$
[6pt] repetition allowed	$n^k$	(Ejercicio 2.10)

Luego busque una biyección o un dividir que reduzca el problema a estos el modelo cuenta; un recuento correcto es una biyección disfrazada.

Observación 2.20 (Errores comunes al contar)

Suma de casos no disjuntos. La regla de la suma requiere una dividir; si las configuraciones pueden satisfacer dos casos en una vez, se cuentan dos veces — la cura es inclusión–exclusión (Teorema 2.24) o una división de casos más fina.
Ordenado versus desordenado. Elegir “un comité de dos” es $\binom n2$ , no $n(n-1)$ : decida antes informática si la selección lleva un orden, y si un conteo ordenado es más fácil, divídalo por el número de pedidos al final — pero sólo cuando todos los desordenados El objeto surge del número mismo de ordenados.
Elecciones de varias etapas que no son independientes. La regla del producto necesita la cantidad de opciones en cada etapa. ser independiente de las elecciones anteriores. “Elige un capitán, entonces otro vicecapitán” está bien ( $n(n-1)$ ); "Elegir dos jugadores que se lleven bien" no es un proceso de dos etapas. producto en absoluto.
Doble conteo por construcción. Construyendo cada uno objeto dos veces — por ejemplo contando manos con al menos un as como (elige un as) $\times$ (elige $4$ más cards) — cuenta en exceso las manos con dos ases. “Al menos” casi siempre pide el complemento (Ejemplo 2.9).

Ejemplo 2.21 (Recuento estilo poker)

De una baraja de cartas $52$ , el número de manos de cartas $5$ es $\binom{52}{5} = 2\,598\,960$ . Manos que contienen exactamente un as: elija el as ( $4$ formas) y luego las cartas $4$ entre las $48$ que no son ases: $4 \binom{48}{4} = 778\,320$ . La regla del producto se aplica porque el La elección se divide en etapas independientes.

Método 2.22 (doble conteo)

Para probar una identidad entre dos expresiones de conteo, encuentre una sola conjunto finito que ambos lados cuentan — típicamente un conjunto de pares — y evaluar su cardinalidad en dos órdenes diferentes. el El prototipo es el lema del apretón de manos: en una fiesta, cuenta los pares. (persona, mano estrechada). La suma de las personas da $\sum_p d_p$ (cada número de apretones de manos de la persona $p$ ); la suma de los apretones de manos da el doble de apretones de manos (cada uno involucra a dos personas). Por lo tanto $\sum_p d_p$ es par — entonces el número de personas que agitaron un número impar número de manos es siempre par, se obtiene una conclusión no trivial sin fórmula alguna. El mismo motor funciona. Ejercicio 2.12 y varias preguntas del fin de semana problema a continuación.

Ejemplo 2.23 (El subconjunto promedio)

¿Cuál es el promedio cardinalidad de un subconjunto de un elemento $n$ conjunto? $E$ , ¿todos los subconjuntos $2^n$ son igualmente probables? Cuente dos veces el pares $(A, a)$ con $a \in A$ : la suma de subconjuntos da $\sum_A \abs A$ , el total que queremos; la suma de elementos da $n \cdot 2^{n-1}$ (cada uno de los elementos $n$ se encuentra exactamente en la mitad de los subconjuntos — empareje cada $A$ que contenga $a$ con $A \setminus \{a\}$ ). Por lo 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 la simetría $A \leftrightarrow \overline A$ (que empareja los tamaños $k$ y $n - k$ ) también predice. Dos pruebas, una respuesta y ambas evitan la conexión directa. cálculo $\sum_k k\binom nk$ de Ejercicio 2.5: a una pareja bien elegida a menudo reemplaza 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. Fijar un elemento $x$ de la unión y contar su contribución al lado derecho. Sea $J = \{i : x \in A_i\}$ , de cardinalidad $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 Ejemplo 2.17. Entonces cada elemento de la unión es contado exactamente una vez. ∎

Ejemplo 2.25 (Contando numeros enteros coprimos)

¿Cuántos números enteros de $\intint1{120}$ son coprimos con $120 = 2^3 \times 3 \times 5$ ? Un número entero comparte un factor con $120$ exactamente cuando es divisible por $2$ , $3$ o $5$ , entonces cuenta el complemento de $A_2 \cup A_3 \cup A_5$ , donde $A_d$ recoge los múltiplos de $d$ . Dentro de $\intint1{120}$ , los múltiplos de $d$ número $120/d$ siempre que $d$ divida $120$ — no se necesitan funciones de piso — 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 ,

por lo que los números enteros $120 - 88 = 32$ son coprimos con respecto a $120$ . es instructivo para 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 :

expandir los tres paréntesis reproduce exactamente los ocho términos de inclusión-exclusión firmados, uno por subconjunto de $\{2, 3, 5\}$ . Esta forma de producto define la función totiente de Euler, cuya El papel aritmético aparece con las congruencias de Capítulo 6 y se desarrolla en el volumen del Año 2.

Ejemplo 2.26 (Trastornos)

Un trastorno mental es un permutación sin punto fijo. Deja $A_i$ ser el conjunto de permutaciones de $\intint{1}{n}$ fijando $i$ ; luego $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ , y inclusión–exclusión cuenta el permutaciones con al menos un fijo punto; el número de trastornos

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

Desde $\sum (-1)^k / k! \to \eu^{-1}$ (ver Capítulo 17), aproximadamente $37\%$ de todos los permutaciones son trastornos, sea lo que sea $n$ .

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

Coeficientes binomiales son los objetos más reutilizados de este capítulo: impulsan el teorema del binomio en Capítulo 8 (expansión de $(X + a)^n$ ), la fórmula de Leibniz para el $n$ -ésimo derivado de un producto en Capítulo 14, y el coeficientes de expansiones de Taylor en Capítulo 16. Permutaciones regresa como grupo — con la firma construida a partir de contando inversiones — en Capítulo 7, y el la firma a su vez define los determinantes en Capítulo 22. Inclusión-exclusión y los principios de conteo son los finito columna vertebral de probabilidad discreta, desarrollada en el volumen del Año 2; los números de trastorno de Ejemplo 2.26 son estudiado en profundidad en el problema del fin de semana a continuación.

2.5 Ceremonias

Ejercicio 2.1 ★

Una matrícula consta de dos letras (A–Z), luego tres dígitos y luego dos letras. ¿Cuántas placas son posibles? cuantos sin repetidos ¿Carta entre las cuatro?

Solución

Solución de Ejercicio 2.1.

Etapas independientes y regla de producto: placas $26^2 \times 10^3 \times 26^2 = 26^4 \times 1000 = 456\,976\,000$ . Con las cuatro letras distintas por pares, las etapas de letras forman una disposición $4$ de las alfabeto: $26 \times 25 \times 24 \times 23 = 358\,800$ formas, entonces Placas $358\,800 \times 1000 = 358\,800\,000$ .

Ejercicio 2.2 ★

¿Cuántos anagramas (reordenamientos de las letras, significativos o no)? tiene la palabra orange? ¿Y banana?

Solución

Solución de Ejercicio 2.2.

orange tiene letras distintas $6$ : anagramas $6! = 720$ . banana tiene letras $6$ con repeticiones ( $3$ a, $2$ n, $1$ b): cada anagrama está determinado por las posiciones de las a (opciones $\binom 63$ ), luego de las n entre los lugares $3$ restantes ( $\binom 32$ ), la b ocupa el último lugar: $\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. como muchos comités: ¿en total? ¿Con exactamente $2$ mujeres? con al menos uno hombre?

Solución

Solución de Ejercicio 2.3.

Total: $\binom{12}{4} = 495$ . Exactamente $2$ mujeres: elígelas ( $\binom 72 = 21$ ) y $2$ hombres ( $\binom 52 = 10$ ): comités $210$ . Al menos un hombre: complemento de “ningún hombre”, $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$ .

Ejercicio 2.4 ★

Demuestre que en cualquier grupo de personas $13$ , dos comparten su mes de nacimiento; y que entre cualquier número entero $n + 1$ elegido de $\intint{1}{2n}$ , dos son consecutivos. (Encasillado en ambas ocasiones: nombre las cajas.)

Solución

Solución de Ejercicio 2.4.

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

Enteros consecutivos: las casillas son los pares $n$ $\{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\}$ , que dividir $\intint{1}{2n}$ . Al elegir números enteros $n + 1$ se colocan dos en el mismo par y los dos Los elementos de un par son consecutivos.

Ejercicio 2.5 ★

Calcule $\sum_{k=0}^{n} k \binom{n}{k}$ . Hint: differentiate $(1 + x)^n$ , or use $k \binom nk = n \binom{n-1}{k-1}$ (prove it).

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}.

Suma y reindexación 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 Proposición 2.15. (Alternativa: diferenciar $(1+x)^n = \sum_k \binom nk x^k$ y establezca $x = 1$ ).

Ejercicio 2.6 ★★

¿Cuántos aplicaciones estrictamente crecientes hay desde $\intint{1}{k}$ hasta $\intint{1}{n}$ ? Deducir el número de aumentando (no necesariamente estrictamente) aplicaciones. Hint for the second count: $f$ increasing $\mapsto$ $g(i) = f(i) + i - 1$ .

Solución

Solución de Ejercicio 2.6.

Una aplicación $f \colon \intint{1}{k} \to \intint{1}{n}$ estrictamente creciente está determinado por su imagen, un subconjunto $k$ de $\intint{1}{n}$ (enumere el subconjunto en orden creciente); por el contrario, cada subconjunto $k$ da exactamente uno de esos aplicación. Por lo tanto, $\binom nk$ aumenta estrictamente aplicaciones.

Si $f$ simplemente aumenta, configure $g(i) = f(i) + i - 1$ . Entonces $g$ es estrictamente creciente (entre argumentos consecutivos, $f$ gana $\geq 0$ y $i - 1$ gana $1$ ) con valores en $\intint{1}{n + k - 1}$ ; y $f(i) = g(i) - i + 1$ recupera $f$ de cualquier $g$ estrictamente creciente en $\intint{1}{n+k-1}$ . Esta es una biyección, por lo que hay $\binom{n + k - 1}{k}$ aumentando aplicaciones.

Ejercicio 2.7 ★★

(Vandermonde) Demuestre, contando subconjuntos $k$ de un conjunto dividido en dos bloques de tamaños $m$ y $n$ :

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

Deducir $\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$ .

Solución

Solución de Ejercicio 2.7.

Dividir un conjunto $E$ con elementos $m + n$ en bloques $M$ (elementos $m$ ) y $N$ (elementos $n$ ). Un subconjunto $k$ de $E$ contiene algunos elementos $j$ de $M$ ( $0 \leq j \leq k$ ) y $k - j$ de $N$ ; para $j$ fijo hay $\binom mj \binom{n}{k-j}$ dichos subconjuntos, y en los casos $j = 0, \dots, k$ dividir los subconjuntos $k$ . La regla de la suma le da a Vandermonde identidad.

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 números enteros en $\intint{1}{1000}$ son divisibles por? ¿ $2$ o $3$ o $5$ ? (Inclusión–exclusión; $\lfloor 1000/6 \rfloor$ cuenta los múltiplos de $6$ , etc.)

Solución

Solución de Ejercicio 2.8.

Sean $A_d$ los múltiplos de $d$ en $\intint{1}{1000}$ , entonces $\abs{A_d} = \lfloor 1000/d \rfloor$ . Inclusión-exclusión (Teorema 2.24) con $A_2, A_3, A_5$ , observando $A_2 \cap A_3 = A_6$ etc.:

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

Entonces los números enteros $734$ son divisibles por $2$ , $3$ o $5$ .

Ejercicio 2.9 ★★

Cuente las sobreyecciones de un conjunto de elementos $4$ en un conjunto de $2$ elementos; luego a un conjunto de elementos $3$ . Hint: count the no sobreyectivo aplicaciones with inclusion–exclusion on the missed values.

Solución

Solución de Ejercicio 2.9.

Sobre los elementos $2$ : todos los $2^4 = 16$ aplicaciones excepto la constante $2$ aplicaciones: $14$ sobrejecciones.

En elementos $3$ : mediante inclusión-exclusión de los valores perdidos, el Al número de aplicaciones de un conjunto $4$ a un conjunto $3$ le falta al menos un valor es $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ ; total aplicaciones $3^4 = 81$ ; sobreyecciones: $81 - 45 = 36$ . (Compruebe: una sobreyección de $4$ en $3$ elementos duplican exactamente un valor: elija el valor duplicado ( $3$ ), el par que se le asigna ( $\binom 42 = 6$ ) y una biyección para el resto ( $2$ ): $3 \times 6 \times 2 = 36$ .)

Ejercicio 2.10 ★★

(Estrellas y barras) Demuestre que el número de selecciones $k$ de $n$ objetos con repetición, orden ignorada — 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}$ . Sugerencia: codifica 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: escribe $x_1$ estrellas, una barra, $x_2$ estrellas, a barra, …, que termina con estrellas $x_n$ . Esta es una biyección sobre el palabras de longitud $k + n - 1$ usando estrellas $k$ y barras $n - 1$ , y esas palabras están determinadas por las posiciones de las estrellas: $\binom{n + k - 1}{k}$ . Las selecciones con repetición corresponden a soluciones de la ecuación ( $x_i$ = número de copias del objeto $i$ ), entonces el conteo es el mismo.

Ejercicio 2.11 ★★★

Demuestre la fórmula de Ejemplo 2.26 para $D_n$ en detalle, y deducir $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (también probar esta identidad directamente clasificando permutaciones por su punto fijo conjunto).

Solución

Solución de Ejercicio 2.11.

Con $A_i = \{\sigma : \sigma(i) = i\}$ , un permutación en $\bigcap_{i \in I} A_i$ arregla cada $i \in I$ y permuta el otro $n - \abs I$ puntos libremente: $\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!} ,

ya que hay $\binom nk$ subconjuntos $I$ de tamaño $k$ . Por lo 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: clasificar el permutaciones $\sigma$ de $\intint{1}{n}$ por su punto fijo conjunto $F(\sigma)$ . por un fijo $k$ -subconjunto $F$ , el permutaciones con $F(\sigma) = F$ son exactamente los Trastornos del complemento: $D_{n-k}$ de ellos. resumiendo el $\binom nk$ opciones de $F$ para cada $k$ : $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$ .

Ejercicio 2.12 ★★★

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

\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1}, \qquad\text{then}\qquad \sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .

Para el segundo: cuenta pares de elementos marcados, iguales o no.

Solución

Solución de Ejercicio 2.12.

Primera identidad. Cuente los pares $(A, a)$ donde $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$ opciones para $a$ , luego cualquier subconjunto de los elementos $n - 1$ restantes para completar $A$ : $n\,2^{n-1}$ pares.

Segunda identidad. Cuéntense los triples $(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}$ triples, recuento anterior), o $a \neq b$ ( $n(n-1)$ opciones ordenadas, luego 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: Trastornos o cartas sin dirección

Problema 2.1

Una secretaria coloca cartas $n$ en sobres con la dirección $n$ al azar: ¿Cuál es la probabilidad de que nadie reciba la carta correcta? Esta pregunta clásica (Montmort, 1708) conduce al trastorno números $D_n$ de Ejemplo 2.26. el La fórmula de inclusión-exclusión es sólo el primer paso: este problema desarrolla las recurrencias que calculan $D_n$ , dos más independientes pruebas de la fórmula, el sorprendente teorema de que $D_n$ es el entero más cercano a $n!/\eu$ , la distribución completa de puntos fijos de un permutación aleatorio, y la curiosa aritmética de la secuencia $(D_n)$ . En todo momento, $D_n$ denota el número de trastornos (punto fijo libre permutaciones) de $\intint1n$ , con la convención $D_0 = 1$ (el permutación vacío no tiene punto fijo).

Parte I — Small cases and the fixed-point census.

Calcule $D_1, D_2, D_3$ directamente y $D_4$ enumerando los Trastornos de $\{1, 2, 3, 4\}$ agrupados por el valor de $\sigma(1)$ . (Debería encontrar $D_4 = 9$ ).
Para $0 \leq k \leq n$ , muestre que el número $P_k(n)$ de permutaciones de $\intint1n$ con exactamente $k$ arreglado puntos es $\binom nk D_{n-k}$ .
Verifique el censo para $n = 4$ : calcule $P_0(4), \dots, P_4(4)$ y verifique que sumen $4! = 24$ . cual es mas probablemente para cuatro letras: ¿ninguna coincidencia o exactamente una coincidencia?
Por conteo doble (Método 2.22) los pares $(\sigma, i)$ con $\sigma(i) = i$ , muestran que

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

en promedio, un permutación aleatorio tiene exactamente uno punto fijo, cualquiera que sea $n \geq 1$ .

Parte II — Two recurrences and two new proofs of the formula.

Demuestre combinatoriamente, para $n \geq 1$ :

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

(Clasifique los trastornos $\sigma$ de $\intint1{n+1}$ por $j = \sigma(n+1)$ , luego por si $\sigma(j) = n + 1$ ; en En el caso $\sigma(j) \neq n+1$ , construya una biyección con el trastornos de $\intint1n$ redirigiendo la imagen inversa de $n + 1$ a $j$ .) Verifique la recurrencia numéricamente hasta $D_6$ .
Configuración $u_n = D_n - n D_{n-1}$ , deducir de la pregunta 5 que $u_{n+1} = -u_n$ , y concluir la segunda recurrencia:

$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$
De la pregunta 6, demuestre por inducción la fórmula de Ejemplo 2.26,

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

— una prueba totalmente independiente de la inclusión–exclusión.
(Inversión binomial) Sean $(a_n)$ y $(b_n)$ dos secuencias tales que $a_n = \sum_{k=0}^n \binom nk b_k$ para todos $n$ . demostrar que

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

(Primero establezca el revisión del trinomio $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$ , entonces utilizar la suma de filas alternas de Ejemplo 2.17.)
Aplicar la pregunta 8 a la identidad $n! = \sum_k \binom nk D_{n-k}$ de Ejercicio 2.11 para obtener una tercero prueba de la fórmula para $D_n$ .

Parte III — The nearest integer to $n!/\eu$ . Admitir para esta parte — la teoría está incorporada 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 serie alterna estricta vinculada $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ por cada $n$ .

Mostrar que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ para todos $n \in \N$ .
Deducir el teorema del titular: for every $n \geq 1$ , $D_n$ is the integer nearest to $n!/\eu$ . ¿Por qué el ¿Se necesita argumento $n \geq 1$ ?
Determine el signo del error: muestre que $D_n > n!/\eu$ exactamente cuando $n$ es par. (Localice el primer término desatendido de la serie alterna.)
Calcule $D_7$ hasta $D_{10}$ con la recurrencia de pregunta 5, luego verifique $D_{10}$ con $10!/\eu$ ( $10! = 3\,628\,800$ , $\eu \approx 2.718281828$ ).
(La probabilidad de verificación de sombrero) Sea $p_n = D_n/n!$ la probabilidad de que un permutación uniformemente aleatorio sea un trastorno. Mostrar $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ y calcule $p_6$ con cinco decimales. Comentario: ¿por qué? la respuesta a la pregunta de Montmort es esencialmente independiente de $n$ — ¿ya por una docena de letras?

Parte IV — The distribution of fixed points.

Reparar $k \in \N$ . Demuestre que la proporción de permutaciones de $\intint1n$ con exactamente $k$ puntos fijos satisface

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

(Estos valores límite, sumados a $1$ , forman el distribución de Poisson del parámetro $1$ , una central objeto del curso de probabilidad en el volumen del Año 2.)
Contando dos veces las tripletas $(\sigma, i, j)$ donde $i \neq j$ están fijadas por $\sigma$ , demuestre 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$ , por lo que el “spread” (varianza) del número de puntos fijos es igual a $1$ — nuevamente independiente de $n$ , coincidiendo nuevamente con la ley de Poisson.
Calcule la proporción de permutaciones que tiene al menos un punto fijo para $n = 4, 5, 6$ (como fracciones y hasta cuatro decimales) y comparar con $1 - \eu^{-1} \approx 0.6321$ .
Muestra directamente — no se necesitan límites — que $s_{n+2} - s_n = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , y deducir que las probabilidades $p_n = s_n$ de pregunta 14 oscilar: $p_0 > p_2 > p_4 > \dots$ y $p_1 < p_3 < p_5 < \dots$ , los valores pares (respectivamente impares) decreciente (o creciente) hacia el límite común $\eu^{-1}$ .
(Santa secreto) $n$ cada persona saca un nombre de un sombrero; si alguien dibuja su propio nombre, el dibujo entero es reiniciado desde cero. Usando el hecho estándar de que un evento de probabilidad $p$ toma en promedio $1/p$ intentos, estimar el número promedio de dibujos completos necesarios, y concluir que el procedimiento cuesta alrededor de $\eu \approx 2.72$ dibujos en promedio, esencialmente independientemente de $n$ .

Part V — The arithmetic of $D_n$ , and a synthesis.

Refinar la pregunta 5: mostrar que para $j \in \intint2n$ fijo, los trastornos de $\intint1n$ con $\sigma(1) = j$ número exactamente $D_{n-1} + D_{n-2}$ , independientemente de $j$ . Deduzca que $n - 1$ divide a $D_n$ por cada $n \geq 2$ .
Demuestre que $D_n$ es impar si y sólo si $n$ es par. (trabajo módulo $2$ en la recurrencia de la pregunta 6.)
Demuestre que $D_n \equiv (-1)^n \pmod n$ para $n \geq 1$ , y verifique la congruencia en el último dígito de $D_{10}$ .
Demuestre en la pregunta 6 que $\dfrac{D_n}{D_{n-1}} = n + \dfrac{(-1)^n}{D_{n-1}}$ para $n \geq 3$ , por lo que la relación de los números de trastorno consecutivos son casi exactamente $n$ ; explique en una oración por qué esto es consistente con $D_n \approx n!/\eu$ .
¿Dónde exactamente se utilizó este problema: (i) el producto y reglas de suma; (ii) doble cómputo; (iii) el binomio teorema; (iv) ¿la serie alterna admitida está limitada? uno frase cada uno.
Síntesis. La fórmula para $D_n$ ahora tiene tres pruebas. (inclusión-exclusión, recurrencia más inducción, binomio inversión). En un párrafo corto, compara lo que cada prueba explica: cuál calcula más rápido, cuál se generaliza a otros recuentos de punto fijo, 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$ (el único permutación corrige $1$ ), $D_2 = 1$ (el intercambio), $D_3 = 2$ (en notación de una línea: $231$ y $312$ ). Para $n = 4$ , agrupar por $\sigma(1)$ : con $\sigma(1) = 2$ los trastornos son $2143$ , $2341$ , $2413$ ; con $\sigma(1) = 3$ : $3142$ , $3412$ , $3421$ ; con $\sigma(1) = 4$ : $4123$ , $4312$ , $4321$ . tres en cada uno grupo: $D_4 = 9$ .

2. Un permutación con exactamente $k$ puntos fijos es determinado por la elección de su punto fijo conjunto $F$ ( $\binom nk$ maneras) junto con su restricción al complemento, que debe ser un permutación de puntos $n - k$ con punto fijo no ( $D_{n-k}$ formas). Las dos opciones son independientes y la La correspondencia es biyectivo: $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 fuerzan a un cuarto); $P_4(4) = 1$ . Suma: $9 + 8 + 6 + 0 + 1 = 24 = 4!$ . Ninguna coincidencia (casos $9$ ) supera exactamente una coincidencia (casos $8$ ) — por poco.

4. Cuente los pares $(\sigma, i)$ con $\sigma(i) = i$ . Para fijo $i$ , el permutaciones que fija $i$ son los permutaciones del otros puntos $n - 1$ : $(n-1)!$ de ellos. De ahí el número de pares. es $n \cdot (n-1)! = n!$ , y este número también es $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$ . Dividiendo por el número $n!$ de permutaciones: el número medio de puntos fijos es exactamente $1$ , por cada $n \geq 1$ .

5. Sea $\sigma$ un trastorno de $\intint1{n+1}$ y $j = \sigma(n+1) \in \intint1n$ : $n$ valores posibles. Case $\sigma(j) = n+1$ : los puntos $j$ y $n+1$ de intercambio, y $\sigma$ restringido a los puntos $n - 1$ restantes es una opción arbitraria. trastorno de ellos: $D_{n-1}$ posibilidades. Case $\sigma(j) \neq n+1$ : deja $i_0 = \sigma^{-1}(n+1)$ ; aquí $i_0 \neq j$ y $i_0 \leq n$ . Defina $\tau$ en $\intint1n$ por $\tau(i) = \sigma(i)$ para $i \neq i_0$ y $\tau(i_0) = j$ . Entonces $\tau$ es un permutación de $\intint1n$ (el valor $n+1$ ha sido reemplazado por el que falta valor $j$ ), y es un trastorno: $\tau(i_0) = j \neq i_0$ , y $\tau(i) = \sigma(i) \neq i$ en otro lugar. Por el contrario, desde un trastorno $\tau$ de $\intint1n$ y el valor $j$ , se recupera $\sigma$ configurando $\sigma(n+1) = j$ , $\sigma(\tau^{-1}(j)) = n+1$ y $\sigma = \tau$ en otros lugares: una biyección, dando $D_n$ posibilidades. Resumiendo $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}$ , entonces

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 .

Desde $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 en $n$ . Base: $D_0 = 1 = 0!\,s_0$ . Paso: asumiendo $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 ,

cual es la formula. No se utilizó inclusión-exclusión: sólo el Recurrencia combinatoria de la pregunta 5.

8. Revisión de trinomios, 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} .

Ahora sustituye $a_k = \sum_j \binom kj b_j$ e intercambia los dos. finito sumas:

\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 interna es la expansión de $(1 + (-1))^{n-j} = 0^{n-j}$ (teorema del binomio, Teorema 2.16): desaparece para $j < n$ y es igual a $1$ para $j = n$ . Sólo sobrevive $j = n$ , y el lado derecho es $b_n$ , como se afirma.

9. Por la simetría $\binom nk = \binom n{n-k}$ , el La identidad de Ejercicio 2.11 se reescribe como $n! = \sum_{k=0}^n \binom nk D_k$ . Aplicar 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!} ,

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

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

\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$ , $\frac1{n+1} \leq \frac12$ y el la desigualdad de la pregunta 10 es estricta: $D_n$ se encuentra a distancia $< \frac12$ de $n!/\eu$ , por lo que es el entero único más cercano. Para $n = 0$ el límite sólo da distancia $< 1$ , y efectivamente el reclamo falla allí: $0!/\eu \approx 0.368$ tiene el número entero más cercano $0$ , mientras que $D_0 = 1$ .

12. $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ es un series alternas con términos estrictamente decrecientes, por lo que su signo es el signo de su primer término $(-1)^{n+1}/(n+1)!$ . Por lo 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 cercano es $1\,334\,961$ — y $D_{10} > 10!/\eu$ , como predice la pregunta 12 incluso para ese $n$ .

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), contra $\eu^{-1} = 0.36788$ ; la brecha está por debajo de $1/7! = 1/5040 < 2 \times 10^{-4}$ . El $1/(n+1)!$ cota colapsa tan rápido que la probabilidad ya está fijada en muchos decimales para un docena de letras: la respuesta “sobre $36.8\%$ ” es, por cada propósito práctico, independiente de $n$ — la famosa sorpresa de el problema.

15. Por 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!}

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

16. Cuente los triples $(\sigma, i, j)$ con $i \neq j$ , $\sigma(i) = i$ , $\sigma(j) = j$ . Elegir primero el par ordenado: $n(n-1)$ maneras; el permutaciones que fija tanto $i$ como $j$ son los permutaciones de los puntos $n - 2$ restantes: $(n-2)!$ de ellos. Total: $n(n-1)(n-2)! = n!$ . Sumando primero sobre $\sigma$ cuenta, para cada $\sigma$ , los pares ordenados de elementos fijos distintos puntos: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$ . De ahí la identidad declarada; dividiendo por $n!$ , el promedio de $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ es $1$ , por lo que el promedio de $\abs{\mathrm{Fix}}^2$ es $1 + 1 = 2$ y la variación 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$ . Todo dentro de un porcentaje 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$ incluso la diferencia es negativo: $s_{n+2} < s_n$ , entonces $p_0 > p_2 > p_4 > \dots$ ; para $n$ impar es positivo: $p_1 < p_3 < p_5 < \dots$ Combinado con pregunta 12 (pares arriba de $\eu^{-1}$ , probabilidades abajo) y pregunta 14 (la distancia a $\eu^{-1}$ tiende a $0$ ): las dos escaleras se aprietan $\eu^{-1}$ entre ellos.

19. Un dibujo completo es un permutación aleatorio uniforme, válido cuando se trata de un trastorno: probabilidad $p_n \approx \eu^{-1}$ . Según el hecho citado, el número promedio de sorteos hasta el éxito es $1/p_n$ y la pregunta 14 muestra un error en $1/p_n \approx \eu$ . eso ya es insignificante para el pequeño $n$ . Así que un Papá Noel secreto con los reinicios cuestan en promedio alrededor de $\eu \approx 2.72$ completos dibujos — ya sea que la oficina tenga $6$ personas o $600$ .

20. Corrija $j \geq 2$ y ejecute la clasificación de la pregunta 5 en el valor $\sigma(1) = j$ . Si $\sigma(j) = 1$ : el resto Los puntos $n - 2$ conllevan un trastorno arbitrario, las formas $D_{n-2}$ . si $\sigma(j) \neq 1$ : redirigir la imagen inversa $i_0 = \sigma^{-1}(1)$ a $j$ exactamente como en la pregunta 5; esta es una biyección con el Trastornos de los puntos $n - 1$ $\{2, \dots, n\}$ : $D_{n-1}$ . maneras. Total $D_{n-1} + D_{n-2}$ , lo mismo para cada $j$ . sumando sobre los valores $n - 1$ de $j$ : $D_n = (n-1)(D_{n-1} + D_{n-2})$ , que muestra el factor $n - 1$ : $(n-1) \mid D_n$ .

21. Reclamación: $D_n$ es impar 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, $n = 1$ impar: la reclamación se mantiene. Si $n$ es par, $nD_{n-1}$ es par y $D_n \equiv 1$ : impar, como se afirma. Si $n$ es impar, entonces $n - 1$ es par, por lo que $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. Reducción de $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 de hecho $D_{10} = 1\,334\,961$ termina en el dígito $1$ .

23. Para $n \geq 3$ , $D_{n-1} \geq 1$ y división de 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 rápidamente tendiendo a $0$ . Consistencia: si $D_n \approx n!/\eu$ , entonces $D_n/D_{n-1} \approx n!/(n-1)! = n$ — el factor $\eu$ se cancela en la proporción, y la recurrencia lo confirma con exactitud $1/D_{n-1}$ .

24. (i) Las reglas del producto y la suma subyacen en cada recuento: preguntas 2 y 5 dividir conjuntos de permutaciones en independientes etapas. (ii) El doble conteo dio la media (pregunta 4) y la varianza (pregunta 16) del número de puntos fijos sin fórmula para $D_n$ en absoluto. (iii) El teorema del binomio evaluó la suma interna alterna $(1-1)^{n-j}$ que hace inversión binomial trabajo (pregunta 8). (iv) El límite de series alternas convirtió el suma exacta pero opaca $n!\,s_n$ en el enunciado transparente “entero más cercano a $n!/\eu$ ” (preguntas 10 a 14).

25. Inclusión–exclusión (Ejemplo 2.26 y Ejercicio 2.11) es la prueba conceptual: explica la suma alterna como correcciones de conteo excesivo y generaliza palabra por palabra al conteo elementos evitando cualquier familia de “malos” conjuntos. La ruta de la recurrencia (preguntas 5 a 7) calcula más rápido — tiempo lineal, entero exacto aritmética, sin factoriales — y es la fuente de la aritmética hechos de la Parte V. La inversión binomial (preguntas 8 a 9) coloca el fórmula dentro de una transformación general que reaparecerá dondequiera Dos sistemas triangulares de identidades se enfrentan. y el La apariencia de $\eu$ se explica mejor por la fórmula misma: el La proporción de trastornos es la suma parcial $s_n$ de la serie. para $\eu^{-1}$ , así eran los sobres de Montmort, tres décadas antes Notación de Euler, calculando ya el número $\eu$ .