Analise Combinatoria

Análise Combinatória

Professor DEJAHYR LOPES JUNIOR

Introdução: Dados dois conjuntos A = {a1, a2, . . . , am} e B = {b1, b2, b3, . . . , bn}, o total de pares distintos (ai, bj) que podemos formar com os elementos dos dois conjuntos é igual a: b1 a1

n .m

b1

b2 b3

a2

bn n pares

b2

b1

b3 . . . . . . . . . . . . . a m bn

+

n pares + . . . . . . . . . + n pares

n + n + n + . . . + n (m vezes) = n.m

b2 b3

bn

Exemplos 1) Para revestir o piso e a parede de um banheiro um arquiteto pode escolher entre 6 tipos de pisos e 9 tipos de azulejos. Se um tipo de piso pode ser usado com qualquer tipo de azulejo, de quantas maneiras o arquiteto pode combinar o par para revestir o banheiro? Piso = {P1, P2, P3, . . . , P6}

nP = 6

Azulejos = {A1, A2, A3, . . . , A9} npares= 6⋅9

npares= 54

nA = 9

2) Se você vai a um restaurante que oferece 10 pratos diferentes e 6 sucos diferentes, de quantas maneiras você pode fazer uma refeição se você pode tomar ou não suco? Pratos = {P1, P2, P3, . . . , P10}

nP = 10

Sucos = {N1, N2, N3, . . . , N6}

nS = 6

Se você optar por não tomar o suco: no de refeições = 10 Se você optar por tomar o suco: no de refeições = 10⋅6 = 60 Total = 10 + 60 = 70 ou

Tipos de agrupamentos: Arranjos: Importa a ordem e a natureza dos elementos. Permutaçã o:Importa a ordem dos elementos.

Podemos analisar a partir do PFC

Combinaçõe s:Não importa a ordem dos elementos, só a natureza.

Exemplos 1) Com os algarismos 1, 2, 3, 4, 5 e 6, quantos números formados por dois algarismos distintos podem ser formados? Como não é possível repetir algarismos, temos: 6 ⋅ 5 = 30 números 2) Com os algarismos 1, 2, 3, 4, 5 e 6, quantos números formados por dois algarismos podem ser formados? Agora pode repetir algarismos: 6

6 = 36 números

São exemplos de arranjos, o primeiro sem repetição (simples) e o segundo com repetição

Outro exemplo: A frente de um prédio tem 10 portas de entrada. Se uma pessoa, ao entrar no prédio, nunca usa a mesma porta para sair, de quantas maneiras distintas ela pode entrar e sair do prédio?

M a

Entrar Sair 10

x

9 = 90

Se a pessoa entrar e sair por qualquer porta:

M a

10 x 10 = 100

Princípio Fundamental da Contagem Parte 1 Considerando os conjuntos: A = {a1, a2, a3, . . . , am} B = {b1, b2, b3, . . . , bn} C = {c1, c2, c3, . . . , cp} ..................................... X = {x1, x2, x3, . . . , xu}

O total de agrupamentos possíveis do tipo (ai, bj, ck, . . . , xt}

Total = m⋅n⋅p⋅. . . ⋅ u

Exemplo De quantas maneiras diferentes uma moça poderá escolher uma saia, uma blusa, um par de meias e um par de sapatos se ela tem 6 saias, 4 blusas, 2 pares de sapatos e 5 pares de meias?

Saia Blusa Sapatos Meias 6 x 4

x 2

x

5 = 240

Se for possível repetir elementos no agrupamento formado, teremos: p casas

n ⋅

n

⋅

n

⋅ ..............⋅

Total = n⋅n⋅n⋅ . . .⋅n = np

n

Exemplo Calcular quantos números de 4 algarismos distintos podem ser formados usando os algarismos 1, 2, 3, 4, 5, 6. Quem está Não pode estar aqui! aqui!

4 casas 6

x

