Em nosso cotidiano é muito comum nos depararmos com situações que envolvam problemas de contagem. Desde as mais simples, em que se é possível determinar através, por exemplo, de um diagrama de árvore, a quantidade de maneiras em que dois ou mais eventos correlacionados podem ocorrer, como com situações em que é necessário se utilizar de métodos especiais de contagem.

Um exemplo simples consiste em determinar quantos anagramas podem ser formados com o uso das quatro letras da palavra BLOG. Mesmo que você ainda não conheça a teoria da Análise Combinatória, é perfeitamente possível chegar ao resultado através da listagem exaustiva das possibilidades ou do uso de um diagrama. Veja abaixo uma das formas de se demonstrar que existem 6 possibilidades de anagramas iniciados com a letra B (BLOG, BLGO, BOLG, BOGL, BGOL e BGLO).

O uso do mesmo raciocínio para as demais letras (L, O e G) nos permite concluir que o número de possibilidades é igual a 24 (4 x 6). Adiante, veremos que a solução é bastante simples, não havendo necessidade de montar um diagrama como o acima, a menos que se queira saber quais são os anagramas, para estabelecer com precisão o resultado.

Mesmo esse caso exige um pouco de trabalho e interpretação para se obter o valor. Agora imagine se você necessitasse determinar a sua chance de ganhar na Mega Sena ou saber quantas placas de carros podem ser construídas com o uso de três letras e quatro algarismos?

É óbvio que o método utilizado acima seria totalmente impraticável para solucionar essas questões. São situações desse tipo, em que se exige a organização e a contagem de grupos, que serão o objeto deste artigo.

Princípio Fundamental da Contagem

O princípio fundamental da contagem estabelece de quantas maneiras dois ou mais eventos correlacionados podem ocorrer.

Assim, se um evento A pode ocorrer de m maneiras diferentes, representadas por a₁, a₂, …, a_m, e, se para cada uma dessas m maneiras um segundo evento B, pode ocorrer de n maneiras diferentes, representadas por b₁, b₂, …, b_n, então o número de maneiras que esses eventos podem ocorrer, um seguido do outro, é igual a mn.

Para demonstrar o princípio é suficiente observar que para cada ocorrência a_i, i = 1, 2, …., m do evento A existem n maneiras de ocorrer o evento B, ou seja, para cada ocorrência a_i de A existem n maneiras em que esses eventos podem ocorrer um seguido do outro. Simbolicamente temos que

(a_i, b₁), (a_i, b₂), …., (a_i, b_n)

onde cada par ordenado representa a ocorrência simultânea dos dois eventos (n vezes) para cada maneira a_i de A. Como i varia de 1 a m, teremos n + n + …. + n (m vezes), que é igual a mn.

Acima consideramos, apenas, a ocorrência de dois eventos distintos. E se fossem iguais, onde uma maneira não pudesse ocorrer, com ela mesma, simultaneamente? E se ocorressem r eventos (r > 2), com maneiras n₁, n₂, …, n_r, respectivamente?

A resposta à primeira pergunta seria m(m – 1), uma vez que m = n e a ocorrência simultânea dos dois eventos é m – 1, para cada maneira a_i, pois, por hipótese, não pode haver repetições do tipo (a_i, a_i).

Para a segunda, a resposta é n₁.n₂. … .n_r e a demonstração pode ser feita pelo princípio da indução finita sobre r, ou seja, provar que é válida para r = 2 (feito acima), supor que é verdadeira para r = p e demonstrar que é verdadeira para r = p + 1 (fica como exercício).

Exemplo 1: Com base no princípio apresentamos, a seguir, outro método para se determinar o número de anagramas formados com a palavra BLOG.

Solução:

• Há quatro (4) maneiras para a escolha da primeira letra;
• Para cada escolha da primeira letra, há três (3) possibilidades para a escolha da segunda;
• Para cada escolha do primeiro par de letras, há duas (2) possibilidades para a escolha da terceira;
• E, finalmente, para cada escolha das primeiras três letras, há somente uma (1) possibilidade para a escolha da quarta.

Portanto, podemos concluir, pelo princípio fundamental da contagem, que o número de anagramas é igual a 4 x 3 x 2 x 1 = 24.

Exemplo 2: Determinar o número de placas de carros que podem ser construídas com o uso de três letras e quatro algarismos.

Solução:

Para resolver o problema, primeiro vamos determinar quantas possibilidades existem para combinar as três letras. Como sabemos que o alfabeto possui 26 letras e é permitida a repetição há 26 maneiras para a escolha da primeira letra, 26 para a segunda e 26 para a terceira. Portanto, existem, pelo princípio fundamental da contagem:

