Combinatória

Habito a Possibilidade —

Em problemas de contagem, raramente é necessário enumerar todas as possibilidades. A dificuldade principal consiste, em geral, em identificar corretamente quais objetos estão sendo contados e de que maneira podem ser organizados.

Em alguns problemas, as possibilidades são divididas em casos disjuntos; em outros, uma escolha é realizada em várias etapas. Há ainda situações em que a ordem dos elementos altera o resultado e outras em que ela é irrelevante. Essas distinções determinam os princípios e as fórmulas que serão utilizados.

A enumeração de casos simples pode servir para reconhecer a estrutura de uma contagem. As fórmulas gerais surgem quando esse raciocínio é expresso de forma independente do número particular de possibilidades.

5.1 Princípios de contagem

5.1.1 O princípio aditivo

Suponha que uma possibilidade possa pertencer a uma de duas classes que não têm elementos em comum. Se a primeira classe contém \(m\) possibilidades e a segunda contém \(n\), então há \(m+n\) possibilidades ao todo.

Se os conjuntos não forem disjuntos, os elementos de \(A\cap B\) serão contados duas vezes. Nesse caso,

O princípio aditivo aplica-se quando a contagem é dividida em casos disjuntos. Conta-se cada caso separadamente e somam-se os resultados. Essa situação deve ser distinguida daquela em que uma mesma escolha é realizada em etapas sucessivas.

5.1.2 O princípio multiplicativo

Considere agora uma escolha feita em etapas. Para cada resultado da primeira etapa, uma segunda escolha ainda precisa ser feita. Se há \(n\) possibilidades na primeira etapa e, para cada uma delas, há \(m\) possibilidades na segunda, então cada uma das \(n\) escolhas iniciais se desdobra em \(m\) resultados.

Se as possibilidades da primeira etapa são

e as da segunda são

então os resultados completos são pares

Para \(a_1\) há \(m\) pares possíveis; para \(a_2\) há outros \(m\); e assim por diante. Temos \(n\) grupos com \(m\) resultados em cada um. Por isso aparecem \(n\cdot m\) possibilidades, e não \(n+m\).

