Análise Combinatória

Análise Combinatória

(Parte 1 de 7)

Professor Gerson Henrique Departamento Matemática Associação Pré-UFMG

Prof. Gerson Henrique 2

Apresentação

Essa é uma apostila com conteúdo de ensino médio voltado para o vestibular – foco Vestibular universidade Federal de Minas Gerais. Foi idealizada com o intuito de fornecer um material acessível a todos os estudantes de ensino médio e pré-vestibulares que almejam sucesso no vestibular.

Esta apostila, contém o assunto de Introdução à análise Combinatória. É formulada numa linguagem simples, mas sem perda do rigor matemático.

Contém os seguintes tópicos:

1 – Introdução; 2 – Quando somar e quando multiplicar em combinatória; 3 – Permutações, 3.1 – Permutações simples, 3.2 – Permutações com repetição, 3.3 – Permutações circulares; 4 – Arranjos simples; 5 – combinações simples.

Os tópicos da matéria são apresentados, em seguida há exercícios resolvidos que auxiliam a fixação da matéria e por último vêm os exercícios para você resolver. Não deixe de resolvê-los, pois, é de fundamental importância para a concretização de seu aprendizado.

Espero que este material o auxilie em sua caminhada rumo a universidade.

Bons estudos! O Autor

Dedico este trabalho a minha mãe, Madalena.

Prof. Gerson Henrique 3

Análise combinatória 1 - Introdução

Em análise combinatória ou simplesmente combinatória estaremos envolvidos com problemas de contagem. Esse assunto é objeto de discussão e interesse há muitos anos, principalmente entre pessoas que disputam jogos de azar e almejavam saber as chances de vitória nas partidas que disputavam. Tem larga aplicação nos estudos de probabilidade e estatística. Além disso, problemas de contagem fazem parte do nosso cotidiano. Desde muito cedo aprendemos a contar e, aprendendo boas técnicas, podemos realizar contagens com eficiência, brevidade e precisão. É importante notar, ao resolver questões desse assunto, que apesar de haver uma infinidade de situações diferentes entre si, eles podem ter semelhanças em vários pontos. Dessa forma para que possa obter sucesso nesse assunto, não se esqueça de resolver muitas questões. Busque sempre semelhanças entre elas.

2 - Quando somar e quando multiplicar em combinatória

2.1 - Quando somamos resultados combinatórios lançamos mão do chamado princípio aditivo. Veja esse exemplo:

Adriana tem dinheiro apenas para ir ao parque de diversões e brincar em apenas um dos 7 brinquedos disponíveis ou ir ao cinema e assistir apenas um filme dos 5 disponíveis. Dessa forma de quantas maneiras diferentes Adriana pode se divertir?

Se Adriana tem dinheiro apenas para uma diversão ela tem de optar ou por brincar em um dos brinquedos do parque ou assistir a um filme do cinema. Assim ela tem 7 opções para ir ao parque e 5 opções para ir ao cinema. Dessa forma ela tem 7 + 5 maneiras de se divertir.

Brinquedo 1Filme A
Brinquedo 2Filme B
Brinquedo 3Filme C 5 maneiras distintas
Brinquedo 47 maneiras distintas Filme D
Brinquedo 5Filme E

Brinquedo 6 Brinquedo 7

Para formalizar, observe a semelhança deste enunciado com o problema proposto anteriormente.

Dados dois conjuntos disjuntos (sem nenhum elemento comum; sem interseção) A e B, A contém m elementos e B contém p elementos. De quantos modos diferentes podemos escolher um elemento de A ou de B.

7 brinquedos distintos + 5 filmes distintos = 12 maneiras distintas de se divertir.

É importante ressaltar o significado do termo distinto. Significa diverso, separado, que não se confunde com outro; para passar a idéia de casos não idênticos.

Prof. Gerson Henrique 4

Como queremos um elemento de A ou de B, temos (m + p) maneiras de escolher um dos elementos. Esse resultado nada mais é do que o número de elementos da união dos dois conjuntos disjuntos.

2.2 - Quando multiplicamos em análise combinatória estamos lançando mão do princípio multiplicativo ou teorema fundamental da contagem.

Observe o exemplo:

Um motorista deseja viajar de uma A para a cidade C, mas para ir à cidade C deve-se passar necessariamente pela cidade B, veja a figura.

