1.2 Contagem e simetria

O problema de contar quantos são os elementos de um dado conjunto é quase sempre baseado no uso de duas regras básicas. Apesar de simples de serem entendidas, seu uso pode se dar de maneira bastante sofisticada. Estas regras são conhecidas como os princípios fundamentais da contagem.

O princípio aditivo diz o seguinte:
Se uma coleção de objetos pode ser decomposta em duas subcoleções disjuntas, a primeira com $m$ objetos e a segunda com $n$ objetos, então o número total de objetos é $m+n$ .

O princípio multiplicativo diz o seguinte:
Suponha que cada objeto de uma coleção pode ser especificado em duas etapas, de forma que na primeira etapa há $m$ opções e, independentemente do resultado da primeira etapa, na segunda etapa há $n$ opções. Suponha também que escolhas diferentes sempre resultem em objetos diferentes. Então a coleção tem $m\times n$ elementos.

Exemplo 1.19.

Fernanda tem quatro saias: preta, cinza, azul e vermelha, e três camisetas: branca, azul e vermelha. Quantas peças de roupa tem Fernanda? Pelo princípio aditivo, Fernanda tem $4+3=7$ peças de roupa. De quantas formas distintas Fernanda pode se vestir? Escolhendo primeiro a saia e depois a camiseta, pelo princípio multiplicativo vemos que Fernanda tem $4\times 3=12$ formas de se vestir. ∎

Exemplo 1.20.

Severino vai a um restaurante onde há duas opções de prato: peixe e carne (bovina). Como opções de vinho, há Merlot e Malbec (tintos), Sauvignon Blanc e Pinot Grigio (brancos). Além disso, há uma opção de cerveja de trigo. Severino não gosta de combinar carne com vinho branco nem peixe com vinho tinto. Escolhendo primeiro o prato e depois a bebida, vemos, pelo princípio multiplicativo, que Severino tem $2\times 3=6$ possibilidades para pedir. Essa solução é mais simples do que se escolhêssemos primeiro a bebida. Se Severino toma cerveja, há 2 opções de prato. Se Severino toma vinho, há 4 opções de vinho, e para cada opção de vinho há 1 opção de prato. Combinando os princípios aditivo e multiplicativo, Severino tem $1\times 2+4\times 1=6$ possibilidades para fazer o pedido. ∎

Exemplo 1.21 (Sorteio com reposição).

Retiramos uma carta do baralho, anotamos o valor, devolvemos a carta, voltamos a embaralhar e voltamos a retirar uma carta. Qual a probabilidade de que pelo menos uma das duas cartas retiradas seja o $4\clubsuit$ ? Pelo princípio multiplicativo, o número de resultados possíveis desse experimento é $52^{2}$ . Para o evento em questão, há duas possibilidades disjuntas, ou a primeira carta retirada é o $4\clubsuit$ , e a segunda carta é qualquer das $52$ cartas do baralho, ou a primeira carta retirada é qualquer das outras $51$ diferentes e a segunda é um $4\clubsuit$ . Combinando os princípios aditivo e multiplicativo, obtemos $\#A=1\times 52+51\times 1=103$ . Como os números das cartas podem ser permutados antes de cada retirada sem que isso afete as chances de cada resultado, vale a hipótese de equiprobabilidade e, portanto, $\mathbb{P}(A)=\frac{103}{2{.}704}$ . ∎

Exemplo 1.22 (Sorteio sem reposição).