Em termos de conjuntos, se \(\# A=n\) e \(\# B=m\), então

O mesmo argumento vale para qualquer número finito de etapas. As opções podem variar de uma etapa para outra; basta que o número de possibilidades em cada etapa seja conhecido para qualquer escolha feita anteriormente.

5.1.3 Subconjuntos e palavras binárias

A contagem anterior baseia-se numa correspondência biunívoca entre subconjuntos de \(A\) e palavras binárias de comprimento \(n\). Cada subconjunto determina uma única palavra e, reciprocamente, cada palavra determina um único subconjunto. Os dois conjuntos têm, portanto, a mesma cardinalidade.

5.2 Contagens em que a ordem importa

Em determinados problemas, duas escolhas formadas pelos mesmos elementos podem ser distintas quando a ordem é alterada. Escolher Ana e Bruno para uma comissão é a mesma escolha que Bruno e Ana; escolher Ana para presidente e Bruno para vice é diferente de inverter essas funções. No segundo caso, o objeto contado é uma lista ordenada.

5.2.1 Arranjos sem repetição

Considere inicialmente cinco estudantes disputando três funções diferentes: presidente, vice-presidente e secretário. Para presidente há \(5\) escolhas. Feita essa escolha, a mesma pessoa não pode ocupar a vice-presidência, de modo que restam \(4\) escolhas. Escolhidos presidente e vice, restam \(3\) possibilidades para secretário. Pelo princípio multiplicativo,

Nesse problema, não se escolhem apenas três pessoas; preenchem-se três posições distintas. Assim, Ana como presidente e Bruno como vice constitui um resultado diferente daquele em que as duas funções são trocadas.

O mesmo raciocínio vale com \(n\) elementos e \(r\) posições. Para formar um arranjo, preenchemos as posições uma de cada vez. Há \(n\) escolhas para a primeira posição. Depois de usada uma delas, restam \(n-1\) para a segunda; depois \(n-2\) para a terceira. Ao chegar à posição \(r\), já usamos \(r-1\) elementos, portanto restam

escolhas. Multiplicando o número de escolhas feitas em cada etapa, obtemos

A escrita com fatoriais apenas compacta esse produto. Como

dividir ambos os lados por \((n-r)!\) fornece

5.2.2 Permutações

Quando todos os elementos são utilizados, obtém-se o caso particular das permutações.

A contagem pode ser feita diretamente. Considere \(n\) objetos distintos e \(n\) posições. Para a primeira posição há \(n\) escolhas. Depois de ocupado um lugar, restam \(n-1\) objetos para a segunda posição; depois \(n-2\) para a terceira, e assim sucessivamente, até restar uma única escolha para a última posição. Portanto,

Assim o fatorial não aparece como uma convenção arbitrária: ele registra exatamente o número de escolhas sucessivas necessárias para ordenar todos os elementos. Naturalmente, isso também é o caso \(r=n\) da fórmula dos arranjos:

5.3 Permutações com repetições

Se cada posição de uma lista admite livremente qualquer um de \(n\) símbolos, uma lista de comprimento \(r\) pode ser formada de \(n^r\) maneiras. Há, porém, uma situação distinta, na qual as multiplicidades de cada símbolo estão previamente fixadas.

Nesse caso, permutar entre si cópias iguais não produz uma nova ordenação. A contagem deve, portanto, corrigir as repetições introduzidas quando essas cópias são tratadas provisoriamente como distintas.

A divisão corrige a contagem realizada com cópias artificialmente distintas. O denominador é precisamente o número de ordenações que produzem o mesmo resultado depois que os índices são retirados.

5.4 Combinações

Considere a escolha de \(r\) elementos de um conjunto com \(n\) elementos, sem levar em conta a ordem. Uma maneira de obter a fórmula correspondente consiste em contar primeiro as listas ordenadas e, em seguida, determinar quantas delas representam a mesma escolha.

Considere, inicialmente,

e suponha que queremos escolher dois elementos. Se mantivermos a ordem, obtemos listas como

e o princípio multiplicativo dá \(4\cdot 3=12\) listas ordenadas.

Mas, se estamos apenas escolhendo uma dupla, as listas \((a,b)\) e \((b,a)\) representam a mesma escolha \(\{ a,b\} \). O mesmo acontece com toda dupla: cada subconjunto de dois elementos foi contado exatamente

vezes. Por isso o número de duplas é

O mesmo argumento vale no caso geral. Há \(A(n,r)\) maneiras de escolher e ordenar \(r\) elementos. Fixe um subconjunto com \(r\) elementos. Ele pode ser ordenado de

maneiras, e todas essas ordenações representam a mesma combinação quando a ordem é esquecida. Assim, na contagem por arranjos, cada combinação aparece exatamente \(r!\) vezes. Dividindo por esse fator,

A diferença entre arranjos e combinações está, portanto, na informação preservada: o arranjo registra os elementos escolhidos e sua ordem; a combinação registra apenas o subconjunto escolhido.

5.5 Coeficientes binomiais

Os coeficientes binomiais contam subconjuntos de cardinalidade fixada. Essa interpretação combinatória permite obter diversas identidades sem recorrer diretamente à expressão em fatoriais.

5.5.1 Simetria

Escolher \(r\) elementos entre \(n\) equivale a decidir quais \(n-r\) ficarão de fora. De fato, a cada subconjunto \(B\) com \(r\) elementos corresponde exatamente o seu complementar, que possui \(n-r\) elementos, e essa correspondência pode ser invertida. Portanto as duas coleções têm a mesma quantidade de elementos:

A identidade expressa, portanto, a correspondência entre escolher os elementos de um subconjunto e escolher os elementos de seu complementar.

5.5.2 A identidade de Pascal

A demonstração consiste em particionar os subconjuntos em dois casos disjuntos, conforme contenham ou não o elemento fixado. A identidade de Pascal é, assim, uma aplicação direta do princípio aditivo.

A identidade de Pascal gera o triângulo

no qual cada entrada interna é a soma das duas entradas imediatamente acima.

5.5.3 O binômio de Newton

Considere inicialmente o caso

Para obter um termo \(ab^2\), precisamos escolher \(b\) em exatamente dois dos três fatores e \(a\) no fator restante. Há três maneiras de escolher quais dois fatores fornecerão o \(b\), por isso o termo \(ab^2\) aparece com coeficiente \(3\). Da mesma forma, o coeficiente de \(a^2b\) também é \(3\).

No caso geral, cada termo da expansão é produzido escolhendo, em cada fator, \(a\) ou \(b\). Se o termo final contém exatamente \(k\) fatores \(b\), basta escolher quais \(k\) dos \(n\) fatores forneceram esses \(b\). Existem \(\binom nk\) escolhas.

5.6 Aprofundamento: o método de barras e estrelas

Certas equações em números inteiros podem ser interpretadas como problemas de distribuição de objetos idênticos entre caixas distintas. Nessa representação, as soluções correspondem a escolhas de posições para separadores.

Considere as soluções inteiras positivas de

Disponha \(n\) objetos idênticos em uma fila. Uma divisão em \(r\) grupos não vazios é determinada pela escolha de \(r-1\) das \(n-1\) lacunas entre objetos consecutivos, nas quais são colocados separadores.

Por exemplo, a solução \((3,2,1)\) de \(x+y+z=6\) pode ser representada por

O caso das soluções não negativas pode ser reduzido ao anterior. Como algumas variáveis podem assumir o valor zero, adicionamos uma unidade a cada uma delas. Defina

Então \(x_i\geq 0\) se, e somente se, \(y_i\geq 1\), e

se transforma em

Essa transformação é reversível: de uma solução positiva em \(y_1,\dots ,y_r\) recuperamos uma única solução não negativa tomando \(x_i=y_i-1\). Portanto os dois conjuntos de soluções têm o mesmo tamanho. Aplicando o resultado anterior à soma \(n+r\), obtemos