26 x 26 x 26 = 17.576

combinações possíveis.

De forma análoga pode-se afirmar que existem 10.000 combinações possíveis que podem ser estabelecidas com os quatro algarismos. Como a cada escolha de três letras se constroem 10.000 placas, vem que o total de placas é:

10.000 x 17.576 = 175.760.000

A título de curiosidade: Segundo o DENATRAN – Departamento Nacional de Trânsito, do Ministério das Cidades, existiam em 2003, 36.658.501 veículos automotores em todo Brasil, cuja distribuição por região era de 1.184.259 na Norte, 4.448.287 na Nordeste, 20.083.423 na Sudeste, 7.928.580 na Sul e 3.013.952 na Centro-Oeste. E que em 1990 o total era de 18.267.245, mostrando que foram necessários 13 anos para dobrar a frota nacional. Como se vê tem placa para aproximadamente uns 30 anos, na hipótese de que ocorra a mesma evolução mencionada e sem considerar a reutilização.

Exemplo 3: Quantos números ímpares de quatro algarismos podemos escrever utilizando os algarismos 1, 2, 4, 5 e 7?

Solução:

Note que não é condição do problema que os números sejam distintos, mas sómente que sejam ímpares. Desses fatos podemos afirmar que:

• Há três possibilidades de escolha para o algarismo das unidades – algarismos 1, 5 e 7;
• Há cinco possibilidades de escolha para o algarismo das demais casas decimais (milhar, centena e dezena);

para concluir que o total de números ímpares é:

5 x 5 x 5 x 3 = 375

A partir das informações e exemplos pode-se concluir que o princípio fundamental da contagem se constitui em um instrumento básico para a Análise Combinatória. Entretanto, em algumas situações pode se tornar trabalhosa a resolução de problemas com sua aplicação direta. Assim, vamos, a seguir, detalhar as várias maneiras de formarmos agrupamentos e deduzir as fórmulas que permitam a sua contagem.

Permutações Simples ou Sem Repetição

Dado o conjunto A = {a₁, a₂, …, a_n} com n elementos distintos, chamamos permutação dos n elementos de A qualquer sequência formada por esses n elementos.

Por exemplo, se A = {1, 2, 3, 4}, as sequências (1, 2, 3, 4), (1, 3, 2, 4), (1, 4, 2, 3), etc. são permutações dos quatro elementos de A. Do mesmo modo, também são, os anagramas formados pela palavra BLOG, onde cada um dos 24 anagramas é uma permutação das letras (elementos) B, L, O e G.

Fórmula do Número de Permutações

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos distintos e P_n o número de permutações dos n elementos de A. Então P_n é dado por:

P_n = n.(n – 1).(n – 2). … . 3.2.1

Demonstração:

Basta analisar quantas possibilidades de escolha existem para o primeiro, segundo, …, e n-ésimo termo das sequências, sem repetição dos elementos. Assim, para o primeiro há n possibilidades de escolha, para o segundo (n – 1), para o terceiro (n – 2), …, e para o n-ésimo 1. Logo, pelo princípio fundamental da contagem podemos concluir que o número de permutações de n elementos distintos é dado pela fórmula acima.

Exemplo 4: Com relação a palavra VICHE:

1. Quantos anagramas existem?
2. Quantos anagramas começam por V?
3. Quantos anagramas começam por V e terminam com E?
4. Quantos anagramas começam por vogal?
5. Quantos anagramas têm as vogais juntas?

Solução:

1. Cada anagrama é uma permutação das letras V, I, C, H e E. Logo o número procurado é P₅ = 5 x 4 x 3 x 2 x 1 = 120.
2. Como V é fixo, temos que somente permutar as letras I, C, H e E. Logo o número procurado é P₄ = 4 x 3 x 2 x 1 = 24.
3. Neste caso temos que permutar as letras I, C e H. Logo o número procurado é P₃ = 3 x 2 x 1 = 6.
4. Na palavra VICHE temos as vogais I e E. Assim, para cada uma delas fixas (início dos anagramas) temos P₄ = 24 permutações (veja item b). Logo o número procurado é 2 x 24 = 48.
5. Como as vogais têm que estar juntas elas funcionam como se fosse uma única, que deve ser permutada com as letras V, C e H. Daqui vem que existem P₄ = 24 permutações. No entanto, as vogais em cada uma dessas permutações podem se permutar entre si. Logo o número procurado é 2 x 24 = 48.

Fatorial

Seja n um número inteiro não negativo, definimos fatorial de n, e indicamos por n!, através da seguinte relação:

n! = n.(n – 1).(n-2). … .3.2.1 para n maior ou igual 2

