Matemática do ensino médio · Grades 10–12

27Análise combinatória e contagem

A análise combinatória é a arte de contar sem listar. Seus dois princípios elementares — somar os tamanhos de alternativas disjuntas, multiplicar os números de escolhas independentes — bastam para contar os arranjos, as permutações e os subconjuntos de um conjunto finito, e culminam no teorema binomial.

27.1 Os dois princípios de contagem

Escrevemos $\abs{E}$ para o número de elementos (a cardinalidade) de um conjunto finito $E$ .

Proposição 27.1 (Princípio aditivo)

Se um conjunto finito $E$ é repartido em subconjuntos $A_1, \dots, A_k$ (dois a dois disjuntos, com união $E$ ), então

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

Proposição 27.2 (Princípio multiplicativo)

Se um objeto é construído por uma sucessão de $k$ escolhas, com $n_1$ opções para a primeira e, quaisquer que tenham sido as escolhas anteriores, $n_i$ opções para a $i$ -ésima, então o número de objetos construídos é $n_1 \times n_2 \times \dots \times n_k$ .

Demonstração. Os dois enunciados se demonstram por indução em $k$ ; o caso $k = 2$ do segundo equivale a contar por linhas um quadro retangular. ∎

Exemplo 27.3

Um restaurante oferece 4 entradas, 6 pratos principais e 3 sobremesas: $4 \times 6 \times 3 = 72$ refeições diferentes de três pratos.

27.2 Sequências, permutações, fatoriais

Definição 27.4 (Sequências de $k$ elementos)

Uma sequência de $k$ elementos de um conjunto $E$ é uma lista ordenada $(x_1, \dots, x_k)$ de elementos de $E$ , com repetições permitidas. Uma sequência de $k$ elementos distintos é um arranjo de $k$ elementos de $E$ .

Proposição 27.5

Seja $\abs E = n$ . O número de sequências de $k$ elementos de $E$ é $n^k$ . O número de arranjos de $k$ elementos de $E$ ( $0 \leq k \leq n$ ) é

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

em que $n! = 1 \times 2 \times \dots \times n$ (e $0! = 1$ ) é o fatorial de $n$ .

Demonstração. Princípio multiplicativo: para uma sequência há $n$ opções em cada um dos $k$ passos; para um arranjo, $n$ opções para $x_1$ , depois $n - 1$ para $x_2$ (um elemento já foi usado), …, $n - k + 1$ para $x_k$ . ∎

Definição 27.6 (Permutação)

Uma permutação de $E$ é um arranjo de todos os $n$ elementos de $E$ : uma ordenação de $E$ . Pela Proposição 27.5 (caso $k = n$ ), o número de permutações de um conjunto de $n$ elementos é $n!$ .

Exemplo 27.7

Cinco corredores podem terminar uma prova em $5! = 120$ ordens diferentes. O número de pódios possíveis (três primeiros lugares) é $5 \times 4 \times 3 = 60$ .

27.3 Combinações e coeficientes binomiais

Definição 27.8 (Combinações)

Uma combinação de $k$ elementos de $E$ é um subconjunto de $E$ com $k$ elementos (sem ordem, sem repetição). Seu número escreve-se $\dbinom{n}{k}$ , lido “ $n$ escolhe $k$ ”.

Teorema 27.9

Para $0 \leq k \leq n$ :

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

Demonstração. Conte de duas maneiras os arranjos de $k$ elementos de $E$ . Diretamente: $\frac{n!}{(n-k)!}$ . Alternativamente, escolha primeiro o subconjunto subjacente ( $\binom nk$ maneiras) e depois ordene-o ( $k!$ maneiras); o princípio multiplicativo dá $\binom{n}{k}\,k!$ . Igualando, $\binom nk = \frac{n!}{k!(n-k)!}$ . ∎

Proposição 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},

e a relação de Pascal: para $1 \leq k \leq n-1$ ,

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

Demonstração. A simetria $\binom nk = \binom{n}{n-k}$ vale porque tomar complementares casa um a um os subconjuntos de $k$ elementos com os de $n-k$ elementos. Para a relação de Pascal, fixe um elemento $a \in E$ e separe os subconjuntos de $k$ elementos entre os que contêm $a$ — obtidos juntando $a$ a um subconjunto de $k-1$ elementos de $E \setminus \{a\}$ , dos quais há $\binom{n-1}{k-1}$ — e os que evitam $a$ , que são os subconjuntos de $k$ elementos de $E \setminus \{a\}$ , em número de $\binom{n-1}{k}$ . Conclua pelo princípio aditivo. ∎

