Matemática universitária — Graduação 1 · Bachelor Year 1

2Contagem

Contar conjuntos finitos parece elementar — e logo se torna sutil. Este capítulo define a cardinalidade como se deve (por meio de bijeções, no espírito do Capítulo 1), estabelece o punhado de princípios de contagem dos quais tudo decorre e deduz as contagens clássicas: listas, permutações, subconjuntos, coeficientes binomiais.

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 $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) 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 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 $f \colon E \to F$ é injetiva: 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, $v \circ f \circ u$ seria uma injeção de $\intint1m$ em $\intint1n$ (composta de injeções, Proposição 1.26), contradizendo o Teorema 2.2. ∎

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

A demonstração do Teorema 2.2 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 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 sobre o grupo simétrico.

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

Sejam $E, F$ conjuntos finitos 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. 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 de cardinalidade $\abs{F} - 1 < \abs{E}$ — impossível pelo princípio da casa dos pombos. Logo $f(E) = F$ : $f$ é sobrejetiva e, portanto, bijetiva.

Suponha $f$ sobrejetiva. Escolha para cada $y \in F$ uma pré-imagem $s(y) \in E$ ; então $f \circ s = \mathrm{id}_F$ , de modo que $s$ é injetiva (Proposição 1.26). Pelo parágrafo anterior aplicado a $s$ (as cardinalidades são iguais), $s$ é bijetiva. De $f \circ s = \mathrm{id}_F$ obtemos $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , logo $f$ é bijetiva. Por fim, uma aplicação bijetiva é, por definição, ao mesmo tempo injetiva e sobrejetiva, o que fecha o ciclo de implicações. ∎

Exemplo 2.6 (A finitude é essencial)

Num conjunto finito, a Proposição 2.5 é um atalho poderoso: toda aplicação injetiva de $E$ em si mesmo é automaticamente uma permutação de $E$ — metade da bijetividade vem de graça. As duas implicações desmoronam em conjuntos infinitos: $n \mapsto n + 1$ é injetiva de $\N$ em $\N$ , mas não atinge $0$ , e a aplicação $\N \to \N$ que envia $0 \mapsto 0$ e $n \mapsto n - 1$ para $n \geq 1$ é sobrejetiva, mas não injetiva. Sempre que esta proposição é invocada, a hipótese de finitude está fazendo trabalho de verdade — tema que o problema de fim de semana do Capítulo 1 explora pelo outro lado, em que os conjuntos 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 $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): 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); 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), alimenta o emparelhamento do teorema de Wilson e reaparece em álgebra linear como “um endomorfismo de um espaço de dimensão finita é injetivo se, e somente se, é sobrejetivo” (Capítulo 19).

2.2 Os princípios de contagem

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

Sejam $E, F$ conjuntos finitos.

Se $E \cap F = \emptyset$ , então $\abs{E \cup F} = \abs{E} + \abs{F}$ ; mais geralmente, para uma partição de $E$ em peças $E_1, \dots, E_k$ , $\abs{E} = \sum_i \abs{E_i}$ .
Em geral, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ .
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
O conjunto $F^E$ de todas as aplicações de $E$ em $F$ satisfaz $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\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 $\{x\} \times F$ , cada um de cardinalidade $\abs{F}$ ; aplique (1).

(4) Uma aplicação 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).

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. — 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 com $\abs{E} = n$ e seja $0 \leq k \leq n$ .

Um $k$ -arranjo de $E$ é uma $k$ -upla injetiva 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$ :

o número de $k$ -arranjos de $E$ é $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
o número de permutações de $E$ é $n!$ ;
$\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 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 (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 não vazio, exatamente metade tem cardinalidade 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 $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)

Depois, procure uma bijeção ou uma partição que reduza o problema a essas contagens modelo; uma contagem correta é uma bijeção disfarçada.

Observação 2.20 (Armadilhas frequentes em contagem)