Como observado na figura, o motorista pode escolher entre três estradas para se deslocar de A para B e depois deve escolher uma entre as duas estradas para se deslocar de B para C.

Essa situação difere e muito da do exemplo anterior. Aqui para que o motorista vá da cidade A para a cidade C tem de passar necessariamente pela cidade B. Isto é, tem de realizar duas ações para deslocar-se de A para C. Primeiro deve escolher uma estrada de A para B e em seguida outra que liga B a C.

Vamos inserir para a resolução dessa questão o conhecido diagrama da árvore. Recebe esse nome pelas ramificações que lembram galhos de uma árvore. Veja:

Primeiro escolhemos uma estrada que sai de A e vai até B

Assim temos 3 opções para o deslocamento. Após escolhido a primeira opção deve escolher o caminho de B para C. Assim tem-se:

2 A B C

Prof. Gerson Henrique 5

É crucial que você entenda que da cidade A para a cidade B, há três opções para o motorista, no entanto ele optara apenas por uma delas. Após a escolha surge uma nova dúvida para nosso amigo. Qual estrada usar para deslocar-se de B para C. Assim com essas duas sucessivas escolhas, pelo diagrama da árvore, vemos que nosso motorista tem seis opções para fazer a viagem. Esse resultado é justamente o produto do número de opções para a escolha da primeira estrada pelo número de opções de escolha para a segunda. Portanto 623=⋅

Vamos voltar a situação de Adriana do penúltimo exemplo. Descontente com sua situação, a de ter dinheiro apenas para uma opção de lazer, foi ao seu pai tentar arrecadar mais dinheiro. Foi atendida e agora tem dinheiro para duas ações. Dessa forma de quantas maneiras diferentes Adriana pode se divertir sem realizar duas vezes a mesma brincadeira?

Note que diante do fato nossa amiga pode realizar duas ações diferentes. Assim primeiro deve escolher uma diversão e em seguida outra que também a agrade.

Primeira escolha: Possui 12 opções de lazer Segunda escolha: Possui 1 opções ( não vai repetir a ação)

Veja que o diagrama da árvore ficaria imenso, se colocado todas as possibilidades, então ramificaremos apenas no brinquedo 5

Para a primeira escolha há 12 tipos de diversão. Supomos que foi escolhido o brinquedo 5 e após essa escolha vem a segunda ação. Não se esqueça que foi exigido que Adriana não repetisse a brincadeira. Restam agora 1 opções de escolha.

Tenha sempre em mente que há varias opções, mas só uma será escolhida. Estamos contando as possibilidades de escolha, não a escolha de Adriana, que será apenas uma. Dessa forma como Adriana optou pelo brinquedo 5, pode, logo em seguida, optar por outra escolhida dentre onze opções distintas. Só aí temos 1 opções de escolha ( Veja o diagrama). Se optasse pelo brinquedo 1 ao invés do 5, teria mais 1 opções para a segunda ação. São mais 1 opções de diversão. Se escolhesse o Brinquedo 2 aí seriam mais 1 opções. Seguindo sucessivamente notamos que a cada primeira ação temos, para a segunda, 1 opções de lazer. Assim como são 12 as maneiras distintas de escolher a primeira ação concluímos que Adriana pode se divertir de

BRINQUEDO 1 BRINQUEDO 2 BRINQUEDO 3 BRINQUEDO 4 BRINQUEDO 5 BRINQUEDO 6 BRINQUEDO 7 FILME 1 FILME 2 FILME 3 FILME 4 FILME 5

BRINQUEDO 1 BRINQUEDO 2 BRINQUEDO 3 BRINQUEDO 4

BRINQUEDO 6 BRINQUEDO 7 FILME 1 FILME 2 FILME 3 FILME 4 FILME 5

Prof. Gerson Henrique 6

Como dito anteriormente, a cada escolha da primeira ação decorre 1 opções de lazer. Assim:

Exercícios resolvidos – Questões de vestibulares

1. Quantos números de 4 algarismos podemos formar utilizando, uma única vez, os numerais 3, 4, 5 e 6 ?

Resolução: Como quereremos formar números com quatro algarismos teremos que preencher quatro casas com 3, 4, 5 e 6. Repare:

Para a primeira casa temos 4 algarismos para preenchê-la. Já para a segunda, como os algarismos podem aparecer uma única vez e já utilizamos um para a primeira, restam 3 algarismos. Pelo mesmo raciocínio, na terceira restarão 2 e para a quarta e última casa 1 algarismo. Vamos usar o diagrama da árvore como solução.