1! = 1 e 0! = 1

Com a definição acima podemos escrever, de forma simplificada, a fórmula do número de permutações como:

P_n = n! (n pertencente a N*)

O cálculo do fatorial de n, isoladamente, se torna extremamente trabalhoso, à medida que n cresce. Porém, em determinadas situações muitos cálculos podem ser simplificados se utilizamos a seguinte igualdade, de fácil comprovação:

(n + 1)! = (n + 1).n.(n – 1).(n – 2). … .3.2.1 = (n + 1).n!

Por exemplo, para calcular 11!/9!, ao invés de calcularmos 11! e depois 9! e daí obter o resultado da divisão, com a utilização da igualdade acima o processo se torna muito simples, uma vez que:

11!/9! = 11.10.9!/9! = 11.10 = 110

Permutações com Repetição

Até o momento tratamos apenas de casos em que os cálculos de permutações ocorriam entre um determinado número de elementos distintos. Como fazer, então, para calcular o número de anagramas formados com as letras da palavra MARIA (nome de minha saudosa e muito querida mãe), onde temos duas letras A?

O natural seria esperar que o número de anagramas fosse P₅ = 5! = 120. Note, no entanto, que a troca das duas letras iguais (A) em cada anagrama não resulta em um novo. E como a letra A ocupa duas posições a cada permutação (P₂ = 2! = 2), temos que cada anagrama gera dois anagramas iguais, ou seja, cada anagrama é computado duas vezes no cálculo de P₅. Logo, o número de anagramas formados com as letras de MARIA é igual a:

P₅⁽²⁾ = P₅/P₂ = 5!/2! = 120/2 = 60

onde, em P₅⁽²⁾, o 5 indica o total de letras e o (2) mostra que uma letra se repete duas vezes.

E com a palavra ODORIDES (segundo nome de solteira de Mamãe, que ela abominava, com razão, e retirou quando se casou) quantos anagramas podem ser formados com suas letras?

Por raciocínio análogo, teríamos P₈ = 8! = 40.320 anagramas se não houvesse repetições. Como temos duas letras repetidas O e D, temos P₂.P₂ = 4 anagramas iguais para cada anagrama computado em P₈. Logo o número de anagramas é:

P₈^(2,2) = P₈/P₂.P₂ = 8!/2!.2! = 40.320/4 = 10.080

De forma análoga podemos definir a fórmula geral para o cálculo das permutações com repetição (a demonstração não é feita) como sendo:

onde temos n elementos, em que um deles se repete n₁ vezes, outro n₂ vezes, …, e outro n_r vezes.

Exemplo 5: Quantos anagramas existem com as letras da palavra BLOGOBORGES.

Solução:

Aplicação direta da fórmula, com n = 11, n₁ = 2 (letra B), n₂ = 3 (letra O) e n₃ = 2 (letra G):

Arranjos com Repetição

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos. Chamamos arranjo com repetição dos n elementos p a p a toda sequência formada com p elementos de A não necessariamente distintos.

Fórmula do Número de Arranjos com Repetição

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos, então o número de arranjos com repetição dos n elementos tomados p a p (p pertencente a N*) é:

(AR)_n,p = n.n. … .n (p fatores iguais a n) => (AR)_n,p = n^p

Demonstração:

A demonstração é consequência do princípio fundamental da contagem e da definição de arranjos com repetição. Da definição segue que cada arranjo é formado por p elementos de A não necessariamente distintos. Desse fato, temos que para cada posição da sequência existem n possibilidades de escolha e a demonstração é concluída pelo princípio, uma vez que teremos o produto de p fatores iguais a n.

Arranjos Simples ou Sem Repetição ou Arranjos

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos. Chamamos arranjo simples (ou arranjo) dos n elementos p a p, com p maior ou igual a 1 e menor ou igual a n, a qualquer sequência formada com p elementos de A todos distintos.

Fórmula do Número de Arranjos

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos distintos, então o número de arranjos dos n elementos tomados p a p (p pertencente a N*) é:

A_n,p = n.(n – 1).(n – 2). … .[n – (p – 1)]

Demonstração:

Para demonstrar a fórmula é suficiente determinar quantas sequências, com p elementos distintos de A, é possível formar. Para tanto, bastará determinar os números de possibilidades de escolha para cada um dos elementos da sequência e depois multiplicá-los. Para o primeiro temos n possibilidades de escolha, para o segundo (n – 1), …, e para o p-ésimo n – (p – 1).

Daqui, aplicando o princípio fundamental da contagem obtemos a fórmula do número de arranjos.