5

x

4

x

3 = 360

E se fosse possível repetir algarismos?

Quem está Pode estar aqui! aqui!

4 casas 6

x

6

x

6

x

6 = 1296

Calcular quantos números de 5 algarismos distintos podem ser formados usando os algarismos 1, 2, 3, 4, 5, 6. 5 casas = 720 6 x 5 x 4 x 3 x 2 Calcular quantos números de 6 algarismos distintos podem ser formados usando os algarismos 1, 2, 3, 4, 5, 6. 6 casas 6

x

5

x

4

x

3

x

2

x

6 fatorial = 6! = 6x5x4x3x2x1

1

= 720

Observações O preenchimento das casas, apresentado nos exemplos anteriores, é um bom método. Devemos lembrar que o seu uso implica em obter agrupamentos diferentes quando mudamos a ordem dos elementos do agrupamento. Como vimos: 0! = 1, 1! = 1 Lembremos como simplificar frações envolvendo fatorial 12! 8!

12⋅11⋅10⋅9⋅ = = 11880 8! 8! Desenvolvemos o maior fatorial até chegar no menor e simplificamos.

Arranjos ou Arranjos Simples Vamos considerar o exemplo: Dado um conjunto de 5 pessoas e vamos escolher 3 delas para formarmos uma diretoria. A primeira escolhida será presidente, a segunda vice e a terceira secretária. De quantas formas isso poderá ser feito? Pessoas = {a, b, c, d, e} abc acb bac bca cab cba

abd adb bad bda dab dba

abe aeb bae bea eab eba

acd adc cad cda dac dca

ace aec cae cea eac eca

ade aed dae dea ead eda

bcd bdc cbd cdb dbc dcb

bce bec cbe ceb ebc ecb

bde bed dbe deb ebd edb

cde ced dce dec ecd edc

abc acb bac bca cab cba abc ≠ abd

abd adb bad bda dab dba

abe aeb bae bea eab eba

acd adc cad cda dac dca

ace aec cae cea eac eca

ade aed dae dea ead eda

bcd bdc cbd cdb dbc dcb

bce bec cbe ceb ebc ecb

bde bed dbe deb ebd edb

cde ced dce dec ecd edc

Porque tem elementos diferentes (c ≠ d)

Isso é chamado de diferença na natureza dos elementos. abc ≠ acb

Porque os elementos ocupam posições diferentes; b é vice em abc e secretária em acb e c é exatamente o contrário. Isso é chamado de diferença na ordem dos elementos.

Arranjos são agrupamentos que diferem entre si na ordem ou na natureza de seus elementos. No caso anterior, como tiramos de um conjunto de 5 elementos 3 deles para compor uma diretoria, temos “Arranjos de 5 elementos tomados 3 a 3.” Quantidade de elementos agrupados. Logo, para reconhecer se os agrupamentos formados 5,3 = ou não, é só escrever um deles e mudar a são arranjos Total de possíveis ordem de elementos distintos que o compõe. diretorias a seremSe o novo agrupamento obtido for diferente do anterior, temos formadas. Quantidade de elementos ARRANJOS, se o agrupamento obtido for igual ao Simbolizado“Arranjo”. conjunto dado. escrito, não temos ARRANJOS.

A

60

Vamos considerar alguns exemplos Quantos números pares formados por 4 algarismos distintos podem ser feitos usando os algarismos 1, 2, 3, 4, 5, 6, 7? O conjunto do Usaremos 4 deles, ou seja teremos 4 qual tiraremos casas para serem preenchidas. os elementos tem Par 7 termos(n = 7) 6 5 4 3 Ou pela fórmula do Arranjo:

A6,3 =

6! 6! = = 6.5.4 = 120 (6 − 3)! 3!

Assim: 120.3 = 360

6x5x4x3 = 360 Devemos sempre preencher a casa condicionada