A relação de Pascal gera os coeficientes linha a linha — o triângulo de Pascal: cada entrada é a soma das duas acima dela.

O triângulo de Pascal, linhas n = 0 a 5: a relação de Pascal 41 + 42 = 52 em ação. — O triângulo de Pascal, linhas $n = 0$ a $5$ : a relação de Pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ em ação.

Teorema 27.11 (Teorema binomial)

Para todos $a, b \in \R$ (ou $\C$ ) e $n \in \N$ :

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

Demonstração. Expanda o produto $(a+b)(a+b)\cdots(a+b)$ ( $n$ fatores): cada termo da expansão escolhe $a$ ou $b$ em cada fator, produzindo $a^k b^{n-k}$ , em que $k$ é o número de fatores que contribuíram com $a$ . O número de maneiras de escolher esses $k$ fatores entre $n$ é $\binom nk$ , que é, portanto, o coeficiente de $a^k b^{n-k}$ . ∎

Corolário 27.12

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

Demonstração. Tome $a = b = 1$ e depois $a = -1$ , $b = 1$ no teorema binomial. A primeira identidade também tem sentido direto: um conjunto de $n$ elementos tem $2^n$ subconjuntos (cada elemento entra ou não: princípio multiplicativo), separados por tamanho. ∎

Método 27.13 (Escolher o modelo certo)

Antes de contar, responda a duas perguntas: a ordem importa? e são permitidas repetições?

	a ordem importa	a ordem não importa
com repetição	$n^k$ (sequências)	(graduação)
sem repetição	$\frac{n!}{(n-k)!}$ (arranjos)	$\binom nk$ (subconjuntos)

Retirar bolas de uma urna: com reposição, em ordem $\to$ sequências; sem reposição, em ordem $\to$ arranjos; um punhado de uma vez $\to$ subconjuntos.

27.4 Exercícios

Exercício 27.1 ★

Uma placa de veículo é formada por 2 letras (A–Z), depois 3 algarismos e depois 2 letras. Quantas placas são possíveis? Quantas não têm nenhum caractere repetido?

Solução

Solução de Exercício 27.1.

Princípio multiplicativo: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$ .

Sem caracteres repetidos, as quatro letras têm de ser distintas ( $26 \times 25 \times 24 \times 23$ maneiras, preenchendo em ordem as posições de letra) e os três algarismos 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 .

Exercício 27.2 ★

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

Solução

Solução de Exercício 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}.

Exercício 27.3 ★

Em uma turma de 30 alunos, deve-se eleger uma comissão de 4 alunos e, dentro dela, um presidente e um tesoureiro (uma mesma pessoa não pode ocupar os dois cargos). Quantos resultados são possíveis?

Solução

Solução de Exercício 27.3.

Escolha a comissão: $\binom{30}{4}$ maneiras. Depois escolha presidente e tesoureiro entre os 4, em ordem: $4 \times 3 = 12$ maneiras. Total:

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

Exercício 27.4 ★

Expanda $(x + 2)^5$ e $(1 - x)^6$ usando o teorema binomial. Qual é o coeficiente de $x^3$ em $(2x + 3)^7$ ?

Solução

Solução de Exercício 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 .

Em $(2x+3)^7$ , o termo em $x^3$ é $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$ : o coeficiente é $22\,680$ .

Exercício 27.5 ★★

Uma mão de pôquer padrão é formada por 5 cartas de um baralho de 52 cartas.

Quantas mãos existem?
Quantas mãos contêm exatamente um ás? E pelo menos um ás?
Quantas mãos são “full houses” (três cartas de um valor e duas de outro)?

Solução

Solução de Exercício 27.5.

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

2. Exatamente um ás: escolha-o ( $4$ maneiras) e complete com $4$ cartas que não sejam ases: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . Pelo menos um ás: contagem pelo complementar, $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

3. Escolha o valor da trinca ( $13$ ), seus naipes ( $\binom43 = 4$ ), o valor do par ( $12$ restantes) e seus naipes ( $\binom42 = 6$ ): $13 \times 4 \times 12 \times 6 = 3744$ .

Exercício 27.6 ★★

Quantos anagramas (rearranjos das letras, com ou sem sentido) tem a palavra MATE? E a palavra BANANA? (Sugestão para BANANA: coloque primeiro os três A.)

Solução

Solução de Exercício 27.6.