Note, a fórmula do número de arranjos diz que para calcular A_n,p basta você fazer o produto do número n por seus sucessivos antecessores até completar p fatores.

Exemplo 6: Calcular A_6,3.

Pelo dito acima vem: A_6,3 = 6 x 5 x 4 = 120.

A fórmula do número de arranjos pode ser simplificada utilizando-se a notação fatorial:

Dessa última fórmula podemos concluir facilmente que se n = p, P_n = A_n,n = n!. Lembre-se da definição de fatorial que 0! = 1.

Exemplo 7: Calcular, agora, A_6,3 utilizando a fórmula simplificada.

A_6,3 = 6!/(6 – 3)! = 6x5x4x3!/3! = 120

Combinações

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos distintos. Chamamos de combinações dos n elementos, tomados p a p, aos subconjuntos de A constituídos de p elementos, que denotamos por C_n,p.

Veja que na difinição de combinações os agrupamentos formados são conjuntos, diferentemente dos arranjos, onde temos sequências. Portanto, nas combinações a ordem não importa, uma vez que em se tratando de conjuntos {a, b} = {b, a}, o que já não é o caso dos arranjos onde a sequência (a, b) é diferente de (b, a). Na resolução de problemas o fato é determinante para estabelecer o procedimento de cálculo a se adotar.

Cálculo do Número de Combinações

Seja A = {a₁, a₂, …, a_n} um conjunto com n elementos distintos. Então o número de combinações dos n elementos de A, tomados p a p é:

onde é apresentada outra notação utilizada para o número de combinações, no final das igualdades.

Demonstração:

Vimos como calcular o número de arranjos e a diferença entre arranjos e combinações. Assim, efetuado o cálculo do número de arranjos dos n elementos p a p, é suficiente eliminarmos o número de repetições existentes (determinados pela ordem de cada agrupamento de p elementos de A) para obtermos o número de combinações.

Em outras palavras, como em qualquer subconjunto de p elementos de A é gerado p! repetições correspondente às permutações desses p elementos, basta, portanto, dividir o número de arranjos por p!, ou seja:

C_n,p = A_n,p/p!

Substituindo A_n,p na igualdade acima obtemos a fórmula do número de combinações.

Para finalizar o artigo seguem mais alguns exemplos de problemas com as respectivas soluções.

Exemplo 8: De uma lista de 10 ministeriáveis, todos com capacidade administrativa comprovada e honestidade ilibada, indicados pela base aliada, o Presidente da República precisa escolher o Ministro da Educação, o Ministro da Cultura e o Ministro dos Esportes. De quantas maneiras diferentes podem ser feitas as escolhas?

Solução:

Primeiro observe que escolhidos três ministeriáveis da lista eles podem ser designados para ocupar os cargos de maneiras diferentes. Assim, cada agrupamento escolhido é regido por uma relação de ordem. Ou seja, cada agrupamento possível é um arranjo de dez ministeriáveis, tomados três a três. Logo:

A_10,3 = 10 x 9 x 8 = 720

Exemplo 9: Quais são as chances de um apostador acertar a sena, a quina ou a quadra com uma aposta simples de seis números da Mega Sena.

Solução:

Os cálculos dessas probabilidades são feitos utilizando-se de:

P(i) = casos prováveis/casos possíveis

Calculemos, primeiro, os casos possíveis. Como a ordem não importa, estamos diante de um caso clássico de combinações. Portanto, como na Mega Sena existem 60 números vem que:

Como para acertar a sena existe uma única possibilidade (C_6,6= 1):

P(sena) = 1/50.063.860

ou seja, sua chance é de 1 em 50.063.860.

No caso da quina os casos prováveis é dado por:

C_6,5.C_54,1 = 6 x 54 = 324

onde C_6,5 é o número de combinações entre os 6 de uma aposta premiada da quina (5 números de uma aposta) e C_54,1 corresponde ao número de possibilidades para se jogar o sexto (para completar a aposta). Portanto,

P(quina) = 324/50.063.860 = 1/154.518

e sua chance é de 1 em 154.518.

Por raciocínio semelhante ao usado para a quina, os casos prováveis de acertar a quadra é determinado por:

C_6,4.C_54,2 = 15 x 1431 = 21465

e, portanto:

P(quadra) = 21465/50.063.860 = 1/2332

e sua chance é de 1 em 2332.

Referências:

1. Fundamentos de Matemática Elementar, Gelson Iezzi, Osvaldo Dolce & Carlos Murakami, São Paulo, Atual Editora Ltda, edição 1977;
2. Matemática para o Ensino Médio: Volume Único, Manoel Jairo Bezerra, São Paulo, Editora Scipione, 2001.