Matemáticas de secundaria · Grades 10–12

27Combinatoria y Conteo

La combinatoria es el arte de contar sin enumerar. Sus dos elementales principios — sumar los tamaños de alternativas disjuntas, multiplicar los números de opciones independientes — basta con contar preparativos, permutaciones y subconjuntos de un conjunto finito, y culminan en el teorema del binomio.

27.1 Los dos principios de conteo

Escribimos $\abs{E}$ para el número de elementos (el cardinalidad) de un conjunto finito $E$ .

Proposición 27.1 (Principio de suma)

Si un conjunto finito $E$ se divide en subconjuntos $A_1, \dots, A_k$ (por pares disjunto, con unión $E$ ), entonces

\abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}.

Proposición 27.2 (Principio de multiplicación)

Si un objeto se construye mediante una sucesión de opciones $k$ , con opciones $n_1$ para la primera opción y, cualesquiera que sean las elecciones anteriores, $n_i$ opciones para el $i$ -ésimo, entonces el número de objetos construidos es $n_1 \times n_2 \times \dots \times n_k$ .

Demostración. Ambas afirmaciones se prueban por inducción sobre $k$ ; el caso $k = 2$ de la El segundo equivale a contar una matriz rectangular por filas. ∎

Ejemplo 27.3

Un restaurante ofrece 4 entrantes, 6 segundos, 3 postres: $4 \times 6 \times 3 = 72$ comidas diferentes de tres platos.

27.2 Tuplas, permutaciones, factoriales.

Definición 27.4 ( $k$ -tuplas)

Un $k$ -tupla de un conjunto $E$ es una lista ordenada $(x_1, \dots, x_k)$ de elementos de $E$ , se permiten repeticiones. Una tupla $k$ de distinto elementos es un acuerdo de $k$ elementos de $E$ .

Proposición 27.5

Deje $\abs E = n$ . El número de tuplas $k$ de $E$ es $n^k$ . el numero de preparativos de $k$ elementos de $E$ ( $0 \leq k \leq n$ ) es

n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!},

donde $n! = 1 \times 2 \times \dots \times n$ (y $0! = 1$ ) es el factorial de $n$ .

Demostración. Principio de multiplicación: para una tupla $k$ hay opciones $n$ en cada una de los pasos $k$ ; para acuerdo, opciones $n$ para $x_1$ , luego $n - 1$ para $x_2$ (se utiliza un elemento), …, $n - k + 1$ para $x_k$ . ∎

Definición 27.6 (Permutación)

Un permutación de $E$ es un acuerdo de todos los $n$ elementos de $E$ : un ordenamiento de $E$ . Por Proposición 27.5 (caso $k = n$ ), el número de permutaciones de un El conjunto de elementos $n$ es $n!$ .

Ejemplo 27.7

Cinco corredores pueden terminar una carrera en $5! = 120$ órdenes diferentes. el numero de posibles podios (tres primeros lugares) es $5 \times 4 \times 3 = 60$ .

27.3 Combinaciones y coeficientes binomiales.

Definición 27.8 (Combinaciones)

Un combinación de elementos $k$ de $E$ es un subconjunto de $E$ con elementos $k$ (sin orden, sin repetición). Su numero esta escrito $\dbinom{n}{k}$ , lea “ $n$ elija $k$ ”.

Teorema 27.9

Para $0 \leq k \leq n$ :

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

Demostración. Cuente los elementos preparativos de $k$ de $E$ de dos maneras. Directamente: $\frac{n!}{(n-k)!}$ . Alternativamente, elija primero el subconjunto subyacente ( $\binom nk$ formas), luego pídalo ( $k!$ formas); el principio de multiplicación da $\binom{n}{k}\,k!$ . equiparando, $\binom nk = \frac{n!}{k!(n-k)!}$ . ∎

Proposición 27.10 (Identidades básicas)

Para $0 \leq k \leq n$ :

\binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{k} = \binom{n}{n-k},