Retiramos, sem reposição, duas cartas de um baralho. Qual a probabilidade de que uma das duas cartas retiradas seja o $4\clubsuit$ ? Para facilitar a contagem, vamos supor que as cartas são retiradas de forma ordenada. Ou seja, primeiro retiramos uma carta do baralho e depois retiramos a outra carta. Pelo princípio multiplicativo, o número de resultados possíveis desse experimento é $52\times 51$ , pois, independentemente de qual seja a primeira carta retirada, para a segunda retirada sempre haverá $51$ cartas restantes no baralho. O evento em questão também pode ser especificado em duas etapas: primeiro escolhemos se o $4\clubsuit$ sai na primeira ou na segunda retirada e, independentemente disso, escolhemos depois qual das outras $51$ cartas sai na outra retirada. Pelo princípio multiplicativo, temos $\#A=2\times 51=102$ . Como os números das cartas podem ser permutados antes de cada retirada sem que isso afete as chances de cada resultado, vale a hipótese de equiprobabilidade e, portanto, $\mathbb{P}(A)=\frac{102}{51\times 52}=\frac{1}{26}$ . ∎

O princípio multiplicativo pode ser estendido para $k$ etapas por indução, se consideramos as etapas $2,\dots,k$ como uma única etapa que consiste em $k-1$ subetapas.

Exemplo 1.23.

Sortear $4$ cartas de um baralho comum, com reposição. Neste caso, podemos tomar $\Omega=\left(\mathclap{\phantom{\big{|}}}\left\{A,2,3,\dots,9,10,J,Q,K\right\}% \times\left\{\clubsuit,\heartsuit,\spadesuit,\diamondsuit\right\}\right)^{4}$ e $\#\Omega=52^{4}.$ Como os números das cartas podem ser permutados antes de cada retirada sem que isso afete as chances de cada resultado, vale a hipótese de equiprobabilidade e, portanto, $\mathbb{P}(D)=\frac{\#D}{52^{4}}$ para todo $D\subseteq\Omega.$

Qual a probabilidade do evento $A=$ “as quatro cartas são valetes”? Escrevendo $A=\left(\left\{J\right\}\times\left\{\heartsuit,\diamondsuit,\spadesuit,% \clubsuit\right\}\right)^{4}$ , temos $\#A=4^{4}$ e $\mathbb{P}(A)=\frac{4^{4}}{52^{4}}=\frac{1}{13^{4}}.$

Qual a probabilidade do evento $B=$ “todas as cartas têm o mesmo naipe”? Temos $4$ escolhas para o naipe, e $13$ escolhas para cada uma das cartas retiradas, logo $\#B=4\times 13^{4}$ e portanto $\mathbb{P}(B)=\frac{4\times 13^{4}}{52^{4}}=\frac{1}{4^{3}}.$ ∎

O princípio aditivo pode ser utilizado de trás para frente.

Exemplo 1.24.

No Exemplo 1.19, de quantas formas Fernanda pode se vestir sem que a saia e a camiseta tenham a mesma cor? As formas de Fernanda se vestir, que são $12$ , podem ser decompostas em dois tipos: com cores iguais, que são $2$ , ou cores diferentes. Portanto, há $10$ combinações que envolvem cores diferentes. ∎

Um objeto considerado frequentemente em probabilidade são as permutações. Comecemos por um assunto familiar: os anagramas.

Exemplo 1.25.

Quantos anagramas tem a palavra M-A-R-C-E-L-O? Podemos construir um anagrama escolhendo uma letra de cada vez, e vemos que, independentemente das escolhas anteriores, a $k$ -ésima letra escolhida terá $8-k$ opções. Pelo princípio multiplicativo, a quantidade de anagramas é dada por $7\times 6\times\dots\times 1=7!=5.040$ . Este é o número de permutações das letras que compõem a palavra. ∎

O princípio multiplicativo também pode ser usado de trás para frente, ou seja, quando conhecemos o número total de objetos e queremos saber quantas opções há na primeira etapa.

Exemplo 1.26.

