O que é Arranjos, permutações, combinações?

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

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.

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

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

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.

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.