Combinatória/Problemas de Contagem*

Quando desejamos saber o número de elementos de um conjunto sem recorrer a uma contagem direta, lançamos mão da  Análise combinatória. Este tema costuma trazer a nossa mente o estudo de arranjos, permutações e combinações, mas, na realidade,  trata-se de muitos outros conceitos ligados ao estudo de estruturas e relações em conjuntos finitos. Em situações diversas de nosso cotidiano, nos deparamos com o que chamamos de problemas de contagem.

Veremos que os problemas de contagem podem ser resolvidos com apenas alguns princípios básicos e muita engenhosidade. O essencial é a compreensão do problema.

Princípio da Adição : Se A e B são conjuntos disjuntos, com p e q elementos respectivamente, então AUB tem p+q elementos.

Exemplo 1 

• Um menino tem sete bolinhas em uma caixa e dez bolinhas em outra caixa. Quantas bolinhas ele tem ao todo?

                 Resp.:  7+10 = 17

Exemplo 2

• Um treinador trabalha na terça feira  com 23 rapazes que jogam futebol e na quarta feira com 25 rapazes que jogam volei. Dado que 5 rapazes treinam tanto futebol como volei, quantos atletas o treinador tem ao todo?

                  Resp.:  A+B-(A∩B) = 23 + 25 - 5 = 43

Princípio da Multiplicação: Se uma decisão d1 pode ser tomada de p1 maneiras e se, uma vez tomada a decisão d1, a decisão d2 puder ser tomada de p2 maneiras, então o número de maneiras de se tomarem as decisões  d1 e d2 é de p1.p2 maneiras.

Exemplo 3

• Uma lanchonete serve sanduíches que podem ser feitos com pão integral , pão de forma ou pão francês, com sete opções de recheios. Quantos sanduíches distintos podem ser feitos?

                  Resp.: 3.7 = 21

Exemplo 4

• Uma bandeira é formada por quatro listas, que devem ser coloridas de vermelho, branco e  preto, não devendo haver listras adjacentes com mesma cor. De quantos modos se pode colorir a bandeira? (Note que cada escolha limita as opções subsequentes.)

                 Resp.:     Para a primeira lista temos 3 opções de cor
                                Para a segunda, só duas por que não podemos repetir a primeira.
                                Para a terceira temos duas opções, por que não podemos repetir a segunda
                                Para a quarta, temos duas opções, por que não podemos repetir a terceira.
                                Assim, 3.2.2.2= 24. Teremos 24 modos de colorir a bandeira.
                              


Observação: O princípio da multiplicação é apenas uma aplicação do fato de que, se um conjunto A tem x elementos e um conjunto B tem y elementos, então o produto cartesiano de A por B, ou seja AxB, tem x.y elementos.


Dicas:

• Quase todos os problemas de aparência simples, podem ser difíceis. Não existe 'receita' que atenda a todos os casos.
• Num problema de contagem, devemos contar o número de objetos de uma certa classe. Tentar identificar precisamente quando um objeto pertence a uma classe e quando dois deles devem ser considerados distintos.
• Fazer uma representação(figura, esquema, etc.) do problema. Liste alguns dos objetos que pertencem e outros que não pertencem a coleção .
• Examinar quantas decisões  você deve tomar para executar os passos anteriores. Tente usar os princípios básicos para contar  os objetos. Se surgirem dificuldades, tente entender claramente quais são elas.

    Caso ainda não esteja claro como proceder, tente:

• Dividir o problema em subcasos que você saiba resolver.
•  "Esquecer" algumas das condições exigidas para que um objeto pertença à coleção, dá origem a uma classe maior que a desejada. É necessário, portanto, excluir posteriormente os objetos indesejados.
• Enunciar o problema de forma diferente e/ou descobrir problemas equivalentes. Muitas vezes, estes poderão ser mais simples  de resolver.
• Depois de resolvido o problema, repense na solução; veja se está contando alguns casos  mais de uma vez ou se não está se esquecendo de algum. Veja se não é possível encontrar alguma maneira mais simples de resolver o mesmo problema. Tente pensar em outros problemas em que o mesmo método pode ser usado.

Um terceiro e último "Princípio", frequentemente utilizado na resolução de problemas de contagem (mas que não leva o nome oficial de Príncipio na literatura especializada), é o uso sistemático da divisão para eliminar repetições de um mesmo tipo de caso nas contagens.