MATE tem 4 letras distintas: $4! = 24$ anagramas.

BANANA tem 6 letras: três A, dois N e um B. Escolha as posições dos A ( $\binom63$ ) e depois as dos N entre as restantes ( $\binom32$ ); o B fica com a última vaga:

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

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

Exercício 27.7 ★★

Demonstre a identidade $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ( $1 \leq k \leq n$ ) de duas maneiras: pela fórmula com fatoriais e contando de duas maneiras os pares (comissão de $k$ pessoas, seu presidente) escolhidos entre $n$ pessoas.

Solução

Solução de Exercício 27.7.

Algebricamente:

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 contagem dupla: conte os pares (comissão de $k$ pessoas, presidente dela). Ou escolha a comissão ( $\binom nk$ ) e depois seu presidente ( $k$ ): $k\binom nk$ pares. Ou escolha o presidente primeiro ( $n$ opções) e depois os outros $k-1$ membros entre os $n-1$ restantes: $n\binom{n-1}{k-1}$ pares.

Exercício 27.8 ★★

Um caminho no plano vai de $(0,0)$ até $(m, n)$ por passos unitários para leste ou para o norte. Mostre que o número desses caminhos é $\dbinom{m+n}{m}$ .

Solução

Solução de Exercício 27.8.

Um caminho é formado por exatamente $m + n$ passos, dos quais $m$ são para leste e $n$ para o norte; ele fica inteiramente determinado pelo conjunto dos instantes (entre os $m+n$ ) em que se anda para leste. Há $\binom{m+n}{m}$ escolhas assim.

Exercício 27.9 ★★★

Demonstre a identidade 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 os subconjuntos de $k$ elementos de um conjunto dividido em um grupo de $m$ e um grupo de $n$ . Deduza que $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$ .

Solução

Solução de Exercício 27.9.

Divida um conjunto de $m + n$ pessoas em um grupo $A$ de $m$ e um grupo $B$ de $n$ . Um subconjunto de $k$ elementos contém um certo número $j$ de membros de $A$ ( $0 \leq j \leq k$ ) e $k - j$ membros de $B$ ; para $j$ fixo há $\binom mj \binom{n}{k-j}$ subconjuntos assim, e o princípio aditivo em $j$ dá a identidade de Vandermonde.

Com $m = n = k$ :

\binom{2n}{n} = \sum_{j=0}^n \binom nj \binom{n}{n-j} = \sum_{j=0}^n \binom nj^{2},

usando a simetria $\binom{n}{n-j} = \binom nj$ .

Exercício 27.10 ★★★

Usando o teorema binomial, mostre que, para todo $n \geq 1$ ,

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

(Sugestão: derive $(1+x)^n$ ou use o Exercício 27.7.)

Solução

Solução de Exercício 27.10.

Pelo Exercício 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},

pelo Corolário 27.12. Por derivação: derivar $(1+x)^n = \sum_k \binom nk x^k$ dá $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; calcule em $x = 1$ .

27.5 Problema: A arte de contar duas vezes

Problema 27.1

Problema de fim de semana — estrelas e barras, chapéus desarranjados e identidades demonstradas contando uma mesma coisa de dois modos

O truque mais profundo da combinatória é desarmadoramente simples: conte a mesma coleção duas vezes, por dois métodos diferentes, e iguale as respostas. Este problema pratica os modelos do Método 27.13, acrescenta uma técnica de que o curso do capítulo não precisou — as estrelas e barras da contagem de sorvetes —, conta em seguida os famosos chapéus desarranjados de modo exato e encontra o número $\frac1\eu$ à espera no fundo da pilha de chapéus, sua terceira aparição neste livro.

Parte I — Escolher o modelo.

Conte as placas formadas por $2$ letras seguidas de $3$ algarismos; depois os anagramas de BANANA.
De um baralho de $32$ cartas, conte as mãos de $5$ cartas; depois as mãos que contêm exatamente $2$ dos $4$ ases.
Um robô caminha de $(0,0)$ até $(4,3)$ usando apenas passos unitários para a direita ou para cima: quantos caminhos? (Codifique um caminho como uma palavra em D e C.)
Expanda $(1 + x)^4$ pelo teorema binomial (Teorema 27.11); depois calcule em $x = 1$ e $x = -1$ : que duas identidades sobre os números $\binom nk$ caem daí?
Demonstre por contagem dupla que $k\binom nk = n\binom{n-1}{k-1}$ (conte comissões-com-presidente de dois modos) e deduza $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ .

