Matemáticas de secundaria · Grades 10–12

27Combinatoria y conteo

La combinatoria es el arte de contar sin enumerar. Sus dos principios elementales (sumar los tamaños de alternativas disjuntas y multiplicar los números de elecciones independientes) bastan para contar las variaciones, las permutaciones y los 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 cardinal) de un conjunto finito $E$ .

Proposición 27.1 (Principio de la suma)

Si un conjunto finito $E$ se reparte en subconjuntos $A_1, \dots, A_k$ (disjuntos dos a dos y de unión $E$ ), entonces

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

Proposición 27.2 (Principio del producto)

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

Demostración. Las dos afirmaciones se demuestran por inducción sobre $k$ ; el caso $k = 2$ de la segunda equivale a contar por filas una tabla rectangular. ∎

Ejemplo 27.3

Un restaurante ofrece 4 entrantes, 6 platos principales y 3 postres: $4 \times 6 \times 3 = 72$ menús distintos de tres platos.

27.2 Tuplas, permutaciones, factoriales

Definición 27.4 ( $k$ -tuplas)

Una $k$ -tupla de un conjunto $E$ es una lista ordenada $(x_1, \dots, x_k)$ de elementos de $E$ , con repeticiones permitidas. Una $k$ -tupla de elementos distintos es una variación de $k$ elementos de $E$ .

Proposición 27.5

Sea $\abs E = n$ . El número de $k$ -tuplas de $E$ es $n^k$ . El número de variaciones 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 del producto: para una $k$ -tupla hay $n$ opciones en cada uno de los $k$ pasos; para una variación, $n$ opciones para $x_1$ , después $n - 1$ para $x_2$ (ya se ha usado un elemento), …, y $n - k + 1$ para $x_k$ . ∎

Definición 27.6 (Permutación)

Una permutación de $E$ es una variación de los $n$ elementos de $E$ : una ordenación de $E$ . Por la Proposición 27.5 (caso $k = n$ ), el número de permutaciones de un conjunto de $n$ elementos es $n!$ .

Ejemplo 27.7

Cinco corredores pueden terminar una carrera en $5! = 120$ órdenes distintos. El número de podios posibles (los tres primeros puestos) es $5 \times 4 \times 3 = 60$ .

27.3 Combinaciones y números combinatorios

Definición 27.8 (Combinaciones)

Una combinación de $k$ elementos de $E$ es un subconjunto de $E$ con $k$ elementos (sin orden y sin repetición). Su número se escribe $\dbinom{n}{k}$ , y se lee “ $n$ sobre $k$ ”.

Teorema 27.9

Para $0 \leq k \leq n$ :

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

Demostración. Contamos de dos maneras las variaciones de $k$ elementos de $E$ . Directamente: $\frac{n!}{(n-k)!}$ . De otro modo: elegimos primero el subconjunto subyacente ( $\binom nk$ maneras) y lo ordenamos después ( $k!$ maneras); el principio del producto da $\binom{n}{k}\,k!$ . Igualando, $\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 la 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 tomar complementarios empareja uno a uno los subconjuntos de $k$ elementos con los de $n-k$ elementos. Para la regla de Pascal, fijamos un elemento $a \in E$ y clasificamos los subconjuntos de $k$ elementos en los que contienen a $a$ (que se obtienen añadiendo $a$ a un subconjunto de $k-1$ elementos de $E \setminus \{a\}$ , y hay $\binom{n-1}{k-1}$ ) y los que no lo contienen, que son los subconjuntos de $k$ elementos de $E \setminus \{a\}$ , en número $\binom{n-1}{k}$ . Concluimos con el principio de la suma. ∎

La regla de Pascal genera los coeficientes fila a fila: es el triángulo de Pascal, en el que cada entrada es la suma de las dos que tiene encima.

El triángulo de Pascal, filas n = 0 a 5: la regla de Pascal 41 + 42 = 52 en acción. — El triángulo de Pascal, filas $n = 0$ a $5$ : la regla de Pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ en acción.