1ª ação2ª ação 3ª ação ... 12ª ação = 12 ações
1 opções + 1 opções + 1 opções ++ 1 opções = 12 x 1 opções de lazer
2ª 3ª 4ª

12 x 1 = 132 maneiras diferentes casas

Prof. Gerson Henrique 7

24 núm e r os di s t i nt os

1ª casa 2ª casa 3ª casa 4ª casa Número formado

Prof. Gerson Henrique 8

Com o diagrama verificamos que podemos formar 24 números com os algarismos 3,4,5 e 6. Entretanto esse resultado pode ser obtido facilmente pelo princípio multiplicativo.

Na primeira casa temos 4 opções de escolha, na segunda 3 opções, na terceira 2 opções, na quarta e última 1 opção. observe

Finalmente, multiplicamos esses valores 4 • 3 • 2 • 1 = 24 números diferentes.

2) Quantos números de quatro algarismos podemos formar com 3, 4, 5 e 7?

Resolução: Diferentemente do enunciado do exercício 1, esse enunciado não exige que utilizemos os algarismos uma única vez. Desse modo números tais como 2, 34 ou 1555 podem ser contabilizados em nossa contagem, o que anteriormente não era permitido. Desse modo teremos:

Isto é, podemos formar 4 x 4 x 4 x 4 = 4 = 256 números distintos. Se utilizássemos o diagrama da árvore (aqui não indicado pela extensão exagerada), essa árvore apresentaria 256 galhos terminais que representaria cada número formado. (Quem não visualizou que podemos formar 256 números pode tentar fazer o diagrama para notar o resultado, mas novamente, o resultado será imenso).

3) Quantos números de três algarismos formam-se com 0, 1, 2, 3, 4 e 5?

Resolução: o raciocínio é praticamente idêntico ao anterior, mas com uma sutil diferença. Observe:

Esse raciocínio parece perfeito, mas esconde um erro, qual? O problema é justamente o seguinte: Se considerarmos que para a primeira casa há 6 opções de escolha estaremos cometendo um erro, o de considerar um número tal como 012 como sendo um número de três algarismos. Na verdade sabemos que 012 é um número de dois algarismos. Desse modo para corrigirmos nosso raciocínio devemos para primeira casa dispor cinco opções de escolha que são os seis algarismos disponíveis menos o Zero, observe:

Finalmente teremos 5 x 6 x 6 = 5 x 62 = 180 números distintos.

2ª 3ª 4ª
43 2 1

opções

2ª 3ª 4ª
44 4 4

opções

2ª 3ª
66 6

opções

2ª 3ª

Prof. Gerson Henrique 9

Cuidado!Na primeira casa não se pode usar o algarismo 0. Desse modo para a primeira temos 2 opções de

4) Quantos números de três algarismos distintos podem-se formar com 0, 3 e 6? escolha. Já para a segunda também temos duas opções de escolha, uma vez que na segunda o 0 pode aparecer, mas o algarismo usado na primeira casa não pode ser usado novamente. Os algarismos devem ser distintos. Para a terceira e última casa tem-se uma opção de escolha. Desse modo, fica:

Finalmente, temos 2 x 2 x 1 = 4 números distintos.

5) Quantos números pares de quatro algarismos distintos podem-se formar com 0, 1, 2, 5, 6, 8 e 9 ?

Resolução:

A atenção, nesse exercício, deve ser redobrada pelo fato do número formando ter de ser par, isto é, 231 é um número ruim e 234 é um número bom para nossa contagem. 434 também é um número ruim e não deve ser incluído em nossa contagem. Apesar de ser par contém algarismos repetidos, contrariando a restrição acima (algarismos distintos). Vamos começar então dirigindo toda a atenção a última casa da direita, pois sabemos que quando ela contém um algarismo par todo o número será par. Observe

Assim poderíamos concluir rapidamente que podemos obter 4 (4ª casa) x 6 (3ª casa) x 5 (2ª casa) x 4 (1ª casa) que é igual a 4 x 6 x 5 x 4 = 480 números pares.

No entanto, esse raciocínio é falso, por quê ?