Exemplo 5

• De quantas caixas de ovos necessito para embalar 48 ovos?

                   Resp.: Uma caixa de ovos tem espaço para 12 ovos, logo, 48/12=4. Necessitamos de 4 caixas.

Exemplo 6

• De quantos modos 3 pessoas podem sentar-se em 5 cadeiras em fila?

Pensando...
A primeira  pessoa tem 5 opções de lugar para sentar, a segunda tem 4 e a terceira 3. Logo

 5   4   3  = 5.4.3 = 60

Um outro modo de pensar, só que mais trabalhoso:
Primeiro verificando de quantos modos as 3 pessoas poderiam se sentar, uma ao lado da outra deixando bancos vazios em um dos lados:

 Então teremos  3   2   1 → 3.2.1 = 6, 

Mas podem haver bancos vazios entre eles , vamos verificar  as possibilidades usando o quadradinho escuro como o banco ocupado.

Logo, temos 10 possibilidades.

                           Resp.: 10.6=60

Exemplo 7

• Quantas comissões de 4 alunos podem ser formadas numa classe de 7 alunos?

Pensando no problema:                   

Na primeira escolha temos 7 opções, na segunda , 6 opções , na terceira temos 5 opções e na quarta, 4 opções.

Logo,

   7   6   5  4  → 7.6.5.4 = 840

Mas 840 não é a quantidade total de comissões. Note que a comissão formada pelos alunos A, B, C e D é a mesma que a formada pelos alunos B, D, C e A. Precisamos saber quantas vezes cada comissão foi contada repetidamente.  

Pensando... cada comissão tem 4 alunos, de quantos modos diferentes podemos fazer a chamada?
  4   3   2   1  → 4.3.2.1 = 24 

Então, das 840 escolhas, cada grupo de 24 representa a mesma comissão. Portanto, o total de comissões será 840/24= 35.

Exemplo 8

• Quantos são os anagramas da palavra MATEMÁTICA?

Pensando...  se todas as letras fossem diferentes, teríamos 

10   9   8   7   6   5   4   3   2   1  = 10.9.8.7.6.5.4.3.2.1=3628800

No entanto  as letras T e M, aparecem 2 vezes cada e a letra A , ignorando o assento, aparece 3 vezes.

para T temos 2.1 =2

para M temos 2.1=2

para A temos 3.2.1=6

Assim, eliminando as repetições  3628800/(2.2.6)=151200 anagramas

             Resp.: 151200 anagramas

Exemplo 9

• Qual o número de rodas de ciranda distintas que podem ser formadas com 7 crianças.

         Note que, quando organizadas em círculo, podemos começar a fila em 7 pontos diferentes que continuará sendo a mesma fila, ou sejam, são equivalentes.

Então, de  7   6   5   4    3   2   1 = 7.6.5.4.3.2.1 = 5040 , teremos que tirar 7 repetições.

               Resp.: 5040/7 = 720

Note que até aqui só utilizamos raciocínio lógico, não fizemos uso de nenhuma fórmula. Ao final, colocaremos uma série de exercícios com situações de complexidades crescentes, sendo que todos poderão ser feito sem o uso de fórmulas.

FORMALIZANDO

I) Do exemplo 6, temos

• De quantos modos 3 pessoas podem sentar-se em 5 cadeiras em fila?

 3   2   1 → 3.2.1 = 6
em 10 possibilidade
10.6=60 que  pode ser reescrito assim

Perceba que tivemos que faze uma escolha de m objetos entre n objetos, onde m<n, e a ordem em que fazemos a escolha determina objetos diferentes. Este tipo de problema aparece frequentemente e recebe o nome de Arranjo simples de m elementos em n. Nestas situações, o resultado é dado por n(n-1)(n-2)...(n-m+1), e a notação utilizada é:

Do exemplo 7, temos

• Quantas comissões de 4 alunos podem ser formadas numa classe de 7 alunos?

  7   6   5  4  → 7.6.5.4 = 840 como escolhas ordenadas de alunos  e
  4   3   2   1  → 4.3.2.1 = 24 como as maneiras diferentes de ordená-los