Teorema 27.11 (Teorema del binomio)

Para todos $a, b \in \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. Desarrollamos el producto $(a+b)(a+b)\cdots(a+b)$ ( $n$ factores): cada término del desarrollo elige $a$ o $b$ en cada factor y produce $a^k b^{n-k}$ , donde $k$ es el número de factores que aportan $a$ . El número de maneras de elegir esos $k$ factores entre $n$ es $\binom nk$ , que es, por tanto, 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. Tomamos $a = b = 1$ y después $a = -1$ , $b = 1$ en el teorema del binomio. La primera identidad tiene además un significado directo: un conjunto de $n$ elementos tiene $2^n$ subconjuntos (cada elemento está dentro o fuera: principio del producto), clasificados por tamaño. ∎

Método 27.13 (Elegir el modelo adecuado)

Antes de contar, responde a dos preguntas: ¿importa el orden? y ¿se permiten repeticiones?

	importa el orden	el orden da igual
con repeticiones	$n^k$ (tuplas)	(universidad)
sin repeticiones	$\frac{n!}{(n-k)!}$ (variaciones)	$\binom nk$ (subconjuntos)

Extraer bolas de una urna: con devolución y en orden $\to$ tuplas; sin devolución y en orden $\to$ variaciones; un puñado de golpe $\to$ subconjuntos.

27.4 Ejercicios

Ejercicio 27.1 ★

Una matrícula consta de 2 letras (A–Z), después 3 cifras y después 2 letras. ¿Cuántas matrículas son posibles? ¿Cuántas no repiten ningún carácter?

Solución

Solución de Ejercicio 27.1.

Principio del producto: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ .

Sin repetir caracteres, las cuatro letras han de ser distintas ( $26 \times 25 \times 24 \times 23$ maneras, rellenando las posiciones de las letras en orden) y las tres cifras también ( $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 ★

Calcula $\dbinom{8}{3}$ y $\dbinom{10}{8}$ , y simplifica $\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 alumnos hay que elegir una comisión de 4 alumnos y, dentro de la comisión, un presidente y un tesorero (una misma persona no puede ocupar los dos cargos). ¿Cuántos resultados son posibles?

Solución

Solución de Ejercicio 27.3.

Elegimos la comisión: $\binom{30}{4}$ maneras. Elegimos después el presidente y el tesorero entre los 4, en orden: $4 \times 3 = 12$ maneras. Total:

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

Ejercicio 27.4 ★

Desarrolla $(x + 2)^5$ y $(1 - x)^6$ con el teorema del binomio. ¿Cuál 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 consta de 5 cartas de una baraja de 52.

¿Cuántas manos hay?
¿Cuántas manos contienen exactamente un as? ¿Y al menos un as?
¿Cuántas manos son “full” (tres cartas de un mismo valor y dos de otro)?

Solución

Solución de Ejercicio 27.5.

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

2. Exactamente un as: lo elegimos ( $4$ maneras) y completamos con $4$ cartas que no sean ases: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . Al menos un as: por el suceso contrario, $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

3. Elegimos el valor del trío ( $13$ ), sus palos ( $\binom43 = 4$ ), el valor de la pareja ( $12$ restantes) y sus palos ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ .

Ejercicio 27.6 ★★

¿Cuántos anagramas (reordenaciones de las letras, con sentido o sin él) tiene la palabra ROMA? ¿Y la palabra BANANA? (Indicación para BANANA: coloca primero las tres aes.)

Solución

Solución de Ejercicio 27.6.

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

BANANA tiene 6 letras: tres aes, dos enes y una be. Elegimos las posiciones de las aes ( $\binom63$ ) y después las de las enes entre las restantes ( $\binom32$ ); la be ocupa el último hueco:

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

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

Ejercicio 27.7 ★★

Demuestra la identidad $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) de dos maneras: con la fórmula de los factoriales y contando de dos formas las parejas (comisión de $k$ personas, su presidente) elegidas 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: contamos las parejas (comisión de $k$ personas, presidente de la comisión). O bien elegimos la comisión ( $\binom nk$ ) y después su presidente ( $k$ ): $k\binom nk$ parejas. O bien elegimos primero al presidente ( $n$ opciones) y después a los otros $k-1$ miembros entre los $n-1$ restantes: $n\binom{n-1}{k-1}$ parejas.