O problema esta novamente com o zero! Imagine se por um acaso escolhemos o zero para a última posição. Dessa forma o número seria um par e não começaria com o zero, já que ele ficou na última casa. Se por outro lado, não escolhemos o zero para a última casa criamos, sem intenção, uma dificuldade. Se não aparecer na última casa, o zero não pode aparecer na primeira. Números tais como 0124 são ruins. Desse modo devemos garantir que o zero não apareça na primeira casa. Esse foi o erro do raciocínio anterior. Não garantimos que o zero não apareceria na primeira casa.

Para contornar essa situação vamos dividir esse problema em casos. Isto é, em dois eventos diferentes. Observe:

Como temos que ter atenção redobrada com o zero, consideremos os casos: 1º caso: Números pares terminados em zero; 2º caso: Números pares não terminados em zero. Desse modo não deixaremos de contar nenhum número e nem contaremos a mais.

Vamos aos cálculos 1º caso: Com o zero na última casa

2ª 3ª

3 ou 6 zero não! 2 opções

0 ou (algum que não foi usado na primeira posição) 2 opções resta apenas um algarismo 1 opção

22 1
2ª 3ª 4ª

Existem quatro opções para a escolha, são elas: 0, 2, 6 ou 8.

Prof. Gerson Henrique 10

Desse modo teremos 1 opção para a quarta casa (pois só o zero pode), 6 opções para a terceira casa ( pode qualquer um menos o zero), 5 opções para a segunda casa ( não pode o zero nem o utilizado na terceira cada), 4 opções para a primeira casa (só pode os não utilizados anteriormente). Assim teremos formados 1 x 6 x 5 x 4 números pares terminados em zero.

2º caso: Sem o zero na última casa

Assim na última casa há 3 opções de escolha (todos algarismos pares menos o zero). Agora vamos para a segunda casa problemática – a primeira – nela não se pode inserir nem o algarismo utilizado na última casa nem o zero. Assim teremos 5 opções. Terminando: na segunda 5 opções (nem o utilizado na última nem primeira casa. Zero, nessa casa pode), na terceira 4 opções (qualquer algarismo menos os utilizados anteriormente). Desse modo fica 3 x 5 x 5 x 4 números pares que não terminam em zero.

Finalmente para sabermos quantos números pares podemos formar basta somarmos os resultados do 1º e 2º caso. Teremos:

1 x 6 x 5 x 4 + 3 x 5 x 5 x 4 = 120 + 300 = 420 números pares de quatro algarismos distintos

6) (FJP) Leia atentamente este quadro:

2ª 3ª 4ª

Só pode o zero

2ª 3ª 4ª

não pode o zero

12 3 4

Caros colegas,

Por outro lado, Assim mesmo

Não podemos esquecer que

Do mesmo modo,

A prática mostra que

Nunca é demais insistir, uma vez que

A experiência mostra que

É fundamental ressaltar que

O incentivo ao avanço tecnológico, assim como a execução deste projeto a complexidade dos estudos efetuados a expansão de nossa atividade a atual estrutura da organização o novo modelo estrutural aqui preconizado o desenvolvimento de formas distintas de atuação a constante divulgação das informações a consolidação das estruturas a análise dos diversos resultados o início do programa de formação de atitudes nos obriga à análise cumpre um papel essencial na formulação exige a precisão e a definição auxilia a preparação e a estruturação contribui para a correta determinação assume importantes posições na definição facilita a definição prejudica a percepção da importância oferece uma boa oportunidade de verificação acarreta um processo de reformulação das nossas opções de desenvolvimento no futuro.

das nossas metas financeiras e administrativas.

dos conceitos de participação geral.

das atitudes e das atribuições da diretoria.

das novas proposições.

das opções básicas para o sucesso do programa.

do nosso sistema de formação dos quadros.

das condições apropriadas para os negócios.

dos índices pretendidos.

das formas de ação.

FONTOURA, Walter: Citado por Gaspari, Elio, Estado de Minas, Belo Horizonte, 28 junho 1998

Prof. Gerson Henrique 1

Esse quadro contém o “Guia de discurso para tecnocratas principiantes”. Segundo o autor, basta combinar qualquer expressão da primeira coluna com expressões das outras colunas, observando sempre a ordem 1, 2, 3 e 4 para se falar durante um certo tempo, embora sem se dizer absolutamente nada.

Suponha que sejam necessários 12 segundos, em média, para se proferir cada combinação possível dessas expressões.

(Parte 1 de 7)

Comentários