Parte II — Estrelas e barras.

Uma sorveteria vende $4$ sabores; você pede $10$ bolas (os sabores podem se repetir, e a ordem na taça é irrelevante). Codifique um pedido como uma fileira de $10$ estrelas (bolas) separadas por $3$ barras (trocas de sabor) e conte os pedidos.
Conte as ternas de inteiros não negativos com $x + y + z = 12$ .
Conte as ternas de inteiros positivos com $x + y + z = 12$ (substitua $x = 1 + x'$ etc.).
Quantos monômios distintos aparecem na expansão de $(a + b + c)^5$ ?
Teste de sanidade do método: conte pela fórmula os pedidos de $3$ bolas com $2$ sabores, depois liste todos e compare.
Diga exatamente onde “as bolas são idênticas” entrou na codificação — e conte o que acontece se as bolas forem comidas em ordem (posições distintas), com a lista de verificação do Método 27.13.

Parte III — Os chapéus desarranjados. Um desarranjo é uma redistribuição de $n$ chapéus aos seus $n$ donos em que ninguém recebe o próprio chapéu; seja $D_n$ o número deles. (O Problema 18.1 mostrou que, em média, um convidado recupera o próprio chapéu — agora contamos exatamente as festas totalmente azaradas.)

Calcule $D_1$ , $D_2$ , $D_3$ listando, e $D_4$ com paciência (ou com esperteza).
Justifique a recorrência $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : o convidado 1 recebe algum chapéu $k \neq 1$ ( $n - 1$ escolhas); separe conforme o convidado $k$ receba ou não o chapéu 1. Verifique que ela reproduz $D_4$ e calcule $D_5$ .
Para $n = 3$ , demonstre por inclusão e exclusão (subtraia as distribuições que fixam pelo menos um chapéu e devolva as contagens excedentes) que $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ , e enuncie a fórmula geral.
Calcule $\frac{D_5}{5!}$ e compare com $\frac1\eu \approx 0.3679$ : a probabilidade de uma festa grande se desarranjar por completo é $\frac1\eu$ — a terceira participação dessa constante, depois da loteria e da secretária do Problema 23.1. (Motivo: a fórmula da questão 14 é o começo de uma série famosa para $\eu^{-1}$ , contada nos volumes de graduação.)
Amigo secreto entre $10$ amigos: os nomes são sorteados de modo uniforme. Qual é a probabilidade de o sorteio ser válido (ninguém tirar a si mesmo) e quantos re-sorteios o grupo deve esperar?

Parte IV — Contar duas vezes, ganhar duas vezes.

O lema dos apertos de mão: em qualquer festa, somar sobre os convidados o número de mãos que cada um apertou conta cada aperto exatamente duas vezes. Deduza que o número de convidados que apertaram um número ímpar de mãos é sempre par — e verifique que a afirmação faz sentido numa festa de três convidados.
Demonstre por indução a joia $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ e verifique-a para $n = 3$ . (A soma do pequeno Gauss, ao quadrado, conta cubos.)
A identidade de Vandermonde (Exercício 27.9) por caminhos: interprete $\binom{2n}{n}$ como caminhos reticulados do tipo da questão 3 de $(0,0)$ até $(n,n)$ , corte cada caminho no cruzamento da antidiagonal e explique como $\sum_j \binom nj^2$ aparece.
Final — os quatro movimentos do contador, uma linha para cada com um exemplo deste problema: multiplicar etapas e somar casos; codificar com esperteza (estrelas e barras, palavras de caminho); contar a mesma coisa duas vezes (comissão com presidente, apertos de mão); subtrair o indesejado e corrigir os excessos (desarranjos). E note para onde a contagem vai trabalhar em seguida: a probabilidade e os caminhos do capítulo de matrizes e grafos.

Solução

Solução de Problema 27.1.

1. $26^2 \times 10^3 = 676\,000$ placas. BANANA: $6$ letras com A triplicado e N duplicado: $\frac{6!}{3!\,2!} = 60$ anagramas.

2. $\binom{32}{5} = 201\,376$ mãos; $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ com exatamente dois ases.

3. Um caminho é uma palavra com $4$ D e $3$ C: escolha as posições dos C: $\binom73 = 35$ .

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ . Em $x = 1$ : $\sum_k \binom nk = 2^n$ ; em $x = -1$ : $\sum_k (-1)^k \binom nk = 0$ — as somas e as somas alternadas das linhas do triângulo de Pascal.

5. Comissões de $k$ pessoas com um presidente, entre $n$ : escolha a comissão e depois o presidente ( $\binom nk \times k$ ), ou o presidente e depois os demais membros ( $n \times \binom{n-1}{k-1}$ ): iguais. Somando em $k$ : o lado direito soma $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$ .

6. Uma fileira de $10$ estrelas e $3$ barras codifica o pedido (as bolas do sabor 1 antes da primeira barra etc.); a fileira tem $13$ símbolos e fica determinada pelas posições das barras: $\binom{13}{3} = 286$ pedidos.

7. $12$ estrelas e $2$ barras: $\binom{14}{2} = 91$ .

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

9. Um monômio $a^i b^j c^k$ com $i + j + k = 5$ : $\binom72 = 21$ .

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

11. O “idênticas” entrou quando se declarou que um pedido não é nada além das quantidades por sabor — as estrelas não têm nome. Se as bolas forem comidas em ordem, cada uma das $10$ posições distintas escolhe livremente um sabor: $4^{10} = 1\,048\,576$ sequências — outro modelo e outro mundo (Método 27.13: pergunte sempre ordenado? distinto? com repetição?).

12. $D_1 = 0$ ; $D_2 = 1$ (a troca); $D_3 = 2$ (os dois ciclos de comprimento $3$ ); $D_4 = 9$ .

13. O convidado 1 recebe o chapéu $k \neq 1$ : $n - 1$ escolhas. Se o convidado $k$ recebe o chapéu 1, os $n - 2$ convidados restantes desarranjam os próprios chapéus: $D_{n-2}$ maneiras. Se o convidado $k$ não recebe o chapéu 1, rebatize o chapéu 1 como o chapéu proibido do convidado $k$ : os $n - 1$ convidados restantes desarranjam: $D_{n-1}$ maneiras. Logo $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Verificação: $D_4 = 3(2 + 1) = 9$ ; e $D_5 = 4(9 + 2) = 44$ .

14. Das $3! = 6$ distribuições, subtraia as que fixam pelo menos um chapéu: três fixam um chapéu dado ( $2!$ cada, $3 \times 2 = 6$ ), o que conta em excesso os pares ( $3$ pares, $1!$ cada), que precisam voltar, e obriga a subtrair de novo a identidade ( $1$ ): $D_3 = 6 - 6 + 3 - 1 = 2$ , isto é, $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$ . Em geral, $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ .

15. $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$ , já próximo de $\frac1\eu \approx 0.3679$ : a soma alternada $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ marcha para $\eu^{-1}$ . Os chapéus de uma festa grande se desarranjam em cerca de $36.8\,\%$ das vezes — a constante da loteria e da secretária, em sua terceira aparição.

16. $\P(\text{válido}) = \frac{D_{10}}{10!} \approx 0.368$ . Cada re-sorteio tem sucesso com probabilidade $\approx \frac1\eu$ , de modo que o número esperado de sorteios é cerca de $\eu \approx 2.7$ : reserve três rodadas de chapéu.

17. Cada aperto de mão contribui com $2$ para a contagem total de apertos por pessoa, de modo que a soma dos números de apertos de todos os convidados é par. Uma soma de inteiros é par apenas se o número de parcelas ímpares for par: quem aperta um número ímpar de mãos vem em quantidade par. (Com três convidados: nenhum perfil possível tem exatamente uma ou três entradas ímpares — confira os quatro grafos possíveis.)

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

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

19. Um caminho até $(n, n)$ dá $2n$ passos e cruza a antidiagonal $x + y = n$ em exatamente um ponto reticulado $(j, n - j)$ ; a primeira metade é um caminho com $j$ passos D entre $n$ passos ( $\binom nj$ escolhas), e a segunda metade, lida de trás para a frente, também ( $\binom nj$ de novo, por simetria). Somando sobre o ponto de cruzamento: $\binom{2n}{n} = \sum_j \binom nj^2$ — a identidade de Vandermonde, desenhada.

20. Multiplicar etapas e somar casos: as placas e as mãos de pôquer. Codificar: caminhos como palavras em D e C, pedidos como estrelas e barras. Contar duas vezes: comissões com presidente, apertos de mão, caminhos cortados ao meio. Subtrair e corrigir: os chapéus desarranjados, com $\frac1\eu$ de resíduo. Próximas paradas: essas contagens sob as frações da probabilidade e o poder de contar caminhos das matrizes de adjacência, dois capítulos adiante.