Somar casos não disjuntos. A regra da soma exige uma partição; 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) ou uma separação de casos mais fina.
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.
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.
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).

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 que ambos os lados contam — tipicamente um conjunto de pares — e avalie sua cardinalidade 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 e várias questões do problema de fim de semana abaixo.

Exemplo 2.23 (O subconjunto médio)

Qual é a cardinalidade média de um subconjunto de um conjunto $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: 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 $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 $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. 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 e é desenvolvido no volume do segundo ano de graduação.

Exemplo 2.26 (Desarranjos)

Um desarranjo é uma permutação sem ponto fixo. Seja $A_i$ o conjunto 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), 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 são os objetos deste capítulo mais reutilizados: eles conduzem o teorema binomial no Capítulo 8 (expansão de $(X + a)^n$ ), a fórmula de Leibniz para a $n$ -ésima derivada de um produto no Capítulo 14 e os coeficientes das expansões de Taylor no Capítulo 16. As permutações voltam como um grupo — com o sinal construído a partir da contagem das inversões — no Capítulo 7, e o sinal, por sua vez, define os determinantes no Capítulo 22. 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 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

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

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

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

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

Inteiros consecutivos: as casas são os $n$ pares $\{1,2\}, \{3,4\}, \dots, \{2n-1, 2n\}$ , que formam uma partição 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

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

Solução de Exercício 2.6.

Uma aplicação 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 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 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

Solução de Exercício 2.7.

Reparta um conjunto $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

Solução de Exercício 2.8.

Seja $A_d$ o conjunto 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) 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 de $4$ elementos sobre um conjunto de $2$ elementos; depois sobre um conjunto de $3$ elementos. Sugestão: conte as aplicações não sobrejetivas com inclusão–exclusão sobre os valores não atingidos.

Solução

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

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 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 de pontos fixos).

Solução

Solução de Exercício 2.11.

Com $A_i = \{\sigma : \sigma(i) = i\}$ , uma permutação 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 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

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. 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 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 vazia não tem ponto fixo).

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

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$ .)
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}$ .
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?
Por contagem dupla (Método 2.22) dos pares $(\sigma, i)$ com $\sigma(i) = i$ , mostre que

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

em média, uma permutação 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.

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 de $n + 1$ para $j$ .) Verifique a recorrência numericamente até $D_6$ .
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).$
A partir da questão 6, demonstre por indução a fórmula do Exemplo 2.26,

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

— demonstração inteiramente independente da inclusão–exclusão.
(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.)
Aplique a questão 8 à identidade $n! = \sum_k \binom nk D_{n-k}$ do Exercício 2.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 — 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$ .

Mostre que $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ para todo $n \in \N$ .
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$ ?
Determine o sinal do erro: mostre que $D_n > n!/\eu$ exatamente quando $n$ é par. (Localize o primeiro termo desprezado da série alternada.)
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$ ).
(A probabilidade do chapeleiro) Seja $p_n = D_n/n!$ a probabilidade de que uma permutação 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.

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.)
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.
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$ .
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}$ .
(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.

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$ .
Demonstre que $D_n$ é ímpar se, e somente se, $n$ é par. (Trabalhe módulo $2$ na recorrência da questão 6.)
Demonstre que $D_n \equiv (-1)^n \pmod n$ para $n \geq 1$ e confira a congruência no último algarismo de $D_{10}$ .
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$ .
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.
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

Solução de Problema 2.1.

1. $D_1 = 0$ (a única permutação 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 com exatamente $k$ pontos fixos fica determinada pela escolha do seu conjunto de pontos fixos $F$ ( $\binom nk$ modos) junto com a sua restrição ao complementar, que deve ser uma permutação de $n - k$ pontos sem ponto fixo ( $D_{n-k}$ modos). As duas escolhas são independentes e a correspondência é bijetiva: $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 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): 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 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 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 $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 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 e Exercício 2.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 “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.