Quantos anagramas tem a palavra V-L-A-D-A-S? A mesma solução que usamos para M-A-R-C-E-L-O já não funciona, porque o número de escolhas para a segunda letra depende da primeira letra (se foi A ou não). Para resolver esse problema, vamos supor, artificialmente, que os dois A’s da palavra V-L-A-D-A-S sejam distintos, ou seja, vamos calcular os anagramas de V-L-A₁-D-A₂-S. Pelo método anterior, essa palavra tem $6!$ anagramas. Agora veja que um anagrama de V-L-A₁-D-A₂-S pode ser construído em duas etapas: primeiro escolhemos um anagrama de V-L-A-D-A-S e depois escolhemos uma permutação de A₁A₂. O número de opções da primeira etapa é justamente o que queremos calcular, e a segunda tem $2!$ opções. Portanto, V-L-A-D-A-S tem $\frac{6!}{2!}=360$ anagramas. ∎

Exemplo 1.27.

Quantos anagramas tem a palavra M-I-S-S-I-S-S-I-P-P-I? Se as letras fossem todas diferentes, seriam $11!$ . Podemos proceder como no exemplo anterior, mas agora em quatro etapas: primeiro tomando um anagrama de M-I-S-S-I-S-S-I-P-P-I, depois uma permutação de S₁-S₂-S₃-S₄, depois de I₁-I₂-I₃-I₄, e finalmente uma de P₁-P₂. Portanto, M-I-S-S-I-S-S-I-P-P-I tem $\frac{11!}{4!4!2!}=34.650$ anagramas. ∎

Estudaremos agora um objeto tão importante que tem um nome e notação próprios.

Exemplo 1.28.

Daniela tem $13$ camisas de cores diferentes. Para sua próxima viagem de negócios, ela vai levar $5$ camisas. De quantas formas possíveis Daniela pode escolhê-las? Usaremos novamente o princípio multiplicativo de trás para frente. Uma permutação das $13$ camisas pode ser especificada em três etapas: primeiro escolhemos $5$ camisas das $13$ para ficarem nas $5$ primeiras posições, depois permutamos essas $5$ camisas, e finalmente permutamos as $8$ camisas restantes. Deduzimos que, na primeira etapa, que é a escolha de $5$ camisas entre as $13$ disponíveis, há $\frac{13!}{5!8!}$ opções. Portanto, Daniela pode fazer a mala de $\frac{13!}{5!8!}=1.287$ formas diferentes. ∎

O exemplo acima é um caso particular de um objeto combinatorial muito importante. Dados $n\in\mathbb{N}_{0}$ e $k\in\mathbb{Z}$ , denotamos por $\tbinom{n}{k}$ o número de subconjuntos de $k$ elementos que um conjunto qualquer de $n$ elementos possui, e lê-se “combinações de $n$ elementos, $k$ a $k$ ” ou mais vulgarmente “ $n$ escolhe $k$ ”. Analisaremos agora propriedades desses coeficientes a partir dessa definição.

Estes números especiais são também chamados de coeficientes binomiais. Podemos dispor os coeficientes binomiais em uma grande tabela onde na $n$ -ésima linha e $k$ -ésima coluna escrevemos $\tbinom{n}{k}$ . Essa tabela infinita se chama Triângulo de Pascal.⁴⁴ 4 O Triângulo de Pascal foi um objeto recorrente em diversos trabalhos da Matemática antiga. Suas origens remontam ao tratado de metrificação em sânscrito Chandas sutra associado a Pingala, por volta dos séculos III-II a.C., onde havia inclusive uma versão da Relação de Stifel. Posteriormente, aparece também na obra do matemático e poeta persa Omar Khayyan, séculos XI-XII d.C, bem como na Grécia Antiga, na China Antiga, dentre outras manifestações. Mesmo o uso do triângulo no cálculo de probabilidades é anterior a Pascal. No século XVI, Tartaglia já estudava as possíveis combinações de resultados em lançamentos sucessivos de um dado, relacionando-as com esse triângulo. O uso sistemático que Pascal fez do triângulo e suas propriedades na solução de problemas de probabilidade relacionados a jogos de azar, dentre eles o famoso problema dos pontos, fez seu nome definitivamente associado ao triângulo. Vejamos algumas das principais propriedades desses números. Primeiro, dado $n\in\mathbb{N}_{0}$ , temos $\tbinom{n}{k}=0\text{ para }k>n\text{ ou }k<0$ pois, dado um conjunto com $n$ elementos, não há subconjuntos com $k$ elementos para esses valores de $k$ . Ademais, $\tbinom{n}{0}=\tbinom{n}{n}=1,$ pois o único subconjunto com zero elementos é o conjunto vazio e o único subconjunto com $n$ elementos é todo o conjunto.