y regla de pascal: para $1 \leq k \leq n-1$ ,

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

Demostración. La simetría $\binom nk = \binom{n}{n-k}$ se cumple porque tomando complementos coincide con los subconjuntos de elementos $k$ con los subconjuntos de elementos $(n-k)$ , uno por uno. Para regla de pascal, arregla un elemento $a \in E$ y ordena los subconjuntos de elementos $k$ en aquellos que contienen $a$ — obtenidos uniendo $a$ a un elemento $(k-1)$ subconjunto de $E \setminus \{a\}$ , de los cuales hay $\binom{n-1}{k-1}$ — y aquellos que evitan $a$ , que son los subconjuntos de elementos $k$ de $E \setminus \{a\}$ , numeración $\binom{n-1}{k}$ . Concluir con la adición principio. ∎

regla de pascal genera los coeficientes fila por fila — Pascal triangulo: cada entrada es la suma de las dos anteriores.

el triangulo de pascal, filas n = 0 a 5: regla de pascal 41 + 42 = 52 en acción. — el triangulo de pascal, filas $n = 0$ a $5$ : regla de pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ en acción.

Teorema 27.11 (Teorema del binomio)

Para todos los $a, b \in \R$ (o $\C$ ) y $n \in \N$ :

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

Demostración. Ampliar el producto $(a+b)(a+b)\cdots(a+b)$ (factores $n$ ): cada término de la La expansión selecciona $a$ o $b$ en cada factor, produciendo $a^k b^{n-k}$ donde $k$ es el número de factores que contribuyen a $a$ . La cantidad de formas de elegir. estos factores $k$ entre $n$ es $\binom nk$ , que por lo tanto es el coeficiente de $a^k b^{n-k}$ . ∎

Corolario 27.12

$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ y $\displaystyle\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ ( $n \geq 1$ ).

Demostración. Tome $a = b = 1$ , luego $a = -1$ , $b = 1$ en el teorema del binomio. el primero La identidad también tiene un significado directo: un conjunto de elementos $n$ tiene subconjuntos $2^n$ (cada elemento está dentro o fuera: principio de multiplicación), ordenados por tamaño. ∎

Método 27.13 (Elegir el modelo correcto)

Antes de contar, responda dos preguntas: ¿Importa el orden? y ¿Se permiten repeticiones?

	order matters	order irrelevant
repetitions allowed	$n^k$ (tuples)	(university)
no repetitions	$\frac{n!}{(n-k)!}$ (preparativos)	$\binom nk$ (subsets)

Sacar bolas de una urna: con reemplazo, para $\to$ tuplas; sin reemplazo, con el fin $\to$ preparativos; un puñado de todos de una vez $\to$ subconjuntos.

27.4 Ceremonias

Ejercicio 27.1 ★

Una matrícula consta de 2 letras (A–Z), luego 3 dígitos y luego 2 letras. ¿Cuántas placas son posibles? ¿Cuántos no tienen carácter repetido?

Solución

Solución de Ejercicio 27.1.

Principio de multiplicación: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ .

Sin caracteres repetidos, las cuatro letras deben ser distintas. ( $26 \times 25 \times 24 \times 23$ formas, completando las posiciones de las letras en orden) y los tres dígitos distintos ( $10 \times 9 \times 8$ ):

26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8 = 358\,800 \times 720 = 258\,336\,000 .

Ejercicio 27.2 ★

Calcule $\dbinom{8}{3}$ , $\dbinom{10}{8}$ y simplifique $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$ .

Solución

Solución de Ejercicio 27.2.

$\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$ ; $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ ;

\frac{\binom n2}{\binom{n+1}2} = \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}.

Ejercicio 27.3 ★

En una clase de 30 estudiantes, se debe elegir un comité de 4 estudiantes, luego un presidente y un tesorero dentro del comité (una persona no puede ocupar ambos oficinas). ¿Cuántos resultados son posibles?