podemos reescrever 7.6.5.4 como 7!/3! = 840 e 4.3.2.1 como 4! = 24.  Assim, 840/24 ficará

Perceba que tivemos que faze uma escolha de m objetos entre n objetos, onde m<n, e a ordem em não determina objetos diferentes. Nessa situação, ignorando inicialmente que a ordem dos objetos é irrelevante, obtivemos uma quantidade maior que a desejada (840), já que várias comissões foram contadas várias vezes.Para eliminar as repetições usamos a divisão. Uma situação como esta, é comum e recebe o nome de Combinação simples de m elementos em n, cuja notação é:

Do exemplo 8 temos

• Quantos são os anagramas da palavra MATEMÁTICA?

10   9   8   7   6   5   4   3   2   1  = 10.9.8.7.6.5.4.3.2.1=3628800

para T temos 2.1 =2

para M temos 2.1=2

para A temos 3.2.1=6

Logo, 3628800/(2.2.6)=151200, reescrevendo

Note que fizemos o número de todas as possibilidades dividido pelo número de repetições.

Do exemplo 9 temos

• Qual o número de rodas de ciranda distintas que podem ser formadas com 7 crianças.

 7   6   5   4    3   2   1 = 7.6.5.4.3.2.1 = 5040 , teremos que tirar 7 repetições.

 5040/7 = 720 que podemos reescrever como

cd

EXERCÍCIOS PROPOSTOS:

Os exercícios abaixo foram extraídos do livro  "Análise Combinatória e Probabilidade"- Morgado,A.C.O.; Carvalho, J.B.P.;Carvalho, P.C.P.; Fernandez,P. - Coleção do Professor de Matemática -SBM.

1. Quantas palavras contendo 3 letras diferentes podem ser formadas com um alfabeto de 26 letras?

2.Quantos são os gabaritos possíveis vem um teste de 10 questões de múltipla escolha, com 5 alternativas por questão? 

3. Quantos inteiros há entre 1000 e 9999 cujos algarismos são distinto?

4. De quantos modos diferentes podem ser escolhidos um presidente e um secretário de um conselho que tem 12 membros?

5. Quantos números de 4 dígitos são maiores que 2400 e:

    a) tem todos os dígitos diferentes.

    b) não tem dígitos iguais a 3, 5 ou 6.

    c) tem as propriedades a( e b) simultaneamente.

6.Quantos subconjuntos possui um conjunto que tem n elementos?

7. Fichas podem ser azuis, vermelhas ou amarelas; circulares, retangulares ou triangulares; finas ou grossas. Quantos tipos de fichas existem?

8.  Quantos são os anagramas com a palavra PRÁTICO?

9.  De quantos modos 5 rapazes e 5 moças podem se sentar em 5 bancos de 2 lugares cada, de modo que em cada banco fiquem um rapaz e uma moça?

10. De quantos modos podemos formar uma roda com 5 crianças?

11. Quantas saladas contendo exatamente 4 frutas podemos formar se dispomos de 10 frutas diferentes?

12. De quantos modos podemos escolher 6 pessoas, incluindo pelo menos duas mulheres, em um grupo de sete homens e quatro mulheres?

13. Quantas diagonais possui um polígono de n lados?

14. De quantos modos podemos formar uma roda de ciranda com 7 crianças, de modo que duas determinadas dessas crianças não fiquem juntas?

15. O conjunto A possui 4 elementos e o conjunto B possui 7 elementos. Quantas são as funções f : A →  B. Quantas delas são injetoras?

Gabarito:

1) 15600         2) 9.765.625       3) 4.536       4) 132      5)  a)3.864   b)1.567  c)  560     6) 2ⁿ      7) 18       8) 5.040       9) 460.800       10) 24       11) 210        12) 371       13)  n(n-3)/2     14) 480       15) 2.401

____________________

* O material aqui apresentado foi adaptado de um trabalho da Profa. Cristina Cerri e da Profa. Iole de Freitas Druk, do IME-USP, baseado no Trabalho Combinatória sem fórmulas de Antônio Luiz Pereira, Cristina Cerri e Iole de Freitas Druk, do IME-USP, escrito para as oficinas do Projeto Pr-Ciências da Fapesp(2000) e baseado em Morgado et al.Análise Combinatória e Probabilidades, Rio de Janeiro:SBM, 1991.