Considerando que as placas de um carro tem 3 letras e 4 algarismos e que as letras são retiradas de um alfabeto que tem 26 letras distintas, determinar quantas placas existem formadas por letras distintas e algarismos distintos.

26

25

24

10

9

8

7

26x25x24x10x9x8x7 = 78.624.000 Se for possível repetir letras ou algarismos será possível emplacar 175.760.000 veículos auto-motores. Vocês já imaginaram quantos veículos auto-motores tem no Brasil?

Com os algarismos 1, 2, 3, 4, 5, 6, 7, 8, 9 quantos números com algarismos distintos existem de 1 até 1000? De 1 até 1000 temos números com 1 algarismo, ou 2 ou 3. Com 1 algarismo: Com 2 algarismos: Com 3 algarismos:

9 9

x 8

= 72

9

x 8 x

7 = 504

Total = 9 + 72 + 504 = 585

Uma pessoa esqueceu sua senha bancária de 6 dígitos, porém, lembra que os dois primeiros dígitos são letras distintas e vogais e os quatro últimos são algarismos pares e distintos. Quantas tentativas ela terá que fazer, no máximo, se for possível, para acertar a senha?

5

x 4 Letras

x

5

x

4 x 3 x Algarismos

Total = 2400

2

Permutações Simples Permutações são agrupamentos feitos com todos os elementos de um conjunto dado sendo que cada agrupamento difere dos demais apenas pela ordem de seus elementos. Dado um conjunto com n elementos vamos fazer todos os arranjos possíveis com n elementos. . . . n. .casas ....... n (n – 1)(n – 2)

3

Pn  n!

2

1

Na figura temos 4 meninos e uma menina prontos para entrarem no clubinho dos meninos. Logicamente é um dia atípico, visto que a entrada de meninas é proibida, principalmente sendo a Mônica. Mas vão entrar. Se Jeremias é um perfeito cavalheiro e só entra após a Mônica, de quantas maneiras diferentes os cinco podem entrar no clubinho.

(Revista Mônica No 186 – Editora Globo)

Calcular a quantidade de anagramas que podem ser formados com as letras da palavra BRASIL. Brasil tem 6 letras diferentes e todas serão usadas 6 x 5 x 4 x 3 x 2 x 1 P6 = 6! = 720 De quantas maneiras diferentes 6 pessoas podem fazer uma fila se duas delas (A e B) pretendem ficar uma ao lado da outra? Consideramos as duas pessoas (A e B) como uma só. Pode ser B e A.

2 x 5

4

3

2

1 = 5! = 240

Formados e dispostos em ordem crescente todos os números que se obtém permutando os algarismos 1, 3, 4, 5 e 8, qual é o lugar ocupado pelo número 54831? Vamos 1 procurar quantos são os números menores do que 54831

P4 = 4! = 24

3

P4 = 4! = 24

4

P4 = 4! = 24

Total: 89

5

1

P3 = 3! = 6

5

3

5

4

1

5

4

3

5

4

8

P3 = 3! = 6 menores. P2 = 2! = 2 Lugar ocupado P2 = 2! = 2 o 90 P = 1! = 1

1

1

Combinações Simples ou Combinações Vamos considerar o exemplo: Dado um conjunto de 5 pessoas, vamos escolher 3 delas para formarmos uma comissão. Pessoas = {a, b, c, d, e} abc abd abe acd ace ade bcd bce bde cde Se mudarmos os elementos de lugar nos agrupamentos, os mesmos não mudam. A comissão abc é a mesma acb. abc = bac

A ordem não muda o agrupamento.

abc ≠ abd

Os agrupamentos são diferentes na natureza dos elementos.

Como calcular o total de combinações simples? Vamos considerar o exemplo de cálculo de arranjo de 5 tomados 3 a 3. abc

abd

abe

acd

ace

ade

bcd

bce

bde

cde

acb

adb

aeb

adc

aec

aed

bdc