Solución

Solución de Ejercicio 27.3.

Elija el comité: $\binom{30}{4}$ formas. Luego elige presidente y tesorero entre los 4, en orden: $4 \times 3 = 12$ formas. totales

\binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 .

Ejercicio 27.4 ★

Expanda $(x + 2)^5$ y $(1 - x)^6$ usando el teorema del binomio. cual es el coeficiente de $x^3$ en $(2x + 3)^7$ ?

Solución

Solución de Ejercicio 27.4.

(x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 ,

(1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 .

En $(2x+3)^7$ , el término en $x^3$ es $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$ : el coeficiente es $22\,680$ .

Ejercicio 27.5 ★★

Una mano de póquer estándar consta de 5 cartas de una baraja de 52 cartas.

¿Cuántas manos hay?
¿Cuántas manos contienen exactamente un as? ¿Al menos un as?
¿Cuántas manos hay “full” (tres cartas de un valor, dos de otro)?

Solución

Solución de Ejercicio 27.5.

1. $\dbinom{52}{5} = 2\,598\,960$ .

2. Exactamente un as: elígelo ( $4$ formas) y completa con $4$ no ases: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . Al menos un as: conteo complementario, $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

3. Elige el rango del trío ( $13$ ), sus palos ( $\binom43 = 4$ ), el rango de la pareja ( $12$ restante), sus palos ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ .

Ejercicio 27.6 ★★

¿Cuántos anagramas (reordenamientos de letras, significativos o no) tiene el palabra MATEMÁTICAS? ¿La palabra PLÁTANO? (Pista para BANANA: primero coloque las tres A.)

Solución

Solución de Ejercicio 27.6.

MATH tiene 4 letras distintas: anagramas $4! = 24$ .

BANANA tiene 6 letras: tres A, dos N, una B. Elige las posiciones de las A ( $\binom63$ ), luego de las N entre el resto ( $\binom32$ ), toma la B el último lugar:

\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 .

(Equivalentemente $\frac{6!}{3!\,2!\,1!} = 60$ .)

Ejercicio 27.7 ★★

Acreditar la identidad $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) de dos maneras: mediante la fórmula factorial, y contando de dos maneras los pares (comité de $k$ personas, su presidente) elegido entre $n$ personas.

Solución

Solución de Ejercicio 27.7.

Algebraicamente:

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

Por doble conteo: cuenta pares (comité de $k$ , presidente en el mismo). Elija el comité ( $\binom nk$ ) y luego su presidente ( $k$ ): $k\binom nk$ pares. O elija primero al presidente (opciones $n$ ) y luego al otros miembros $k-1$ entre los pares restantes $n-1$ : $n\binom{n-1}{k-1}$ .

Ejercicio 27.8 ★★

Un camino en el plano va de $(0,0)$ a $(m, n)$ en pasos unitarios Este o Norte. Demuestre que el número de dichas rutas es $\dbinom{m+n}{m}$ .

Solución

Solución de Ejercicio 27.8.

Una ruta consta exactamente de $m + n$ pasos, de los cuales $m$ son Este y $n$ son Norte; está enteramente determinado por el conjunto de instantes (entre los $m+n$ ) en cuál da un paso hacia el este. Existen $\binom{m+n}{m}$ tales opciones.

Ejercicio 27.9 ★★★

Demuestre La identidad de Vandermonde: para $0 \leq k \leq m + n$ ,

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

contando los subconjuntos de elementos $k$ de un conjunto dividido en un grupo de $m$ y un grupo de $n$ . deducir eso $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ .

Solución

Solución de Ejercicio 27.9.

Dividir un conjunto de personas $m + n$ en un grupo $A$ de $m$ y un grupo $B$ de $n$ . Un subconjunto de elementos $k$ contiene algún número $j$ de miembros de $A$ ( $0 \leq j \leq k$ ) y $k - j$ miembros de $B$ ; para $j$ fijo hay $\binom mj \binom{n}{k-j}$ dichos subconjuntos y el principio de suma sobre $j$ 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},