Ejercicio 27.8 ★★

Un camino del plano va de $(0,0)$ a $(m, n)$ mediante pasos unitarios hacia el este o hacia el norte. Demuestra que el número de esos caminos es $\dbinom{m+n}{m}$ .

Solución

Solución de Ejercicio 27.8.

Un camino consta de exactamente $m + n$ pasos, de los cuales $m$ van hacia el este y $n$ hacia el norte; queda completamente determinado por el conjunto de instantes (entre los $m+n$ ) en los que se da un paso hacia el este. Hay $\binom{m+n}{m}$ elecciones así.

Ejercicio 27.9 ★★★

Demuestra 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 $k$ elementos de un conjunto repartido en un grupo de $m$ y otro de $n$ . Deduce que $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ .

Solución

Solución de Ejercicio 27.9.

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

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

Ejercicio 27.10 ★★★

Usando el teorema del binomio, demuestra que para todo $n \geq 1$ ,

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

(Indicación: deriva $(1+x)^n$ , o usa el Ejercicio 27.7.)

Solución

Solución de Ejercicio 27.10.

Con el 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 el Corolario 27.12. Derivando: al derivar $(1+x)^n = \sum_k \binom nk x^k$ se obtiene $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; se evalúa en $x = 1$ .

27.5 Problema: El arte de contar dos veces

Problema 27.1

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

El truco más profundo de la combinatoria es de una sencillez desarmante: contar dos veces la misma colección por dos métodos distintos e igualar las respuestas. Este problema practica los modelos del Método 27.13, añade una técnica que el curso del capítulo no necesitó (las estrellas y barras del recuento de helados), cuenta después con exactitud los famosos sombreros desarreglados y encuentra al número $\frac1\eu$ esperando al fondo del montón de sombreros: su tercera aparición en este libro.

Parte I — Elegir el modelo.

Cuenta las matrículas formadas por $2$ letras seguidas de $3$ cifras; y después los anagramas de BANANA.
De una baraja de $32$ cartas, cuenta las manos de $5$ cartas; y después las manos que contienen exactamente $2$ de los $4$ ases.
Un robot camina de $(0,0)$ a $(4,3)$ usando solo pasos unitarios a la derecha o hacia arriba: ¿cuántos caminos hay? (Codifica cada camino como una palabra en D y A.)
Desarrolla $(1 + x)^4$ con el teorema del binomio (Teorema 27.11) y evalúa después en $x = 1$ y en $x = -1$ : ¿qué dos identidades sobre los números $\binom nk$ caen solas?
Demuestra por doble conteo que $k\binom nk = n\binom{n-1}{k-1}$ (cuenta de dos maneras las comisiones con presidente) y deduce que $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ .

Parte II — Estrellas y barras.