bec

bed

ced

bac

bad

bae

cad

cae

dae

cbd

cbe

dbe

dce

bca

bda

bea

cda

cea

dea

cdb

ceb

deb

dec

cab

dab

eab

dac

eac

ead

dbc

ebc

ebd

ecd

cba

dba

eba

dca

eca

eda

dcb

ecb

edb

edc

Vamos observar que de cada coluna aproveitamos apenas uma combinação. C53

A 53

5.4.3    10 6 6

6 = 3!

“Número de casas” fatorial

Combinações são agrupamentos que diferem entre si apenas na natureza de seus elementos. Na formação das comissões tínhamos 5 elementos no conjunto e escolhemos apenas 3. 5

x

4

x

3

=

5.4.3

= 10

3! 3.2.1 Quantidade de elementos agrupados. 5! 5.4.3! comissões = Total de possíveis = = 10 2!3!a serem formadas. 5,3 (5 – 3)!.3!

C

Quantidade de elementos do conjunto dado.

Exemplos

Um químico possui 10 tipos de substâncias. De quantos modos possíveis poderá associar 6 dessas substâncias se, entre as dez, duas somente não podem ser juntadas porque produzem misturas explosivas. Trocando as duas incompatíveis!!! Não usando!!! Não usando uma e usando a outra!!! Perigo 8! 8.7.6! 6 C8  6 serão misturadas   28 (8  6)!6! 2!.6! 8! 8.7.6.5! 5 C8    56 (8  5)!5! 2!.5! 8! 8.7.6.5! 5 C8    56 (8  5)!5! 2!.5!

28 + 56 + 56 = 140

Permutação com repetição

Para calcular a permutação de n elementos com repetição de um deles α Partindo do exemplo: calcular o total de anagramas que podem ser vezes, outro βvezes, outro γ vezes e assim sucessivamente, até um µ formados com as letras da palavra PIRACICABA. vezes tem-se a fórmula: A palavra tem 10 letras. diferentes a quantidade de ,, Se ,...,todas  fossemn! Pna 10! = 10.9.8.7.6.5.4.3.2.1  anagramas seria igual = 3.628.800

 ! !  !... !

A letra A aparece 3 vezes. Mudando o A de lugar com ele mesmo, obtém-se 6 palavras (3!) das quais aproveita-se uma. A letra I aparece 2 vezes, logo, mudando de lugar o I com ele obtém-se 2 palavras (2!) e aproveita-se apenas uma, o mesmo ocorre (2) com a letra C.

3,2,2 3.628.800 10! P10 = = = 151.200 6.2.2 3! 2! 2!

De quantas maneiras diferentes podemos distribuir 9 cartas distintas de um baralho em 3 montinhos distintos? 1

2

3

4

5

6

7

Grupo 1

Grupo 2

Grupo 3

3 C9

3 C6

3 C3

x

x

8

9

= 280

3! Mudando um grupo de lugar com outro não acarreta mudança na distribuição.

Permutação Circular De quantas maneiras diferentes n pessoas podem se colocar em uma fila circular?

Pn = (n – 1)! ’

Arranjos Completos Tratando-se de arranjos completos podemos ter elementos repetidos nos agrupamentos. Exemplo: Não existe restrição para numerar uma placa de veículos auto motores. A placa é formada por 3letras de um alfabeto de 26 letras e quatro algarismos escolhidos de zero a nove (10 algarismos).

3 Letras

4 Algarismos

26 x 26 x 26 x 10 x 10 x 10 x 10 = 175.760.000 Placas

p

AR(n,p)  A '(n,p)  n

Combinações Completas

Tratando-se de combinações repetidos nos agrupamentos.

completas

podemos

ter

elementos

As Combinações Completas são pouco usadas nos diversos problemas que temos visto ao longo dos nossos estudos.

(n  p  1)! CR(n,p)  C'(n,p)  (n  1)!p!