Uma propriedade fundamental é a Relação de Stifel: $\tbinom{n+1}{k+1}=\tbinom{n}{k}+\tbinom{n}{k+1}.$ Com efeito, um subconjunto de $\{1,\dots,n+1\}$ com $k+1$ elementos pode ser obtido escolhendo-se $k+1$ elementos de $\{1,\dots,n\}$ , ou escolhendo-se o elemento $n+1$ e outros $k$ elementos em $\{1,\dots,n\}$ .

As propriedades acima nos dizem que, se ignorarmos os termos nulos da nossa tabela de coeficientes binomiais, esta assumirá uma forma triangular, e encontramos o número $1$ no início e no final de cada linha do triângulo. Esse formato triangular combinado com a Relação de Stifel nos permite encontrar todos os valores de uma linha a partir da linha anterior.

Os coeficientes binomiais também têm a propriedade de simetria: $\tbinom{n}{k}=\tbinom{n}{n-k}.$ Com efeito, basta ver que há uma bijeção entre o conjunto de subconjuntos de $\{1,\dots,n\}$ contendo $k$ elementos e o de subconjuntos contendo $n-k$ elementos. Um exemplo de bijeção é simplesmente tomar o complementar de cada conjunto.

O Teorema das Linhas diz que $\sum_{k=0}^{n}\tbinom{n}{k}=2^{n},$ o que é justificado observando-se que ambos os lados da igualdade acima correspondem à quantidade de subconjuntos de $\{1,\dots,n\}$ . Para o lado esquerdo, classificamos os subconjuntos pelo seu tamanho e observamos que, para cada $k$ , há $\tbinom{n}{k}$ subconjuntos com exatamente $k$ elementos e, somando sobre os possíveis valores de $k$ , concluímos pelo princípio aditivo que o número total de subconjuntos é $\sum_{k=0}^{n}\tbinom{n}{k}$ . Para o lado direito, observamos que um subconjunto $A\subseteq\{1,\dots,n\}$ pode ser especificado em $n$ etapas, onde na $k$ -ésima etapa dizemos se $k\in A$ ou $k\not\in A$ , totalizando $2^{n}$ possibilidades pelo princípio multiplicativo. Portanto, $\sum_{k=0}^{n}\tbinom{n}{k}=2^{n}$ , como queríamos demonstrar.

O Teorema Binomial generaliza o Teorema das Linhas, e diz que

(a+b)^{n}=\sum_{k=0}^{n}\tbinom{n}{k}a^{k}b^{n-k}

para todos $a,b\in\mathbb{R}$ e $n\in\mathbb{N}_{0}$ . Com efeito, ao expandir o binômio $(a+b)^{n}={(a+b)\times\dots\times(a+b)}$ , a operação a ser feita é escolher $a$ ou $b$ em cada um dos $n$ parêntesis acima, multiplicar os valores escolhidos e depois somar sobre todas as possíveis escolhas. Ao multiplicar, obtemos produtos da forma $a^{k}b^{n-k}$ , onde $k$ é o número de parêntesis na expansão acima em que escolhemos o símbolo $a$ . Ao somar todas as possíveis escolhas, podemos agrupá-las em função dos distintos valores de $k$ . Cada termo da forma $a^{k}b^{n-k}$ aparecerá uma determinada quantidade de vezes, dada pelo número de possíveis escolhas de $k$ parêntesis dentre os $n$ disponíveis, isto é, $\tbinom{n}{k}$ . Isso prova o teorema.