Una heladería vende $4$ sabores y pides $10$ bolas (los sabores se pueden repetir y el orden en la tarrina da igual). Codifica un pedido como una fila de $10$ estrellas (las bolas) separadas por $3$ barras (los cambios de sabor) y cuenta los pedidos.
Cuenta las ternas de enteros no negativos con $x + y + z = 12$ .
Cuenta las ternas de enteros positivos con $x + y + z = 12$ (sustituye $x = 1 + x'$ , etc.).
¿Cuántos monomios distintos aparecen en el desarrollo de $(a + b + c)^5$ ?
Comprueba el método: cuenta con la fórmula los pedidos de $3$ bolas con $2$ sabores, enuméralos todos después y compara.
Di exactamente en qué punto entró en la codificación que “las bolas son idénticas”, y cuenta qué pasaría si las bolas se comieran en orden (posiciones distintas), con la lista de comprobación del Método 27.13.

Parte III — Los sombreros desarreglados. Un desarreglo es un reparto de $n$ sombreros a sus $n$ dueños en el que nadie recibe el suyo; sea $D_n$ el número de desarreglos. (El Problema 18.1 mostró que, de media, un invitado recupera su propio sombrero; ahora contamos con exactitud las fiestas totalmente aciagas.)

Calcula $D_1$ , $D_2$ y $D_3$ enumerando, y $D_4$ con paciencia (o con astucia).
Justifica la recurrencia $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : el invitado 1 recibe algún sombrero $k \neq 1$ ( $n - 1$ opciones); separa los casos según si el invitado $k$ recibe el sombrero 1 o no. Comprueba que reproduce $D_4$ y calcula $D_5$ .
Para $n = 3$ , demuestra por inclusión-exclusión (restando los repartos que fijan al menos un sombrero y devolviendo los excesos) que $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ , y enuncia la fórmula general.
Calcula $\frac{D_5}{5!}$ y compáralo con $\frac1\eu \approx 0.3679$ : la probabilidad de que una fiesta grande se desarregle por completo es $\frac1\eu$ , la tercera aparición estelar de esta constante, tras la lotería y la secretaria del Problema 23.1. (¿Por qué? La fórmula de la pregunta 14 es el comienzo de una serie famosa para $\eu^{-1}$ , que se cuenta en los volúmenes universitarios.)
Amigo invisible entre $10$ amigos: los nombres se sacan al azar de manera uniforme. ¿Cuál es la probabilidad de que el sorteo sea válido (nadie se saca a sí mismo) y cuántas repeticiones del sorteo debe esperar el grupo?

Parte IV — Contar dos veces, ganar dos veces.

El lema de los apretones de manos: en cualquier fiesta, sumar sobre los invitados el número de manos que estrechó cada uno cuenta cada apretón exactamente dos veces. Deduce que el número de invitados que estrecharon un número impar de manos es siempre par, y comprueba que la afirmación tiene sentido en una fiesta de tres invitados.
Demuestra la joya $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ por inducción y compruébala para $n = 3$ . (La suma del pequeño Gauss, elevada al cuadrado, cuenta cubos.)
La identidad de Vandermonde (Ejercicio 27.9) mediante caminos: interpreta $\binom{2n}{n}$ como los caminos reticulares del tipo de la pregunta 3 de $(0,0)$ a $(n,n)$ , corta cada camino en su cruce con la antidiagonal y explica cómo aparece $\sum_j \binom nj^2$ .
Final: los cuatro movimientos del que cuenta, una línea para cada uno con un ejemplo de este problema: multiplicar etapas y sumar casos; codificar con astucia (estrellas y barras, palabras de caminos); contar dos veces lo mismo (la comisión con presidente, los apretones de manos); y restar lo indeseado corrigiendo los excesos (los desarreglos). Y fíjate en dónde se pone a trabajar el conteo a continuación: en la probabilidad y en los caminos del capítulo de matrices y grafos.

Solución

Solución de Problema 27.1.

1. $26^2 \times 10^3 = 676\,000$ matrículas. BANANA: $6$ letras con la a triplicada y la 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. Un camino es una palabra con $4$ letras D y $3$ letras A: se eligen las posiciones de las A: $\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$ : las sumas de las filas y las sumas alternadas de las filas del triángulo de Pascal.

5. Comisiones de $k$ personas con presidente, elegidas entre $n$ : o bien se elige la comisión y después su presidente ( $\binom nk \times k$ ), o bien el presidente y después los demás miembros ( $n \times \binom{n-1}{k-1}$ ): son iguales. Sumando sobre $k$ , el segundo miembro suma $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ .

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

7. $12$ estrellas y $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. Con la fórmula: $3$ estrellas y $1$ barra: $\binom41 = 4$ ; enumerando: $(3,0)$ , $(2,1)$ , $(1,2)$ , $(0,3)$ : coinciden.

11. Lo de “idénticas” entró cuando se declaró que un pedido no era más que el recuento por sabor: las estrellas no llevan nombre. Si las bolas se comen en orden, cada una de las $10$ posiciones distintas elige sabor libremente: $4^{10} = 1\,048\,576$ secuencias; otro modelo y otro mundo (Método 27.13: pregunta siempre ¿ordenado?, ¿distintos?, ¿con repetición?).

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

13. El invitado 1 recibe el sombrero $k \neq 1$ : $n - 1$ opciones. Si el invitado $k$ recibe el sombrero 1, los $n - 2$ invitados restantes desarreglan sus propios sombreros: $D_{n-2}$ maneras. Si el invitado $k$ no recibe el sombrero 1, renombramos el sombrero 1 como el sombrero prohibido del invitado $k$ : los $n - 1$ invitados restantes desarreglan: $D_{n-1}$ maneras. Por tanto, $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Comprobación: $D_4 = 3(2 + 1) = 9$ ; y $D_5 = 4(9 + 2) = 44$ .

14. De los $3! = 6$ repartos, restamos los que fijan al menos un sombrero: tres fijan un sombrero dado ( $2!$ cada uno, $3 \times 2 = 6$ ), lo que cuenta de más las parejas ( $3$ parejas, $1!$ cada una), que hay que devolver, y vuelve a restarse 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$ : la suma alternada $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ marcha hacia $\eu^{-1}$ . Los sombreros de una fiesta grande se desarreglan alrededor del $36.8\,\%$ de las veces: la constante de la lotería y de la secretaria, en su tercera aparición.

16. $\P(\text{válido}) = \frac{D_{10}}{10!} \approx 0.368$ . Cada repetición del sorteo sale bien con probabilidad $\approx \frac1\eu$ , así que el número esperado de sorteos es de en torno a $\eu \approx 2.7$ : hay que contar con tres rondas de sombrero.

17. Cada apretón aporta $2$ al recuento total de manos estrechadas, así que la suma de los números de todos los invitados es par. Una suma de enteros es par solo si el número de sumandos impares es par: los que estrechan un número impar de manos vienen en cantidad par. (Con tres invitados: ningún perfil de apretones tiene exactamente una o tres entradas impares; compruébalo con los cuatro grafos posibles.)

18. $n = 1$ : $1 = 1$ . Si $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ , al añadir $(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} :

paso de inducción hecho. Para $n = 3$ : $1 + 8 + 27 = 36 = 6^2$ .

19. Un camino hasta $(n, n)$ da $2n$ pasos y cruza la antidiagonal $x + y = n$ exactamente en un punto de la retícula $(j, n - j)$ ; la primera mitad es un camino con $j$ letras D entre $n$ pasos ( $\binom nj$ elecciones), y la segunda mitad, leída al revés, otro tanto ( $\binom nj$ de nuevo, por simetría). Sumando sobre el punto de cruce: $\binom{2n}{n} = \sum_j \binom nj^2$ : la identidad de Vandermonde, dibujada.

20. Multiplicar etapas y sumar casos: las matrículas y las manos de póquer. Codificar: los caminos como palabras de D y A, y los pedidos como estrellas y barras. Contar dos veces: la comisión con presidente, los apretones de manos y los caminos cortados por la mitad. Restar y corregir: los sombreros desarreglados, con $\frac1\eu$ como residuo. Próximas paradas: estos recuentos bajo las fracciones de la probabilidad y el recuento de caminos con las potencias de las matrices de adyacencia, dos capítulos más adelante.

Términos definidos en este capítulo

Ver los 395 términos del glosario