utilizando la simetría $\binom{n}{n-j} = \binom nj$ .

Ejercicio 27.10 ★★★

Utilizando el teorema del binomio, demuestre que para todo $n \geq 1$ ,

\sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}.

(Sugerencia: diferencie $(1+x)^n$ o utilice Ejercicio 27.7).

Solución

Solución de Ejercicio 27.10.

Via Ejercicio 27.7:

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

por Corolario 27.12. Vía diferenciación: diferenciando $(1+x)^n = \sum_k \binom nk x^k$ da $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; evaluar en $x = 1$ .

27.5 Problema: el arte de contar dos veces

Problema 27.1

Problema de fin de semana — estrellas y barras, trastornadas sombreros e identidades demostradas contando una cosa de dos maneras

El truco más profundo de la combinatoria es sorprendentemente simple: contar la misma colección dos veces, por dos métodos diferentes, y equiparar las respuestas. Este problema practica los modelos de Método 27.13, agrega una técnica al curso del capítulo. no necesitaba — el estrellas y barras de conteo de helados — luego cuenta exactamente el famoso sombreros trastornados, y encuentra el número $\frac1\eu$ esperando en la parte inferior del sombrero pila, su tercera aparición en este libro.

Parte I — Choosing the model.

Cuente las placas formadas por las letras $2$ seguidas de $3$ dígitos; luego los anagramas de BANANA.
De una baraja de cartas $32$ , cuente las manos de cartas $5$ ; entonces las manos que contienen exactamente $2$ de los ases $4$ .
Un robot camina desde $(0,0)$ a $(4,3)$ usando solo la unidad Pasos hacia la derecha o hacia arriba: ¿cuántos caminos? (Codifique una ruta como palabra en R y U.)
Expande $(1 + x)^4$ por el teorema del binomio (Teorema 27.11); luego evaluar en $x = 1$ y $x = -1$ : ¿cuáles dos identidades sobre el los números $\binom nk$ abandonan?
Demuestre por conteo doble que $k\binom nk = n\binom{n-1}{k-1}$ (cuenta comités-con-presidente de dos maneras), y deducir $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ .

Parte II — Stars and bars.