Para fins de cálculos de probabilidades, há uma fórmula explícita para o coeficiente binomial, que podemos extrair do Exemplo 1.28. Naquele exemplo tínhamos $n=13$ e $k=5$ e, aplicando exatamente o mesmo raciocínio para $n\geqslant k\geqslant 0$ inteiros, obtemos

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

Exemplo 1.29.

No Exemplo 1.23, qual a probabilidade do evento $C=$ “há um par de cartas de um naipe e um par de cartas de um outro naipe”? Temos $\tbinom{4}{2}$ escolhas para os naipes. Escolhidos os naipes, temos $\tbinom{4}{2}$ combinações para quais retiradas correspondem a cada naipe. Escolhidos os naipes e as posições, há $13$ escolhas de cartas para cada retirada. Assim, $\#C=\textstyle\tbinom{4}{2}\tbinom{4}{2}13^{4}=(\tfrac{4!}{2!\,2!})^{2}13^{4}=% 6^{2}13^{4}$ e, portanto, $\mathbb{P}(C)=\frac{6^{2}13^{4}}{52^{4}}=\frac{6^{2}}{4^{4}}=\frac{9}{64}.$ ∎

Exemplo 1.30.

No Exemplo 1.28, se Daniela escolhe as camisas ao acaso, qual a probabilidade de que ela leve as camisas azul e vermelha em sua mala? Para isso temos que considerar de quantas formas é possível levar ambas as camisas azul e vermelha. Especificar uma configuração cumprindo essas condições é o mesmo que especificar um conjunto de $3$ camisas dentre as $11$ que não são nem azul nem vermelha. Novamente, por razões de simetria, a medida de probabilidade correta é $\mathbb{P}(D)=\frac{\#D}{\#\Omega}\text{ para todo }D\subseteq\Omega$ e, se $A$ denota o evento acima, então

\mathbb{P}(A)=\frac{\tbinom{11}{3}}{\ \tbinom{13}{5}\ }=\frac{\tfrac{11!}{3!8!% }}{\ \tfrac{13!}{5!8!}\ }=\frac{5\times 4}{\ 13\times 12\ }=\frac{5}{39}.\qed

Observação 1.31.

O Exemplo 1.22 foi resolvido sem usar o coeficiente binomial, supondo-se que as cartas eram retiradas de forma ordenada. Se considerássemos as cartas retiradas como um subconjunto do baralho contendo dois elementos, sem distinção de ordem, a solução seria

\mathbb{P}^{\prime}(A^{\prime})=\frac{\#A^{\prime}}{\#\Omega^{\prime}}=\frac{5% 1}{\tbinom{52}{2}}=\frac{1}{26}.\qed

O uso de bijeções pode ser muito poderoso, como veremos a seguir.

Exemplo 1.32 (Princípio da reflexão e números de Catalan).

Eva teve quatro filhas, a primeira e a terceira não tiveram filhas, a segunda teve duas filhas (a primeira das quais não teve filhas e a segunda teve uma filha que não teve filhas), e a quarta teve três filhas, que não tiveram filhas. Veja que Eva teve $10$ descendentes por linhagem feminina (consideramos apenas a linhagem feminina). Na Figura 1.4, ilustramos a árvore de descendência de Eva, que é uma das possíveis árvores com $10$ descendentes. Quantas árvores distintas existem com $10$ descendentes? Esse número é conhecido como o décimo número de Catalan. Se consideramos o mesmo problema para $n$ descendentes, a solução é o $n$ -ésimo número de Catalan, que denotaremos por $C_{n}$ .

A árvore genealógica de Eva e o respectivo caminho gerado.
À direita temos os cinco exemplos possíveis de árvores com três descendentes. — Figura 1.4: A árvore genealógica de Eva e o respectivo caminho gerado. À direita temos os cinco exemplos possíveis de árvores com três descendentes.

Para deixar claro como as árvores são contadas, na Figura 1.4 mostramos todas as árvores com $3$ descendentes, e há $5$ delas: filha, neta e bisneta; filha e duas netas; três filhas; duas filhas e uma neta através da filha mais velha; duas filhas e uma neta através da filha mais jovem. Portanto, $C_{3}=5$ .

Dada a árvore de descendência de Eva, podemos definir um caminho que contorna os elos da árvore no sentido anti-horário. Tal caminho é formado por $10$ passos para cima, $10$ passos para baixo, termina na altura inicial e nunca fica abaixo desta. Na Figura 1.4 mostramos como construir esse caminho. Observe que é possível reconstruir a árvore a partir do caminho, portanto esses objetos estão em bijeção.

De modo mais geral, quantas são as árvores com $n$ descendentes? Dado $m\in\mathbb{N}$ , dizemos que a $m$ -upla $s=(s_{1},\dots,s_{m})\in\mathbb{Z}^{m}$ é um caminho simples de duração $m$ se $s_{k}-s_{k-1}=+1$ ou $-1$ para $k=1,\dots,m$ , com $s_{0}=0$ . Assumindo duração sempre de $2n$ , temos que $C_{n}$ é igual ao número de caminhos que voltam à origem no tempo $2n$ e nunca passam por $-1$ .

Definimos $\tau=\tau(s)=\min\{k\geqslant 1:s_{k}=-1\}$ , onde $\min(\emptyset)=+\infty$ , como o instante da primeira passagem por $-1$ , ou seja, $s_{j}\geqslant 0$ para $j<\tau$ e $s_{j}=-1$ para $j=\tau$ caso $\tau<\infty$ . Nessa notação, $C_{n}=\#\{s:s_{2n}=0,\tau(s)>2n\}$ .

Figura 1.5: Um caminho que passa por $-1$ e termina na origem e o respectivo caminho refletido, que termina em $-2$ (passando obrigatoriamente por $-1$ ).

Observe que, se $s_{2n}=2k$ , há exatamente $n+k$ passos para cima e $n-k$ passos para baixo, e a quantidade de tais caminhos é $\tbinom{2n}{n+k}$ . Por outro lado, o conjunto de todas as trajetórias que terminam em $s_{2n}=0$ pode ser particionado pelos conjuntos daquelas que nunca passam por $-1$ e daquelas que sim passam por $-1$ . Pelo princípio aditivo, conclui-se que

\tbinom{2n}{n}=C_{n}+\#\{s:s_{2n}=0,\tau(s)\leqslant 2n\}.

Portanto, nossa tarefa agora consiste em calcular o último termo da equação acima, o que faremos usando um truque chamado princípio da reflexão.

Dado um caminho $s$ de duração $2n$ tal que $\tau(s)\leqslant 2n$ , definimos o caminho $s^{\prime}$ refletindo, em relação à reta $y=-1$ , a parte do caminho posterior à primeira visita a $-1$ . Ou seja, $s^{\prime}_{j}=s_{j}$ para $j\leqslant\tau$ e $s^{\prime}_{j}=-2-s_{j}$ para $j\geqslant\tau$ .

Observe na Figura 1.5 que $s^{\prime}$ é um caminho de duração $2n$ e $s^{\prime}_{2n}=-2$ . Por outro lado, todo caminho que termina em $-2$ passa necessariamente por $-1$ . Além disso, $(s^{\prime})^{\prime}=s$ , e podemos ver que o mapa $s\mapsto s^{\prime}$ é uma bijeção entre o conjunto dos caminhos de duração $2n$ que visitam $-1$ e terminam na origem e o conjunto dos caminhos de duração $2n$ que terminam em $-2$ . Assim, $\#\{s:s_{2n}=0,\tau(s)\leqslant 2n\}=\#\{s:s_{2n}=-2\}=\tbinom{2n}{n+1}.$ Obtemos, assim, a expressão

C_{n}=\tbinom{2n}{n}-\tbinom{2n}{n+1}

para o $n$ -ésimo número de Catalan. ∎