---
title: "Contagem"
book: "Matemática universitária — Graduação 1"
subject: math
language: pt
chapter: 2
exercises: 12
source: https://one-course.com/books/math/3/pt/chapter/2-contagem
---

# Capítulo 2 — Contagem

Contar [conjuntos finitos](#def-b1-counting-card) parece elementar — e logo se torna sutil. Este capítulo define a [cardinalidade](#def-b1-counting-card) como se deve (por meio de bijeções, no espírito do [Capítulo 1](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#ch-b1-logic)), estabelece o punhado de princípios de contagem dos quais tudo decorre e deduz as contagens clássicas: listas, permutações, subconjuntos, [coeficientes binomiais](#def-b1-counting-objects).

## 2.1 Cardinalidade dos conjuntos finitos

**Definição 2.1 (Conjunto finito, cardinalidade).**

Para $n \in \N^*$, escreva $\intint{1}{n} = \{1, 2, \dots,
n\}$. Um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $E$ é *finito* quando $E = \emptyset$ ou existe uma bijeção de $\intint{1}{n}$ sobre $E$ para algum $n \in \N^*$; esse $n$ é único ([Teorema 2.2](#thm-b1-counting-welldef)) e é a *cardinalidade* de $E$, escrita $\abs{E}$ (com $\abs{\emptyset} = 0$).

**Teorema 2.2 (A cardinalidade está bem definida).**

Se $m \neq n$, não existe bijeção de $\intint{1}{m}$ sobre $\intint{1}{n}$. Mais precisamente, se $m > n$ não existe injeção de $\intint{1}{m}$ em $\intint{1}{n}$.

**Demonstração.** Demonstramos por indução em $n$ o enunciado: *para todo $m > n$, não existe injeção $\intint{1}{m} \to \intint{1}{n}$*. Para $n = 0$ o contradomínio é vazio e $m \geq 1$: não existe [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) alguma. Suponha o enunciado para $n$ e suponha que $f \colon
\intint{1}{m} \to \intint{1}{n+1}$ seja uma injeção com $m > n + 1$. Se o valor $n + 1$ não é atingido, $f$ é uma injeção em $\intint{1}{n}$, o que contradiz a hipótese de indução. Caso contrário, $f(a) = n + 1$ para exatamente um $a$; troque $f(a)$ e $f(m)$ (formalmente: componha com a transposição dos dois valores), de modo que a nova injeção $g$ tenha $g(m) = n + 1$. Então a restrição de $g$ a $\intint{1}{m-1}$ é uma injeção em $\intint{1}{n}$ com $m - 1 > n$ — contradição, novamente. ∎

**Corolário 2.3 (Princípio da casa dos pombos).**

Se $\abs{E} > \abs{F}$, nenhuma [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) $f \colon E \to F$ é [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj): dois elementos de $E$ partilham a mesma imagem.

**Demonstração.** Escreva $\abs E = m$, $\abs F = n$ com $m > n$ e escolha bijeções $u \colon \intint1m \to E$ e $v \colon F \to \intint1n$. Se $f$ fosse [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj), $v \circ f \circ u$ seria uma injeção de $\intint1m$ em $\intint1n$ (composta de injeções, [Proposição 1.26](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#prop-b1-logic-comp)), contradizendo o [Teorema 2.2](#thm-b1-counting-welldef). ∎

**Observação 2.4 (Interlúdio: por que a troca na demonstração do teorema?).**

A demonstração do [Teorema 2.2](#thm-b1-counting-welldef) contém a primeira jogada genuinamente engenhosa do capítulo, que vale a pena revisitar devagar. O obstáculo: para aplicar a hipótese de indução queremos apagar o último ponto $m$ do domínio *e* o último ponto $n+1$ do contradomínio, mas $f$ pode enviar algum outro ponto $a$ a $n
+ 1$, e então apagar o ponto do contradomínio estraga a [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) em outro lugar. O remédio: compor $f$ com a transposição dos dois *valores* $f(a)$ e $f(m)$ — uma bijeção do contradomínio, de modo que a injetividade se preserva — após o que o valor incômodo $n + 1$ passa a ocupar a posição inofensiva $m$, e as duas remoções ficam limpas. Esse padrão “normalizar primeiro, cortar depois” reaparece: é assim que a recorrência dos desarranjos redireciona $\sigma^{-1}(n+1)$ no problema de fim de semana deste capítulo, e assim que as permutações são remendadas ao longo de todo o problema do [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures) sobre o grupo simétrico.

**Proposição 2.5 (Injeções, sobrejeções e cardinalidade).**

Sejam $E, F$ [conjuntos finitos](#def-b1-counting-card) com $\abs{E} = \abs{F}$, e seja $f \colon E
\to F$. Então

$$
f \text{ injetiva} \iff f \text{ sobrejetiva} \iff f \text{ bijetiva}.
$$

**Demonstração.** Suponha $f$ [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj). Então $f$ é uma bijeção de $E$ sobre $f(E)$, logo $\abs{f(E)} = \abs{E} = \abs{F}$. Se $f(E)$ deixasse de fora um ponto $y_0$ de $F$, então $f$ seria uma injeção de $E$ em $F \setminus \{y_0\}$, [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de [cardinalidade](#def-b1-counting-card) $\abs{F} - 1 < \abs{E}$ — impossível pelo princípio da casa dos pombos. Logo $f(E) = F$: $f$ é [sobrejetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) e, portanto, [bijetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj).

Suponha $f$ [sobrejetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj). Escolha para cada $y \in F$ uma [pré-imagem](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) $s(y)
\in E$; então $f \circ s = \mathrm{id}_F$, de modo que $s$ é [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) ([Proposição 1.26](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#prop-b1-logic-comp)). Pelo parágrafo anterior aplicado a $s$ (as [cardinalidades](#def-b1-counting-card) são iguais), $s$ é [bijetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj). De $f \circ s =
\mathrm{id}_F$ obtemos $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$, logo $f$ é [bijetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj). Por fim, uma [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) [bijetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) é, por definição, ao mesmo tempo [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) e [sobrejetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj), o que fecha o ciclo de implicações. ∎

**Exemplo 2.6 (A finitude é essencial).**

Num [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) *[finito](#def-b1-counting-card)*, a [Proposição 2.5](#prop-b1-counting-injsur) é um atalho poderoso: toda [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) de $E$ em si mesmo é automaticamente uma [permutação](#def-b1-counting-objects) de $E$ — metade da bijetividade vem de graça. As duas implicações desmoronam em [conjuntos](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) infinitos: $n \mapsto n + 1$ é [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) de $\N$ em $\N$, mas não atinge $0$, e a [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) $\N \to \N$ que envia $0 \mapsto 0$ e $n \mapsto n - 1$ para $n \geq 1$ é [sobrejetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj), mas não [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj). Sempre que esta [proposição](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-statement) é invocada, a hipótese de finitude está fazendo trabalho de verdade — tema que o problema de fim de semana do [Capítulo 1](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#ch-b1-logic) explora pelo outro lado, em que os [conjuntos](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) infinitos são precisamente os que admitem tais aplicações de si em si.

**Exemplo 2.7 (Metade do trabalho, de graça).**

Considere a [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) $f$ em $\{0, 1, \dots, 6\}$ que envia $k$ ao resto da divisão de $3k$ por $7$; sua tabela de valores é

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

$f$ é uma bijeção? A injetividade sozinha basta ([Proposição 2.5](#prop-b1-counting-injsur)): se $3k$ e $3k'$ têm o mesmo resto, $7$ divide $3(k - k')$ e, como $7$ é primo e não divide $3$, ele divide $k - k'$ (lema de Euclides, usado aqui no nível do ensino médio e demonstrado no [Capítulo 6](https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros#ch-b1-arith)); com $\abs{k - k'} \leq 6$ isso força $k = k'$. A sobrejetividade vem de graça — não é preciso resolver $3k \equiv c$ para cada $c$, embora a tabela confirme que todo valor aparece exatamente uma vez. O atalho é um cavalo de batalha: demonstra a invertibilidade da multiplicação modular ([Capítulo 6](https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros#ch-b1-arith)), alimenta o emparelhamento do teorema de Wilson e reaparece em álgebra linear como “um endomorfismo de um espaço de dimensão finita é [injetivo](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) se, e somente se, é [sobrejetivo](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj)” ([Capítulo 19](https://one-course.com/books/math/3/pt/chapter/19-dimensao-finita#ch-b1-findim)).

## 2.2 Os princípios de contagem

**Proposição 2.8 (Regras da soma e do produto).**

Sejam $E, F$ [conjuntos finitos](#def-b1-counting-card).

1. Se $E \cap F = \emptyset$ , então $\abs{E \cup F} = \abs{E} +  \abs{F}$ ; mais geralmente, para uma [partição](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#thm-b1-logic-partition) de $E$ em peças $E_1, \dots, E_k$ , $\abs{E} = \sum_i \abs{E_i}$ .
2. Em geral, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap  F}$ .
3. $\abs{E \times F} = \abs{E} \times \abs{F}$ .
4. O [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $F^E$ de todas as aplicações de $E$ em $F$ satisfaz $\abs{F^E} = \abs{F}^{\abs{E}}$ .
5. $\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

**Demonstração.** (1) Concatene enumerações: se $E = \{x_1, \dots, x_m\}$ e $F =
\{y_1, \dots, y_n\}$ sem repetição, então $x_1, \dots, x_m, y_1,
\dots, y_n$ enumera $E \cup F$ sem repetição (por serem disjuntos). A indução estende isso a $k$ peças.

(2) $E \cup F$ é a união disjunta de $E$ e $F \setminus E$, e $F$ é a união disjunta de $F \cap E$ e $F \setminus E$; logo $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} -
\abs{E \cap F}$.

(3) $E \times F$ é a união disjunta, sobre $x \in E$, dos [conjuntos](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $\{x\} \times F$, cada um de [cardinalidade](#def-b1-counting-card) $\abs{F}$; aplique (1).

(4) Uma [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) de $E = \{x_1, \dots, x_m\}$ em $F$ é exatamente a escolha da $m$-upla $(f(x_1), \dots, f(x_m)) \in F^m$; essa correspondência é uma bijeção, e $\abs{F^m} = \abs{F}^m$ por (3) e indução.

(5) Os subconjuntos de $E$ correspondem bijetivamente às aplicações $E \to \{0, 1\}$ (envie $A$ à sua função indicadora); aplique (4). ∎

**Exemplo 2.9 (Contagem pelo complementar).**

Quantas senhas de $4$ dígitos (algarismos de $0$ a $9$, a ordem importa, repetições permitidas) contêm *pelo menos um* algarismo repetido? Contá-las diretamente significa manejar os casos “exatamente um par, dois pares, uma trinca, uma quadra” — cinco configurações que se sobrepõem. Conte antes o complementar: as senhas em geral somam $10^4 = 10\,000$ (regra do produto) e as senhas com quatro algarismos distintos somam $10 \times 9 \times 8 \times 7 = 5\,040$ ($4$-arranjos), de modo que a resposta é

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

Quase metade de todas as senhas repete um algarismo. A ideia: sempre que uma contagem é formulada com “pelo menos” ou “nem todos”, tente primeiro o complementar — a regra da soma garante que $\abs{A} = \abs{E} - \abs{\overline A}$, e o complementar é muitas vezes uma única configuração limpa.

**Exemplo 2.10 (Caminhos na grade).**

Conte os caminhos mínimos do canto $(0,0)$ ao canto $(4, 3)$ de uma grade, movendo-se apenas um passo para a direita (D) ou um passo para cima (C) de cada vez. Todo caminho desses tem exatamente $7$ passos, dos quais $4$ são D e $3$ são C; reciprocamente, qualquer palavra de comprimento $7$ nas letras D, C com quatro D descreve exatamente um caminho. Os caminhos correspondem, portanto, bijetivamente às escolhas das posições dos D:

$$
\binom{7}{4} = 35 .
$$

A ideia é a *codificação*: a contagem tornou-se trivial no momento em que cada caminho foi traduzido em uma palavra, isto é, em um subconjunto de posições — mais uma instância do lema de que uma contagem correta é uma bijeção disfarçada ([Método 2.19](#met-b1-counting-which)).

![Um dos 74 = 35 caminhos mínimos de (0,0) a (4,3): o caminho mostrado codifica a palavra DCDDCDC, isto é, a escolha das posições \1,3,4,6\ para a letra D entre os sete passos.](https://one-course.com/images/onecourse/chapters/math-3/b1-counting/fig-9d38fb7e142a.svg)

*Um dos $\binom74 = 35$ caminhos mínimos de $(0,0)$ a $(4,3)$: o caminho mostrado codifica a palavra DCDDCDC, isto é, a escolha das posições $\{1,3,4,6\}$ para a letra D entre os sete passos.*

## 2.3 Listas, permutações, subconjuntos

**Definição 2.11 (Arranjos, permutações, combinações).**

Seja $E$ um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) com $\abs{E} = n$ e seja $0 \leq k \leq n$.

- Um *$k$-arranjo* de $E$ é uma $k$ -upla [injetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) de elementos de $E$ (uma seleção ordenada sem repetição);
- uma *permutação* de $E$ é uma bijeção de $E$ em si mesmo — equivalentemente, um $n$ -arranjo;
- uma *$k$-combinação* é um subconjunto de $E$ com $k$ elementos (uma seleção não ordenada e sem repetição). O seu número escreve-se $\binom{n}{k}$ , lido “combinações de $n$ , $k$ a $k$ ” .

**Teorema 2.12 (As três contagens).**

Com $n = \abs{E}$ e $0 \leq k \leq n$:

1. o número de $k$ -arranjos de $E$ é $n (n-1) \cdots  (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
2. o número de permutações de $E$ é $n!$ ;
3. $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

**Demonstração.** (1) Escolha a primeira coordenada ($n$ modos), depois a segunda ($n - 1$ escolhas restantes), …, depois a $k$-ésima ($n - k + 1$ escolhas). Formalmente, faça indução em $k$. Para $k = 1$ há $n$ uplas [injetivas](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) de um só termo. Suponha a contagem para $k - 1$. Cada $k$-arranjo $(x_1, \dots, x_k)$ é obtido de exatamente um $(k-1)$-arranjo — o seu truncamento $(x_1, \dots, x_{k-1})$ — acrescentando uma última coordenada fora de $\{x_1, \dots,
x_{k-1}\}$, para a qual há exatamente $n - (k - 1)$ valores disponíveis. Os $k$-arranjos ficam assim repartidos, pelo truncamento, em classes de tamanho comum $n - k + 1$ indexadas pelos $(k-1)$-arranjos, e a regra da soma dá

$$
\frac{n!}{(n-k+1)!}\;(n - k + 1) = \frac{n!}{(n-k)!} .
$$

(2) é (1) com $k = n$.

(3) Cada $k$-subconjunto se ordena de $k!$ modos distintos, dando $k$-arranjos distintos, e todo $k$-arranjo provém de exatamente um subconjunto: logo $\frac{n!}{(n-k)!} = \binom nk \cdot k!$. ∎

**Exemplo 2.13 (Mesas redondas: quocientar pela simetria).**

De quantos modos $n$ convidados podem se sentar em torno de uma mesa redonda, sendo duas disposições idênticas quando cada convidado tem os mesmos vizinhos à esquerda e à direita — isto é, a menos de rotação? Cada disposição circular corresponde a exatamente $n$ disposições lineares (corte o círculo em qualquer dos $n$ lugares), de modo que as $n!$ ordens lineares se agrupam de $n$ em $n$:

$$
\frac{n!}{n} = (n-1)! \quad\text{disposições circulares.}
$$

Equivalentemente: sente um convidado distinguido em qualquer lugar (matando a liberdade de rotação) e depois ordene os $n - 1$ convidados restantes no sentido horário. Para $n = 6$: $120$ mesas. As duas soluções ilustram os dois remédios usuais para a contagem excessiva: dividir pelo número exato de repetições ou *quebrar a simetria* fixando um objeto. Ambos exigem que o grupo de repetições tenha o mesmo tamanho em toda configuração — o que a demonstração da fórmula $\binom nk = \frac{n!}{k!\,(n-k)!}$ acima também usou, com $k!$ no lugar de $n$.

**Exemplo 2.14 (Acrescentando uma restrição).**

Continuando com a mesa redonda: entre as $(n-1)!$ mesas de $n \geq
3$ convidados, quantas mantêm dois convidados dados $A$ e $B$ *separados* (não adjacentes)? Conte o complementar. Mesas em que $A$ e $B$ se sentam juntos: cole-os num único bloco — $n - 1$ objetos em torno da mesa, isto é, $(n-2)!$ disposições circulares — e depois ordene o par dentro do bloco ($2$ modos): $2\,(n-2)!$ mesas com adjacência. Portanto

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

mesas os mantêm separados. Verificações de sanidade: $n = 3$ dá $0$ (em torno de um triângulo, todos se tocam) e $n = 4$ dá $2$, facilmente listadas à mão. O truque da colagem — tratar um bloco forçado como um único objeto e depois contar suas disposições internas — é o remédio usual para restrições de adjacência, lineares ou circulares.

**Proposição 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 .
$$

**Demonstração.** Primeira identidade: $A \mapsto E \setminus A$ é uma bijeção entre os $k$-subconjuntos e os $(n-k)$-subconjuntos. Regra de Pascal: fixe um elemento $a \in E$; os $k$-subconjuntos se repartem entre os que contêm $a$ (escolha os $k - 1$ restantes: $\binom{n-1}{k-1}$) e os que evitam $a$ ($\binom{n-1}{k}$). Terceira identidade: os dois lados contam todos os subconjuntos de $E$, à esquerda separados por tamanho ([Proposição 2.8](#prop-b1-counting-rules) (1) e (5)). ∎

**Teorema 2.16 (Teorema binomial).**

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

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

**Demonstração.** Expandir $(a+b)(a+b)\cdots(a+b)$ distributivamente produz um termo por escolha, em cada fator, de $a$ ou de $b$: o termo $a^k b^{n-k}$ aparece uma vez para cada modo de escolher quais $k$ dos $n$ fatores contribuem com $a$ — isto é, $\binom nk$ vezes. (Alternativamente: faça indução em $n$ usando a regra de Pascal.) ∎

**Exemplo 2.17.**

Duas especializações clássicas: $a = b = 1$ recupera $\sum_k \binom nk
= 2^n$; $a = -1$, $b = 1$ dá $\sum_{k} (-1)^k \binom nk = 0$ para $n \geq 1$: entre os subconjuntos de um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) não vazio, exatamente metade tem [cardinalidade](#def-b1-counting-card) par.

**Exemplo 2.18 (Uma identidade, duas demonstrações).**

A especialização $a = 2$, $b = 1$ do teorema binomial diz que

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

Eis a mesma identidade sem álgebra nenhuma. O lado direito conta as palavras de comprimento $n$ sobre o alfabeto $\{0, 1, 2\}$ (regra do produto). Classifique cada palavra pelo [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $K$ das posições que carregam uma letra não nula: escolher $K$ com $\abs K = k$ custa $\binom nk$, e depois cada posição de $K$ carrega, independentemente, $1$ ou $2$: $2^k$ modos. A regra da soma sobre $k$ dá o lado esquerdo. Além do prazer da concordância, as duas demonstrações têm virtudes diferentes: a algébrica se generaliza a qualquer valor de $a$; a combinatória *explica* a fórmula e se adapta a restrições (proibir a letra $2$ na última posição, digamos) que substituição alguma capta. Manter as duas técnicas em atividade é a habilidade prática que este capítulo treina.

**Método 2.19 (Que contagem se aplica?).**

Antes de calcular, responda a duas perguntas sobre a seleção: a *ordem* importa e as *repetições* são permitidas?

|  | a ordem importa | a ordem não importa |
| --- | --- | --- |
| sem repetição | $\dfrac{n!}{(n-k)!}$ | $\dbinom{n}{k}$ |
| [6pt] com repetição | $n^k$ | ([Exercício 2.10](#exo-b1-counting-10)) |

Depois, procure uma bijeção ou uma [partição](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#thm-b1-logic-partition) que reduza o problema a essas contagens modelo; uma contagem correta é uma bijeção disfarçada.

**Observação 2.20 (Armadilhas frequentes em contagem).**

1. *Somar casos não disjuntos.* A regra da soma exige uma [partição](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#thm-b1-logic-partition) ; se configurações podem satisfazer dois casos ao mesmo tempo, elas são contadas duas vezes — o remédio é a inclusão–exclusão ( [Teorema 2.24](#thm-b1-counting-inclexcl) ) ou uma separação de casos mais fina.
2. *Ordenado versus não ordenado.* Escolher “uma comissão de duas pessoas” é $\binom n2$ , e não $n(n-1)$ : decida *antes de calcular* se a seleção carrega uma ordem e, se a contagem ordenada for mais fácil, divida no fim pelo número de ordenações — mas só quando cada objeto não ordenado provier do *mesmo* número de objetos ordenados.
3. *Escolhas em várias etapas que não são independentes.* A regra do produto exige que o número de opções em cada etapa seja independente das escolhas anteriores. “Escolha um capitão e depois um vice-capitão diferente” é legítimo ( $n(n-1)$ ); “escolha dois jogadores que se deem bem” não é de modo algum um produto em duas etapas.
4. *Contagem dupla por construção.* Construir cada objeto duas vezes — por exemplo, contar as mãos com *pelo menos* um ás como (escolher um ás) $\times$ (escolher mais $4$ cartas) — conta em excesso as mãos com dois ases. “Pelo menos” quase sempre pede o complementar ( [Exemplo 2.9](#ex-b1-counting-complement) ).

**Exemplo 2.21 (Uma contagem de pôquer).**

De um baralho de $52$ cartas, o número de mãos de $5$ cartas é $\binom{52}{5} = 2\,598\,960$. Mãos contendo exatamente um ás: escolha o ás ($4$ modos) e depois $4$ cartas entre as $48$ que não são ases: $4 \binom{48}{4} = 778\,320$. A regra do produto se aplica porque a escolha se divide em etapas independentes.

**Método 2.22 (Contagem dupla).**

Para demonstrar uma identidade entre duas expressões de contagem, encontre um único [conjunto finito](#def-b1-counting-card) que ambos os lados contam — tipicamente um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de *pares* — e avalie sua [cardinalidade](#def-b1-counting-card) em duas ordens diferentes. O protótipo é o *lema do aperto de mão*: numa festa, conte os pares (pessoa, mão apertada). Somando sobre as pessoas obtém-se $\sum_p d_p$ (o número de apertos de mão de cada pessoa $p$); somando sobre os apertos obtém-se o dobro do número de apertos (cada um envolve duas pessoas). Portanto $\sum_p d_p$ é par — de modo que o número de pessoas que apertaram um número ímpar de mãos é sempre par, conclusão não trivial obtida sem fórmula alguma. O mesmo motor aciona o [Exercício 2.12](#exo-b1-counting-12) e várias questões do problema de fim de semana abaixo.

**Exemplo 2.23 (O subconjunto médio).**

Qual é a [cardinalidade](#def-b1-counting-card) média de um subconjunto de um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $E$ de $n$ elementos, sendo todos os $2^n$ subconjuntos igualmente prováveis? Conte duas vezes os pares $(A, a)$ com $a \in A$: somando sobre os subconjuntos obtém-se $\sum_A \abs A$, o total que queremos; somando sobre os elementos obtém-se $n \cdot 2^{n-1}$ (cada um dos $n$ elementos está em exatamente metade dos subconjuntos — emparelhe cada $A$ que contém $a$ com $A
\setminus \{a\}$). Portanto

$$
\frac{1}{2^n}\sum_{A \subseteq E} \abs A
= \frac{n\,2^{n-1}}{2^n} = \frac n2 :
$$

os subconjuntos estão, em média, pela metade — como a simetria $A
\leftrightarrow \overline A$ (que emparelha os tamanhos $k$ e $n - k$) também prevê. Duas demonstrações, uma só resposta, e ambas evitam o cálculo direto $\sum_k k\binom nk$ do [Exercício 2.5](#exo-b1-counting-5): um emparelhamento bem escolhido substitui muitas vezes uma identidade.

## 2.4 Inclusão–exclusão

**Teorema 2.24 (Inclusão–exclusão).**

Para [conjuntos finitos](#def-b1-counting-card) $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}$.

**Demonstração.** Fixe um elemento $x$ da união e conte a sua contribuição ao lado direito. Seja $J = \{i : x \in A_i\}$, de [cardinalidade](#def-b1-counting-card) $m \geq
1$. O elemento $x$ é contado uma vez em $\abs{\bigcap_{i \in I} A_i}$ exatamente quando $\emptyset \neq I \subseteq J$, com sinal $(-1)^{\abs I + 1}$; sua contribuição total é

$$
\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1}
= 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1
$$

pelo [Exemplo 2.17](#ex-b1-counting-binomial). Assim, cada elemento da união é contado exatamente uma vez. ∎

**Exemplo 2.25 (Contando os inteiros coprimos).**

Quantos inteiros de $\intint1{120}$ são coprimos com $120 = 2^3
\times 3 \times 5$? Um inteiro tem um fator comum com $120$ exatamente quando é divisível por $2$, $3$ ou $5$; conte então o complementar de $A_2 \cup A_3 \cup A_5$, em que $A_d$ reúne os múltiplos de $d$. Dentro de $\intint1{120}$, os múltiplos de $d$ somam $120/d$ sempre que $d$ divide $120$ — sem necessidade de partes inteiras — e $A_2 \cap A_3 = A_6$, etc. Inclusão–exclusão:

$$
\abs{A_2 \cup A_3 \cup A_5}
= 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,
$$

de modo que $120 - 88 = 32$ inteiros são coprimos com $120$. É instrutivo reagrupar o cálculo como um produto:

$$
120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 -
\frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot
\frac23 \cdot \frac45 = 32 :
$$

expandir os três parênteses reproduz exatamente os oito termos com sinal da inclusão–exclusão, um por subconjunto de $\{2, 3,
5\}$. Essa forma de produto define a função totiente de Euler, cujo papel aritmético aparece com as congruências do [Capítulo 6](https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros#ch-b1-arith) e é desenvolvido no volume do segundo ano de graduação.

**Exemplo 2.26 (Desarranjos).**

Um *desarranjo* é uma [permutação](#def-b1-counting-objects) sem ponto fixo. Seja $A_i$ o [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) das permutações de $\intint{1}{n}$ que fixam $i$; então $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$, e a inclusão–exclusão conta as permutações com pelo menos um ponto fixo; os desarranjos somam

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

Como $\sum (-1)^k / k! \to \eu^{-1}$ (veja o [Capítulo 17](https://one-course.com/books/math/3/pt/chapter/17-series-numericas#ch-b1-series)), cerca de $37\%$ de todas as permutações são desarranjos, seja qual for $n$.

**Observação 2.27 (Onde este capítulo é usado).**

Os [coeficientes binomiais](#def-b1-counting-objects) são os objetos deste capítulo mais reutilizados: eles conduzem o teorema binomial no [Capítulo 8](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly) (expansão de $(X + a)^n$), a fórmula de Leibniz para a $n$-ésima derivada de um produto no [Capítulo 14](https://one-course.com/books/math/3/pt/chapter/14-derivacao#ch-b1-derivative) e os coeficientes das expansões de Taylor no [Capítulo 16](https://one-course.com/books/math/3/pt/chapter/16-formulas-de-taylor-e-expansoes-assintoticas#ch-b1-taylor). As permutações voltam como um grupo — com o sinal construído a partir da contagem das inversões — no [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures), e o sinal, por sua vez, define os determinantes no [Capítulo 22](https://one-course.com/books/math/3/pt/chapter/22-determinantes-e-sistemas-lineares#ch-b1-det). A inclusão–exclusão e os princípios de contagem são a espinha dorsal finita da probabilidade discreta, desenvolvida no volume do segundo ano de graduação; os números de desarranjos do [Exemplo 2.26](#ex-b1-counting-derangement) são estudados a fundo no problema de fim de semana abaixo.

## 2.5 Exercícios

**Exercício 2.1 ★.**

Uma placa de veículo é formada por duas letras (A–Z), depois três algarismos e depois duas letras. Quantas placas são possíveis? E quantas sem letra repetida entre as quatro?

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

Etapas independentes e regra do produto: $26^2 \times 10^3 \times 26^2
= 26^4 \times 1000 = 456\,976\,000$ placas. Com as quatro letras duas a duas distintas, as etapas das letras formam um $4$-arranjo do alfabeto: $26 \times 25 \times 24 \times 23 = 358\,800$ modos, logo $358\,800 \times 1000 = 358\,800\,000$ placas.

**Exercício 2.2 ★.**

Quantos anagramas (rearranjos das letras, com ou sem sentido) tem a palavra orange ? E banana ?

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

orange tem $6$ letras distintas: $6! = 720$ anagramas. banana tem $6$ letras com repetições ($3$ letras a, $2$ letras n, $1$ letra b): cada anagrama fica determinado pelas posições dos a ($\binom 63$ escolhas), depois dos n entre os $3$ lugares restantes ($\binom 32$), ficando o b com o último lugar: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ anagramas (equivalentemente, $6!/(3!\,2!\,1!) = 60$).

**Exercício 2.3 ★.**

Uma comissão de $4$ pessoas é escolhida entre $7$ mulheres e $5$ homens. Quantas comissões há: no total? com exatamente $2$ mulheres? com pelo menos um homem?

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

Total: $\binom{12}{4} = 495$. Exatamente $2$ mulheres: escolha-as ($\binom 72 = 21$) e $2$ homens ($\binom 52 = 10$): $210$ comissões. Pelo menos um homem: complementar de “nenhum homem”, $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$.

**Exercício 2.4 ★.**

Demonstre que, em qualquer grupo de $13$ pessoas, duas fazem aniversário no mesmo mês; e que, entre quaisquer $n + 1$ inteiros escolhidos em $\intint{1}{2n}$, dois são consecutivos. *(Casa dos pombos nas duas vezes: nomeie as casas.)*

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

*Aniversários:* as casas são os $12$ meses; $13$ pessoas em $12$ casas forçam duas na mesma casa ([Corolário 2.3](#cor-b1-counting-pigeonhole)).

*Inteiros consecutivos:* as casas são os $n$ pares $\{1,2\},
\{3,4\}, \dots, \{2n-1, 2n\}$, que formam uma [partição](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#thm-b1-logic-partition) de $\intint{1}{2n}$. Escolher $n + 1$ inteiros coloca dois no mesmo par, e os dois elementos de um par são consecutivos.

**Exercício 2.5 ★.**

Calcule $\sum_{k=0}^{n} k \binom{n}{k}$. *Sugestão: derive $(1 + x)^n$, ou use $k \binom nk = n \binom{n-1}{k-1}$ (demonstre esta igualdade).*

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

Somando e reindexando com $j = k - 1$:

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

pela [Proposição 2.15](#prop-b1-counting-identities). (Alternativa: derive $(1+x)^n = \sum_k \binom nk x^k$ e faça $x = 1$.)

**Exercício 2.6 ★★.**

Quantas aplicações estritamente crescentes existem de $\intint{1}{k}$ em $\intint{1}{n}$? Deduza o número de aplicações crescentes (não necessariamente estritamente). *Sugestão para a segunda contagem: $f$ crescente $\mapsto$ $g(i) = f(i) + i - 1$.*

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

Uma [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) estritamente crescente $f \colon \intint{1}{k} \to \intint{1}{n}$ fica determinada por sua imagem, um $k$-subconjunto de $\intint{1}{n}$ (liste o subconjunto em ordem crescente); reciprocamente, todo $k$-subconjunto dá exatamente uma [aplicação](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) desse tipo. Portanto, há $\binom nk$ aplicações estritamente crescentes.

Se $f$ é apenas crescente, ponha $g(i) = f(i) + i - 1$. Então $g$ é estritamente crescente (entre argumentos consecutivos, $f$ ganha $\geq 0$ e $i - 1$ ganha $1$), com valores em $\intint{1}{n + k - 1}$; e $f(i) = g(i) - i + 1$ recupera $f$ a partir de qualquer $g$ estritamente crescente em $\intint{1}{n+k-1}$. Isso é uma bijeção, de modo que há $\binom{n + k - 1}{k}$ aplicações crescentes.

**Exercício 2.7 ★★.**

(Vandermonde) Demonstre, contando os $k$-subconjuntos de um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) repartido em dois blocos de tamanhos $m$ e $n$:

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

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

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

Reparta um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) $E$ com $m + n$ elementos em blocos $M$ ($m$ elementos) e $N$ ($n$ elementos). Um $k$-subconjunto de $E$ contém certos $j$ elementos de $M$ ($0 \leq j \leq k$) e $k - j$ de $N$; para $j$ fixado há $\binom mj \binom{n}{k-j}$ subconjuntos desses, e os casos $j = 0, \dots,
k$ repartem os $k$-subconjuntos. A regra da soma 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 $\binom{n}{n-j} =
\binom nj$.

**Exercício 2.8 ★★.**

Quantos inteiros de $\intint{1}{1000}$ são divisíveis por $2$, por $3$ ou por $5$? (Inclusão–exclusão; $\lfloor 1000/6 \rfloor$ conta os múltiplos de $6$, etc.)

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

Seja $A_d$ o [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) dos múltiplos de $d$ em $\intint{1}{1000}$, de modo que $\abs{A_d} = \lfloor 1000/d \rfloor$. Inclusão–exclusão ([Teorema 2.24](#thm-b1-counting-inclexcl)) com $A_2, A_3, A_5$, notando que $A_2 \cap A_3 = A_6$, etc.:

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

Logo $734$ inteiros são divisíveis por $2$, $3$ ou $5$.

**Exercício 2.9 ★★.**

Conte as sobrejeções de um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de $4$ elementos sobre um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de $2$ elementos; depois sobre um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de $3$ elementos. *Sugestão: conte as aplicações não [sobrejetivas](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj) com inclusão–exclusão sobre os valores não atingidos.*

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

Sobre $2$ elementos: todas as $2^4 = 16$ aplicações, exceto as $2$ constantes: $14$ sobrejeções.

Sobre $3$ elementos: por inclusão–exclusão sobre os valores não atingidos, o número de aplicações de um [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de $4$ elementos num de $3$ que deixam de fora pelo menos um valor é $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$; total de aplicações: $3^4 =
81$; sobrejeções: $81 - 45 = 36$. (Verificação: uma sobrejeção de $4$ sobre $3$ elementos duplica exatamente um valor: escolha o valor duplicado ($3$), o par que é enviado a ele ($\binom 42 = 6$) e uma bijeção para o resto ($2$): $3 \times 6 \times 2 = 36$.)

**Exercício 2.10 ★★.**

(Estrelas e barras) Demonstre que o número de $k$-seleções de $n$ objetos *com* repetição, ignorando a ordem — equivalentemente, o número de $(x_1, \dots, x_n) \in \N^n$ com $x_1 + \dots + x_n = k$ — é $\binom{n + k - 1}{k}$. *Sugestão: codifique uma solução como uma fila de $k$ estrelas e $n - 1$ barras.*

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

Uma solução de $x_1 + \dots + x_n = k$ em $\N^n$ codifica-se como uma fila de $k$ estrelas e $n - 1$ barras: escreva $x_1$ estrelas, uma barra, $x_2$ estrelas, uma barra, …, terminando com $x_n$ estrelas. Isso é uma bijeção sobre as palavras de comprimento $k + n - 1$ com $k$ estrelas e $n - 1$ barras, e essas palavras ficam determinadas pelas posições das estrelas: $\binom{n + k - 1}{k}$. As seleções com repetição correspondem a soluções da equação ($x_i$ = número de cópias do objeto $i$), de modo que a contagem é a mesma.

**Exercício 2.11 ★★★.**

Demonstre em detalhe a fórmula do [Exemplo 2.26](#ex-b1-counting-derangement) para $D_n$ e deduza que $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (demonstre também esta identidade diretamente, classificando as permutações pelo seu [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de pontos fixos).

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

Com $A_i = \{\sigma : \sigma(i) = i\}$, uma [permutação](#def-b1-counting-objects) de $\bigcap_{i \in I} A_i$ fixa todo $i \in I$ e permuta livremente os outros $n - \abs I$ pontos: $\abs{\bigcap_{i \in I} A_i} =
(n - \abs I)!$. Inclusão–exclusão:

$$
\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!} ,
$$

pois há $\binom nk$ subconjuntos $I$ de tamanho $k$. Portanto

$$
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 a segunda identidade: classifique as permutações $\sigma$ de $\intint{1}{n}$ pelo seu [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de pontos fixos $F(\sigma)$. Para um $k$-subconjunto $F$ fixado, as permutações com $F(\sigma) = F$ são exatamente os desarranjos do complementar: $D_{n-k}$ delas. Somando sobre as $\binom nk$ escolhas de $F$ para cada $k$: $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$.

**Exercício 2.12 ★★★.**

Para $n \in \N^*$, demonstre por uma contagem dupla de pares (subconjunto, elemento marcado):

$$
\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1},
\qquad\text{então}\qquad
\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .
$$

*Para a segunda: conte pares de elementos marcados, iguais ou não.*

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

*Primeira identidade.* Conte os pares $(A, a)$ com $A \subseteq E$ ($\abs E = n$) e $a \in A$. Pelo tamanho de $A$: $\sum_k \binom nk k$ pares. Escolhendo primeiro o elemento marcado: $n$ escolhas para $a$ e depois um subconjunto qualquer dos $n - 1$ elementos restantes para completar $A$: $n\,2^{n-1}$ pares.

*Segunda identidade.* Conte as triplas $(A, a, b)$ com $a, b \in
A$ (podendo ser $a = b$). Pelo tamanho: $\sum_k k^2 \binom nk$. Diretamente: ou $a = b$ ($n\,2^{n-1}$ triplas, contagem anterior), ou $a \neq b$ ($n(n-1)$ escolhas ordenadas e depois um subconjunto qualquer dos outros $n - 2$ elementos: $n(n-1)\,2^{n-2}$). 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: Desarranjos, ou as cartas trocadas

**Problema 2.1.**

Uma secretária coloca $n$ cartas em $n$ envelopes endereçados ao acaso: qual é a chance de que *ninguém* receba a carta certa? Esta questão clássica (Montmort, 1708) leva aos números de desarranjos $D_n$ do [Exemplo 2.26](#ex-b1-counting-derangement). A fórmula de inclusão–exclusão é apenas a jogada de abertura: este problema desenvolve as recorrências que calculam $D_n$, duas outras demonstrações independentes da fórmula, o notável teorema de que $D_n$ é o inteiro mais próximo de $n!/\eu$, a distribuição completa dos pontos fixos de uma [permutação](#def-b1-counting-objects) aleatória e a curiosa aritmética da sequência $(D_n)$. Ao longo do problema, $D_n$ denota o número de desarranjos (permutações sem pontos fixos) de $\intint1n$, com a convenção $D_0 = 1$ (a [permutação](#def-b1-counting-objects) vazia não tem ponto fixo).

**Parte I — Casos pequenos e o censo dos pontos fixos.**

1. Calcule $D_1, D_2, D_3$ diretamente, e $D_4$ listando os desarranjos de $\{1, 2, 3, 4\}$ agrupados pelo valor de $\sigma(1)$ . (Você deve encontrar $D_4 = 9$ .)
2. Para $0 \leq k \leq n$ , mostre que o número $P_k(n)$ de permutações de $\intint1n$ com *exatamente* $k$ pontos fixos é $\binom nk D_{n-k}$ .
3. Verifique o censo para $n = 4$ : calcule $P_0(4), \dots,  P_4(4)$ e confira que a soma é $4! = 24$ . O que é mais provável com quatro cartas: nenhum acerto ou exatamente um?
4. Por contagem dupla ([Método 2.22](#met-b1-counting-doublecount)) dos pares $(\sigma, i)$ com $\sigma(i) = i$, mostre que $$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$$ em média, uma [permutação](#def-b1-counting-objects) aleatória tem *exatamente um* ponto fixo, seja qual for $n \geq 1$.

**Parte II — Duas recorrências e duas novas demonstrações da fórmula.**

1. Demonstre combinatoriamente, para $n \geq 1$: $$D_{n+1} = n\,(D_n + D_{n-1}) .$$ (Classifique os desarranjos $\sigma$ de $\intint1{n+1}$ por $j = \sigma(n+1)$ e depois conforme $\sigma(j) = n + 1$ ou não; no caso $\sigma(j) \neq n+1$, construa uma bijeção com os desarranjos de $\intint1n$ redirecionando a [pré-imagem](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) de $n + 1$ para $j$.) Verifique a recorrência numericamente até $D_6$.
2. Pondo $u_n = D_n - n D_{n-1}$, deduza da questão 5 que $u_{n+1} = -u_n$, e conclua a segunda recorrência: $$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$$
3. A partir da questão 6, demonstre por indução a fórmula do [Exemplo 2.26](#ex-b1-counting-derangement), $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$$ — demonstração inteiramente independente da inclusão–exclusão.
4. (Inversão binomial) Sejam $(a_n)$ e $(b_n)$ duas sequências tais que $a_n = \sum_{k=0}^n \binom nk b_k$ para todo $n$. Demonstre que $$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k  \qquad (n \in \N).$$ (Estabeleça primeiro a *revisão trinomial* $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$, e depois use a soma alternada de uma linha do [Exemplo 2.17](#ex-b1-counting-binomial).)
5. Aplique a questão 8 à identidade $n! = \sum_k \binom nk  D_{n-k}$ do [Exercício 2.11](#exo-b1-counting-11) para obter uma *terceira* demonstração da fórmula de $D_n$ .

**Parte III — O inteiro mais próximo de $n!/\eu$.** Admita nesta parte — a teoria é construída no [Capítulo 17](https://one-course.com/books/math/3/pt/chapter/17-series-numericas#ch-b1-series) — que $\eu^{-1} = \lim_{n \to \infty} s_n$, em que $s_n = \sum_{k=0}^{n}
\frac{(-1)^k}{k!}$, com a estimativa estrita das séries alternadas $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ para todo $n$.

1. Mostre que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ para todo $n \in \N$ .
2. Deduza o teorema central: *para todo $n \geq 1$, $D_n$ é o inteiro mais próximo de $n!/\eu$* . Por que o argumento precisa de $n \geq 1$ ?
3. Determine o sinal do erro: mostre que $D_n > n!/\eu$ exatamente quando $n$ é par. (Localize o primeiro termo desprezado da série alternada.)
4. Calcule $D_7$ até $D_{10}$ com a recorrência da questão 5 e depois confira $D_{10}$ contra $10!/\eu$ ( $10! = 3\,628\,800$ , $\eu \approx 2.718281828$ ).
5. (A probabilidade do chapeleiro) Seja $p_n = D_n/n!$ a probabilidade de que uma [permutação](#def-b1-counting-objects) uniformemente aleatória seja um desarranjo. Mostre que $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ e calcule $p_6$ com cinco casas decimais. Comente: por que a resposta à questão de Montmort é essencialmente independente de $n$ — já para uma dúzia de cartas?

**Parte IV — A distribuição dos pontos fixos.**

1. Fixe $k \in \N$. Mostre que a proporção das permutações de $\intint1n$ com exatamente $k$ pontos fixos satisfaz $$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!}  \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$$ (Esses valores-limite, cuja soma é $1$, formam a *distribuição de Poisson* de parâmetro $1$, objeto central do curso de probabilidade do volume do segundo ano de graduação.)
2. Por contagem dupla das triplas $(\sigma, i, j)$ , em que $i  \neq j$ são ambos fixados por $\sigma$ , mostre que $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\,  (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ para $n \geq 2$ . Combinado com a questão 4: a média de $\abs{\mathrm{Fix}}^2$ é $2$ , de modo que a “dispersão” (variância) do número de pontos fixos vale $1$ — de novo independentemente de $n$ , de novo em acordo com a lei de Poisson.
3. Calcule a proporção das permutações que têm pelo menos um ponto fixo para $n = 4, 5, 6$ (em frações e com quatro casas decimais) e compare com $1 - \eu^{-1} \approx  0.6321$ .
4. Mostre diretamente — sem precisar de limites — que $s_{n+2} - s_n  = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , e deduza que as probabilidades $p_n = s_n$ da questão 14 oscilam: $p_0 > p_2 > p_4 > \dots$ e $p_1 < p_3 < p_5 < \dots$ , os valores pares (resp. ímpares) decrescendo (resp. crescendo) rumo ao limite comum $\eu^{-1}$ .
5. (Amigo oculto) $n$ pessoas tiram, cada uma, um nome de um chapéu; se alguém tira o próprio nome, o sorteio *inteiro* é reiniciado do zero. Usando o fato usual de que um evento de probabilidade $p$ exige em média $1/p$ tentativas, estime o número médio de sorteios completos necessários e conclua que o procedimento custa cerca de $\eu \approx  2.72$ sorteios em média, essencialmente de modo independente de $n$ .

**Parte V — A aritmética de $D_n$, e uma síntese.**

1. Refine a questão 5: mostre que, para $j \in  \intint2n$ fixado, os desarranjos de $\intint1n$ com $\sigma(1) = j$ somam exatamente $D_{n-1} + D_{n-2}$ , independentemente de $j$ . Deduza que $n - 1$ divide $D_n$ para todo $n \geq 2$ .
2. Demonstre que $D_n$ é ímpar se, e somente se, $n$ é par. (Trabalhe módulo $2$ na recorrência da questão 6.)
3. Demonstre que $D_n \equiv (-1)^n \pmod n$ para $n \geq 1$ e confira a congruência no último algarismo de $D_{10}$ .
4. Mostre, a partir da questão 6, que $\dfrac{D_n}{D_{n-1}} = n +  \dfrac{(-1)^n}{D_{n-1}}$ para $n \geq 3$ , de modo que a razão entre números de desarranjos consecutivos é *quase exatamente* $n$ ; explique em uma frase por que isso é coerente com $D_n \approx n!/\eu$ .
5. Onde exatamente este problema usou: (i) as regras do produto e da soma; (ii) a contagem dupla; (iii) o teorema binomial; (iv) a estimativa admitida das séries alternadas? Uma frase para cada.
6. Síntese. A fórmula de $D_n$ tem agora três demonstrações (inclusão–exclusão, recorrência mais indução, inversão binomial). Num parágrafo curto, compare o que cada demonstração *explica* : qual delas calcula mais rápido, qual se generaliza a outras contagens de pontos fixos e qual revela por que $\eu$ aparece num problema sobre envelopes.

**Solução de Problema 2.1.**

**1.** $D_1 = 0$ (a única [permutação](#def-b1-counting-objects) fixa $1$), $D_2 = 1$ (a troca), $D_3 = 2$ (em notação de uma linha: $231$ e $312$). Para $n = 4$, agrupe por $\sigma(1)$: com $\sigma(1) = 2$ os desarranjos são $2143$, $2341$, $2413$; com $\sigma(1) = 3$: $3142$, $3412$, $3421$; com $\sigma(1) = 4$: $4123$, $4312$, $4321$. Três em cada grupo: $D_4 = 9$.

**2.** Uma [permutação](#def-b1-counting-objects) com exatamente $k$ pontos fixos fica determinada pela escolha do seu [conjunto](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de pontos fixos $F$ ($\binom nk$ modos) junto com a sua restrição ao complementar, que deve ser uma [permutação](#def-b1-counting-objects) de $n - k$ pontos *sem* ponto fixo ($D_{n-k}$ modos). As duas escolhas são independentes e a correspondência é [bijetiva](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-inj): $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$ (três pontos fixos forçam um quarto); $P_4(4) = 1$. Soma: $9 + 8 + 6
+ 0 + 1 = 24 = 4!$. Nenhum acerto ($9$ casos) supera exatamente um acerto ($8$ casos) — por pouco.

**4.** Conte os pares $(\sigma, i)$ com $\sigma(i) = i$. Para $i$ fixado, as permutações que fixam $i$ são as permutações dos outros $n - 1$ pontos: $(n-1)!$ delas. Portanto, o número de pares é $n \cdot (n-1)! = n!$, e esse número é também $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$. Dividindo pelo número $n!$ de permutações: o número médio de pontos fixos é exatamente $1$, para todo $n \geq 1$.

**5.** Seja $\sigma$ um desarranjo de $\intint1{n+1}$ e $j = \sigma(n+1) \in \intint1n$: $n$ valores possíveis. *Caso $\sigma(j) = n+1$:* os pontos $j$ e $n+1$ se trocam, e $\sigma$ restrito aos $n - 1$ pontos restantes é um desarranjo arbitrário deles: $D_{n-1}$ possibilidades. *Caso $\sigma(j)
\neq n+1$:* seja $i_0 = \sigma^{-1}(n+1)$; aqui $i_0 \neq j$ e $i_0 \leq n$. Defina $\tau$ em $\intint1n$ por $\tau(i) = \sigma(i)$ para $i \neq i_0$ e $\tau(i_0) = j$. Então $\tau$ é uma [permutação](#def-b1-counting-objects) de $\intint1n$ (o valor $n+1$ foi substituído pelo valor $j$, que estava faltando), e é um desarranjo: $\tau(i_0) = j \neq i_0$ e $\tau(i) = \sigma(i) \neq i$ nos demais pontos. Reciprocamente, a partir de um desarranjo $\tau$ de $\intint1n$ e do valor $j$, recupera-se $\sigma$ pondo $\sigma(n+1) = j$, $\sigma(\tau^{-1}(j)) = n+1$ e $\sigma = \tau$ nos demais pontos: uma bijeção, o que dá $D_n$ possibilidades. Somando sobre $j$: $D_{n+1} = n(D_n + D_{n-1})$. Numericamente: $D_5 = 4(9 + 2) = 44$, $D_6 = 5(44 + 9) = 265$.

**6.** Da questão 5, $D_{n+1} = nD_n + nD_{n-1}$, logo

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

Como $u_1 = D_1 - 1 \cdot D_0 = -1$, a indução dá $u_n =
(-1)^n$, isto é, $D_n = nD_{n-1} + (-1)^n$ para $n \geq 1$.

**7.** Indução em $n$. Base: $D_0 = 1 = 0!\,s_0$. Passo: supondo $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 ,
$$

que é a fórmula. Nenhuma inclusão–exclusão foi usada: apenas a recorrência combinatória da questão 5.

**8.** Revisão trinomial, por fatoriais:

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

Agora substitua $a_k = \sum_j \binom kj b_j$ e troque as duas somas finitas:

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

A soma interna é a expansão de $(1 + (-1))^{n-j} = 0^{n-j}$ (teorema binomial, [Teorema 2.16](#thm-b1-counting-binomial)): ela se anula para $j < n$ e vale $1$ para $j = n$. Só $j = n$ sobrevive, e o lado direito é $b_n$, como afirmado.

**9.** Pela simetria $\binom nk = \binom n{n-k}$, a identidade do [Exercício 2.11](#exo-b1-counting-11) reescreve-se como $n! =
\sum_{k=0}^n \binom nk D_k$. Aplique a questão 8 com $a_n = n!$ e $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!} ,
$$

reindexando por $j = n - k$: a fórmula pela terceira vez.

**10.** $D_n = n!\,s_n$ (questão 7), logo

$$
\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$, e a desigualdade da questão 10 é estrita: $D_n$ está a distância $< \frac12$ de $n!/\eu$, logo é o único inteiro mais próximo. Para $n = 0$ a estimativa só dá distância $< 1$ e, de fato, a afirmação falha aí: $0!/\eu \approx 0.368$ tem como inteiro mais próximo $0$, ao passo que $D_0 = 1$.

**12.** $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ é uma série alternada com termos estritamente decrescentes, de modo que o seu sinal é o sinal do primeiro termo $(-1)^{n+1}/(n+1)!$. Portanto, $s_n -
\eu^{-1}$ tem o sinal de $(-1)^n$: para $n$ par, $s_n > \eu^{-1}$ e $D_n = n!\,s_n > n!/\eu$; para $n$ ímpar, $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$. Verificação: $10!/\eu = 3\,628\,800 /
2.718281828 \approx 1\,334\,960.92$, cujo inteiro mais próximo é $1\,334\,961$ — e $D_{10} > 10!/\eu$, como a questão 12 prevê para $n$ par.

**14.** $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} <
\frac1{(n+1)!}$. Para $n = 6$: $p_6 = 265/720 = 0.36806$ (cinco casas decimais), contra $\eu^{-1} = 0.36788$; a diferença é inferior a $1/7! =
1/5040 < 2 \times 10^{-4}$. A estimativa $1/(n+1)!$ decresce tão depressa que a probabilidade fica fixada em muitas casas decimais já para uma dúzia de cartas: a resposta “cerca de $36.8\%$” é, para todo efeito prático, independente de $n$ — a famosa surpresa do problema.

**15.** Pela questão 2 e por $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!}
$$

quando $n \to \infty$, com $k$ fixado, pois $s_{n-k} \to \eu^{-1}$. Os valores-limite $\eu^{-1}/k!$ ($k \in \N$) são os pesos da distribuição de Poisson de parâmetro $1$.

**16.** Conte as triplas $(\sigma, i, j)$ com $i \neq j$, $\sigma(i) = i$, $\sigma(j) = j$. Escolhendo primeiro o par ordenado: $n(n-1)$ modos; as permutações que fixam $i$ e $j$ são as permutações dos $n - 2$ pontos restantes: $(n-2)!$ delas. Total: $n(n-1)(n-2)! = n!$. Somando antes sobre $\sigma$, conta-se, para cada $\sigma$, os pares ordenados de pontos fixos distintos: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$. Daí a identidade enunciada; dividindo por $n!$, a média de $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ é $1$, logo a média de $\abs{\mathrm{Fix}}^2$ é $1 + 1 = 2$ e a variância é $2 -
1^2 = 1$.

**17.** As proporções $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$. Todas a menos de um por cento de $1 - \eu^{-1}
\approx 0.6321$, oscilando em torno desse valor.

**18.** Diretamente:

$$
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),
$$

e o parêntese é $> 0$. Para $n$ par a diferença é negativa: $s_{n+2} < s_n$, logo $p_0 > p_2 > p_4 > \dots$; para $n$ ímpar ela é positiva: $p_1 < p_3 < p_5 < \dots$ Combinado com a questão 12 (os pares acima de $\eu^{-1}$, os ímpares abaixo) e com a questão 14 (a distância a $\eu^{-1}$ tende a $0$): as duas escadas comprimem $\eu^{-1}$ entre elas.

**19.** Um sorteio completo é uma [permutação](#def-b1-counting-objects) aleatória uniforme, válido quando é um desarranjo: probabilidade $p_n \approx \eu^{-1}$. Pelo fato citado, o número médio de sorteios até o sucesso é $1/p_n$, e a questão 14 dá $1/p_n \approx \eu$ a menos de um erro já desprezível para $n$ pequeno. Assim, um amigo oculto com reinícios custa em média cerca de $\eu \approx 2.72$ sorteios completos — tenha o escritório $6$ pessoas ou $600$.

**20.** Fixe $j \geq 2$ e aplique a classificação da questão 5 ao valor $\sigma(1) = j$. Se $\sigma(j) = 1$: os $n - 2$ pontos restantes carregam um desarranjo arbitrário, $D_{n-2}$ modos. Se $\sigma(j) \neq 1$: redirecione a [pré-imagem](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-map) $i_0 = \sigma^{-1}(1)$ para $j$ exatamente como na questão 5; isso é uma bijeção com os desarranjos dos $n - 1$ pontos $\{2, \dots, n\}$: $D_{n-1}$ modos. Total $D_{n-1} + D_{n-2}$, o mesmo para todo $j$. Somando sobre os $n - 1$ valores de $j$: $D_n = (n-1)(D_{n-1} + D_{n-2})$, o que exibe o fator $n - 1$: $(n-1) \mid D_n$.

**21.** Afirmação: $D_n$ é ímpar se, e somente se, $n$ é par. Indução usando $D_n = nD_{n-1} + (-1)^n$, isto é, $D_n \equiv nD_{n-1} + 1 \pmod 2$. Base: $D_1 = 0$ é par, e $n = 1$ é ímpar: a afirmação vale. Se $n$ é par, $nD_{n-1}$ é par e $D_n \equiv 1$: ímpar, como afirmado. Se $n$ é ímpar, então $n - 1$ é par, logo $D_{n-1}$ é ímpar pela hipótese, e $D_n \equiv D_{n-1} + 1 \equiv 0$: par. A indução se fecha.

**22.** Reduzir $D_n = nD_{n-1} + (-1)^n$ módulo $n$ mata o primeiro termo: $D_n \equiv (-1)^n \pmod n$. Para $n = 10$: $(-1)^{10} = 1$ e, de fato, $D_{10} = 1\,334\,961$ termina no algarismo $1$.

**23.** Para $n \geq 3$, $D_{n-1} \geq 1$ e a divisão da recorrência da questão 6 por $D_{n-1}$ dá $D_n/D_{n-1} = n +
(-1)^n/D_{n-1}$, com $\abs{(-1)^n/D_{n-1}} \leq 1$ e tendendo rapidamente a $0$. Coerência: se $D_n \approx n!/\eu$, então $D_n/D_{n-1} \approx n!/(n-1)! = n$ — o fator $\eu$ se cancela na razão, e a recorrência confirma isso com precisão $1/D_{n-1}$.

**24.** (i) As regras do produto e da soma sustentam toda contagem: as questões 2 e 5 repartem [conjuntos](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) de permutações em etapas independentes. (ii) A contagem dupla deu a média (questão 4) e a variância (questão 16) do número de pontos fixos sem fórmula alguma para $D_n$. (iii) O teorema binomial avaliou a soma interna alternada $(1-1)^{n-j}$ que faz a inversão binomial funcionar (questão 8). (iv) A estimativa das séries alternadas converteu a soma exata mas opaca $n!\,s_n$ no enunciado transparente “inteiro mais próximo de $n!/\eu$” (questões 10–14).

**25.** A inclusão–exclusão ([Exemplo 2.26](#ex-b1-counting-derangement) e [Exercício 2.11](#exo-b1-counting-11)) é a demonstração conceitual: ela explica a soma alternada como correções de contagem excessiva e se generaliza literalmente à contagem dos elementos que evitam qualquer família de [conjuntos](https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes#def-b1-logic-sets) “ruins”. A via da recorrência (questões 5–7) é a que calcula mais rápido — tempo linear, aritmética inteira exata, sem fatoriais — e é a fonte dos fatos aritméticos da Parte V. A inversão binomial (questões 8–9) insere a fórmula numa transformada geral que reaparecerá sempre que dois sistemas triangulares de identidades se defrontarem. E o aparecimento de $\eu$ é melhor explicado pela própria fórmula: a proporção de desarranjos é a soma parcial $s_n$ da série de $\eu^{-1}$, de modo que os envelopes de Montmort já calculavam o número $\eu$ três décadas antes da notação de Euler.