Una heladería vende sabores $4$ ; usted ordena $10$ cucharadas (los sabores pueden repetirse, el orden en la taza es irrelevante). Codificar un pedido como una fila de estrellas $10$ (cucharadas) separadas por barras $3$ (cambios de sabor), y contar los pedidos.
Cuente los triples de números enteros no negativos con $x + y + z = 12$ .
Cuente los triples de positivo números enteros con $x + y + z = 12$ (sustituya $x = 1 + x'$ , etc.).
¿Cuántos monomios distintos aparecen en la expansión de $(a + b + c)^5$ ?
Método de verificación de cordura: contar los pedidos de $3$ cucharadas de sabores $2$ con la fórmula, luego enumere Todos ellos y comparar.
Diga exactamente dónde ingresó "las bolas son idénticas" codificación — y contar lo que sucede en su lugar si el las cucharadas se comen en orden (posiciones distintas), con Lista de verificación de Método 27.13.

Parte III — The deranged hats. Un trastorno mental es una redistribución de sombreros $n$ a sus propietarios de $n$ en los que nadie recibe su propio sombrero; dejar $D_n$ cuéntalos. (Problema 18.1 mostró que un invitado en promedio recupera su propio sombrero — ahora contamos el total fiestas desafortunadas exactamente.)

Calcular $D_1$ , $D_2$ , $D_3$ por listado y $D_4$ . pacientemente (o inteligentemente).
Justificar la recurrencia $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : invitado 1 recibe un sombrero $k \neq 1$ (opciones $n - 1$ ); dividir según si el invitado $k$ recibe el sombrero 1 o no. Verifique que reproduzca $D_4$ y calcule $D_5$ .
Para $n = 3$ , probar por inclusión–exclusión (resta las tareas de arreglar al menos un sombrero, vuelva a agregar el recuentos excesivos) que $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ e indique la fórmula general.
Calcular $\frac{D_5}{5!}$ y comparar con $\frac1\eu \approx 0.3679$ : el probabilidad que un gran grupo barajado desarregla completamente es $\frac1\eu$ — el tercer cameo de esta constante, después la lotería y la secretaria de Problema 23.1. (Por qué: la fórmula de la pregunta 14 es el comienzo de una serie famosa para $\eu^{-1}$ , contada en la universidad volúmenes.)
Papá Noel secreto entre amigos de $10$ : se sortean nombres uniformemente al azar. ¿Qué es el probabilidad del sorteo? es válido (nadie se dibuja a sí mismo), y cuántos ¿Los nuevos sorteos que debería esperar el grupo?

Parte IV — Counting twice, winning twice.

El lema del apretón de manos: en cualquier fiesta, sumando a los invitados el número de manos que cada apretón cuenta cada apretón de manos exactamente dos veces. Deduce que el número de invitados quien estrechó un número impar de manos siempre es par — y compruebe que el reclamo tiene sentido en una fiesta de tres invitados.
Prueba la joya $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ por inducción y verifíquelo para $n = 3$ . (El pequeño Gauss suma, al cuadrado, cuenta cubos.)
Identidad de Vandermonde (Ejercicio 27.9) vía caminos: interpretar $\binom{2n}{n}$ como caminos de celosía de tipo de pregunta 3 de $(0,0)$ a $(n,n)$ , corte cada una camino en su cruce de la antidiagonal, y explicar cómo aparece $\sum_j \binom nj^2$ .
Finale — los cuatro movimientos del contador, una línea cada uno con un ejemplo de este problema: multiplica las etapas y suma casos; codificar inteligentemente (estrellas y barras, palabras de ruta); contar lo mismo dos veces (comité con presidente, apretones de manos); restar lo no deseado y corregir lo recuentos excesivos (trastornos). Y observe dónde está el conteo va a trabajar a continuación: probabilidad, y las rutas del Capítulo de matrices y gráficas.

Solución

Solución de Problema 27.1.

Placas 1. $26^2 \times 10^3 = 676\,000$ . PLÁTANO: $6$ letras con A triplicada y N duplicada: $\frac{6!}{3!\,2!} = 60$ anagramas.

2. $\binom{32}{5} = 201\,376$ manos; $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ con exactamente dos ases.

3. Una ruta es una palabra con $4$ R y $3$ U: elija las posiciones U: $\binom73 = 35$ .

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ . en $x = 1$ : $\sum_k \binom nk = 2^n$ ; en $x = -1$ : $\sum_k (-1)^k \binom nk = 0$ — sumas de filas y filas alternas sumas de el triangulo de pascal.

5. Comités de $k$ personas con silla, de $n$ : elegir el comité y luego su presidente ( $\binom nk \times k$ ), o el presidente y luego los demás miembros ( $n \times \binom{n-1}{k-1}$ ): igual. Resumiendo $k$ : el El lado derecho suma $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ .

6. Una fila de estrellas $10$ y barras $3$ codifica el pedido. (cucharadas de sabor 1 antes de la primera barra, etc.); la fila tiene Símbolos $13$ y está determinado por las posiciones de las barras: $\binom{13}{3} = 286$ pedidos.

7. $12$ estrellas, $2$ barras: $\binom{14}{2} = 91$ .

8. Con $x', y', z' \geq 0$ y $x' + y' + z' = 9$ : $\binom{11}{2} = 55$ .

9. Un monomio $a^i b^j c^k$ con $i + j + k = 5$ : $\binom72 = 21$ .

10. Fórmula: $3$ estrellas, $1$ barra: $\binom41 = 4$ ; lista: $(3,0)$ , $(2,1)$ , $(1,2)$ , $(0,3)$ : acuerdo.

11. “Idéntico” ingresado cuando se declaró una orden no ser más que el cuenta por sabor — las estrellas no llevan nombres. Si las bolas se comen en orden, cada una de las $10$ posiciones distintas elige un sabor libremente: $4^{10} = 1\,048\,576$ secuencias — un modelo diferente y un mundo diferente (Método 27.13: siempre pregunta ¿ordenado? ¿distinto? ¿Se permite la repetición?).

12. $D_1 = 0$ ; $D_2 = 1$ (intercambio); $D_3 = 2$ (los dos $3$ -ciclos); $D_4 = 9$ .

13. El invitado 1 recibe sombrero $k \neq 1$ : $n - 1$ opciones. si El invitado $k$ obtiene el sombrero 1, los invitados $n - 2$ restantes se desorganizan. sus propios sombreros: $D_{n-2}$ maneras. Si el huésped $k$ hace no obtenga el sombrero 1, vuelva a etiquetar el sombrero 1 como el sombrero prohibido del invitado $k$ : el $n - 1$ los invitados restantes se deshacen: $D_{n-1}$ formas. Por lo tanto $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Comprobar: $D_4 = 3(2 + 1) = 9$ ; y $D_5 = 4(9 + 2) = 44$ .

14. De las asignaciones $3! = 6$ , restar aquellas arreglando al menos un sombrero: tres arreglan un sombrero determinado ( $2!$ cada uno, $3 \times 2 = 6$ ), contando en exceso los pares ( $3$ pares, $1!$ cada uno) que debe regresar, y volviendo a restar la identidad ( $1$ ): $D_3 = 6 - 6 + 3 - 1 = 2$ , es decir $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$ . en general $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ .

15. $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$ , ya cerca de $\frac1\eu \approx 0.3679$ : el suma alterna $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ marcha a $\eu^{-1}$ . Los sombreros de un gran partido se revuelven $36.8\,\%$ de la época — la de la lotería y la de la secretaria constante, tercer avistamiento.

16. $\P(\text{valid}) = \frac{D_{10}}{10!} \approx 0.368$ . Cada redibujo tiene éxito con probabilidad $\approx \frac1\eu$ , por lo que el número esperado de sorteos es aproximadamente $\eu \approx 2.7$ : presupuesto tres pases de sombrero.

17. Cada apretón de manos contribuye $2$ al total recuento de grados, por lo que la suma de los números de apretón de manos de todos los invitados es Incluso. Una suma de números enteros es par sólo si el número de números impares términos es par: los impares vienen en números pares. (A las tres invitados: los posibles perfiles de apretón de manos nunca tienen exactamente uno o tres entradas impares — marque las cuatro posibles graficos.)

18. $n = 1$ : $1 = 1$ . si $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ , agregando $(n+1)^3$ :

\frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} :

herencia. Para $n = 3$ : $1 + 8 + 27 = 36 = 6^2$ .

19. Un camino hacia $(n, n)$ hace $2n$ pasos y cruces la antidiagonal $x + y = n$ en exactamente un punto de la red $(j, n - j)$ ; la primera mitad es un camino con $j$ R entre $n$ pasos (opciones $\binom nj$ ), la segunda mitad, leída al revés, igualmente ( $\binom nj$ nuevamente, por simetría). resumiendo el punto de cruce: $\binom{2n}{n} = \sum_j \binom nj^2$ — La identidad de Vandermonde, dibujada.

20. Multiplica etapas, suma casos: placas y póquer. manos. Codificar: rutas como palabras RU, órdenes como estrellas y barras. Cuente dos veces: comités con presidente, apretones de manos, caminos intermedios. Resta y corrige: los sombreros trastornados, con $\frac1\eu$ como el residuo. Próximas paradas: estos conteos bajo probabilidad fracciones y los poderes de conteo de caminos de la adyacencia matrices dos capítulos más adelante.