---
title: "Análise combinatória e contagem"
book: "Matemática do ensino médio"
subject: math
language: pt
chapter: 27
exercises: 10
source: https://one-course.com/books/math/2/pt/chapter/27-analise-combinatoria-e-contagem
---

# Capítulo 27 — Aná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](#def-g12-comb-tuples), as [permutações](#def-g12-comb-permutation) 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](https://one-course.com/books/math/2/pt/chapter/1-numeros-e-conjuntos-numericos#def-g10-numbers-interunion) $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 kkk elementos).**

Uma *[sequência](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) de $k$ elementos de $E$ é $n^k$. O número de [arranjos](#def-g12-comb-tuples) 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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) há $n$ opções em cada um dos $k$ passos; para um [arranjo](#def-g12-comb-tuples), $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](#def-g12-comb-tuples) de todos os $n$ elementos de $E$: uma ordenação de $E$. Pela [Proposição 27.5](#prop-g12-comb-tuples) (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](#def-g12-comb-tuples) 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](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-operations) casa um a um os subconjuntos de $k$ elementos com os de $n-k$ elementos. Para a [relação de Pascal](#prop-g12-comb-identities), 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](#prop-g12-comb-identities) gera os coeficientes linha a linha — o *[triângulo de Pascal](https://one-course.com/books/math/2/pt/chapter/19-a-distribuicao-binomial#prop-g11-binom-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.](https://one-course.com/images/onecourse/chapters/math-2/g12-comb/fig-37a02167c00d.svg)

*O [triângulo de Pascal](https://one-course.com/books/math/2/pt/chapter/19-a-distribuicao-binomial#prop-g11-binom-pascal), linhas $n = 0$ a $5$: a [relação de Pascal](#prop-g12-comb-identities) $\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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence)) | (graduação) |
| sem repetição | $\frac{n!}{(n-k)!}$ ([arranjos](#def-g12-comb-tuples)) | $\binom nk$ (subconjuntos) |

Retirar bolas de uma urna: *com reposição, em ordem* $\to$ [sequências](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence); *sem reposição, em ordem* $\to$ [arranjos](#def-g12-comb-tuples); *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 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 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 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 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.

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

**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](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-operations), $\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 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](#prop-g12-comb-tuples) e contando de duas maneiras os pares (comissão de $k$ pessoas, seu presidente) escolhidos entre $n$ pessoas.

**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 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 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](#exo-g12-comb-7).)

**Solução de Exercício 27.10.**

*Pelo [Exercício 27.7](#exo-g12-comb-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](#cor-g12-comb-sums). *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](#met-g12-comb-model), 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.**

1. Conte as placas formadas por $2$ letras seguidas de $3$ algarismos; depois os anagramas de BANANA.
2. 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.
3. 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.)
4. Expanda $(1 + x)^4$ pelo teorema binomial ( [Teorema 27.11](#thm-g12-comb-binomial) ); depois calcule em $x = 1$ e $x = -1$ : que duas identidades sobre os números $\binom nk$ caem daí?
5. 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.**

6. 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.
7. Conte as ternas de inteiros não negativos com $x + y + z = 12$ .
8. Conte as ternas de inteiros *positivos* com $x + y + z = 12$ (substitua $x = 1 + x'$ etc.).
9. Quantos monômios distintos aparecem na expansão de $(a + b + c)^5$ ?
10. Teste de sanidade do método: conte pela fórmula os pedidos de $3$ bolas com $2$ sabores, depois liste todos e compare.
11. 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](#met-g12-comb-model) .

**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](https://one-course.com/books/math/2/pt/chapter/18-probabilidade-e-variaveis-aleatorias#pb-g11-prob-1) mostrou que, em [média](https://one-course.com/books/math/2/pt/chapter/17-estatistica-descritiva#def-g11-stat-mean), um convidado recupera o próprio chapéu — agora contamos exatamente as festas totalmente azaradas.)

12. Calcule $D_1$ , $D_2$ , $D_3$ listando, e $D_4$ com paciência (ou com esperteza).
13. 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$ .
14. 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.
15. Calcule $\frac{D_5}{5!}$ e compare com $\frac1\eu \approx 0.3679$ : a [probabilidade](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) 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](https://one-course.com/books/math/2/pt/chapter/23-exponencial-e-logaritmo#pb-g12-exp-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.)
16. Amigo secreto entre $10$ amigos: os nomes são sorteados de modo uniforme. Qual é a [probabilidade](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) 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.**

17. 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.
18. 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.)
19. A identidade de Vandermonde ( [Exercício 27.9](#exo-g12-comb-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.
20. 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](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) e os caminhos do capítulo de matrizes e grafos.

**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](https://one-course.com/books/math/2/pt/chapter/19-a-distribuicao-binomial#prop-g11-binom-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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) — outro modelo e outro mundo ([Método 27.13](#met-g12-comb-model): 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](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) $\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](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) e o poder de contar caminhos das matrizes de adjacência, dois capítulos adiante.