Análise combinatória

Análise Combinatória

• Problemas análise combinatória são problemas de contagem.

Princípio Fundamental da Contagem – PFC (ou Princípio Multiplicativo)

SE um acontecimento ocorre em n etapas diferentes, e se cada etapa i ocorrer de ki maneiras diferentes ENTÃO o número total T de maneiras de ocorrer o acontecimento é dado por:

Aulas de Matemática / Física / Química – Contato: Horacimar (21) 9-8126-2831 [email protected]


• T = k1.k2.k3. ... ki ....kn ; i=1,2,3,...,n • Exemplo: Placa Detran 3 Letras / 4 algarismos • Alfabeto 26 letras s ; Algarismos 0..9 são 10 • T = 26.26.26.10.10.10.10 = 175.760.000 combinações s (Podem ocorrer repetição de algarismos: Por exemplo: Placa KKK-7777) Aulas de Matemática / Física / Química – Contato: Horacimar (21) 9-8126-2831 [email protected]


Exercício: Um salão tem 6 portas. De quantos modos distintos

esse salão pode estar aberto?

Solução: Para a primeira porta temos duas opções: aberta ou fechada Para a segunda porta temos também, duas opções, e assim sucessivamente. Para as seis portas, teremos então, pelo Princípio Fundamental da Contagem - PFC:

N = 2.2.2.2.2.2 = 64 Lembrando que uma dessas opções corresponde a todas as duas portas fechadas, teremos então que o número procurado é igual a 64 - 1 = 63.

Resposta: o salão pode estar aberto de 63 modos possíveis


Análise Combinatória Fatorial • Seja n um número positivo pertencente ao conjunto dos números Naturais (n N), então n! (lê-se “ene fatorial”) é igual a:

n! = n.(n-1).(n-2).(n-3)...1 5! = 5.4.3.2.1 = 120 Propriedades: 0! = 1 e 1!=1


Análise Combinatória Permutação Simples • Formado por n elementos distintos (s ) que são agrupados e diferem um dos outros pela ordem de seus elementos. (Os conjuntos obtidos são chamados de Anagramas) • Calculado por Pn = n! = n.(n-1).(n-2)...2.1, n N


Análise Combinatória Exemplo: 3 elementos {A, B, C} P3 = 3! = 3.2.1 = 6 combinações ABC, ACB, BCA, BAC, CAB, CBA => 6 Anagramas Quantos números com 5 algarismos distintos podemos formar c/ 1, 2, 3, 4, 5 : P5 = 5! = 120 Quantos são os anagramas da palavra “Cola” => A palavra possui 4 letras diferentes, logo o número de anagramas é dados por P4 = 4! = 24 Aulas de Matemática / Física / Química – Contato: Horacimar (21) 9-8126-2831 [email protected]

Análise Combinatória O número de anagramas da palavra ESTUDAR que começam e terminam com vogal: Vamos analisar os casos: E_ _ _ _ _ U U_ _ _ _ _ E A_ _ _ _ _ E E_ _ _ _ _ A U_ _ _ _ _ A A_ _ _ _ _ U Cada um resulta em P5 = 5! Anagramas, logo no total teremos 6.5! = 6.120 = 720 anagramas s (Total de anagramas de ESTUDAR P7 = 7! = 5.040) Aulas de Matemática / Física / Química – Contato: Horacimar (21) 9-8126-2831 [email protected]

Análise Combinatória Permutação com elementos repetidos • Se entre os n elementos de um conjunto existem a elementos repetidos, b elementos repetidos e assim sucessivamente, então o número total de permutações é dado por: • Calculado por

!...!

!,...,

ba

nP ba

n


Análise Combinatória • Anagrama de MATEMATICA • n = 10 letras

200.151!2!.3!.2

!3.4.5.6.7.8.9.10

!2!.3!.2

!102,3,2

10P

a = 2 2x M

b = 3 3x A

c = 2 2x T


Análise Combinatória • Exemplo: Quantos números de cinco algarismos podemos escrever

com os dígitos 1, 1, 2, 2 e 3, respeitadas as repetições apresentadas ? •Solução: Caso de permutação com repetição •O número de combinações possíveis será 30.

30!2!.2

!2.3.4.5

!2!.2

!522,21

5 nnP


Análise Combinatória Permutações circulares • O número de permutações circulares de n elementos é dado por: • Calculado por

)!1(, nP


Análise Combinatória Arranjos Simples • Dado um conjunto de n elementos, chama-se arranjo simples de k elementos, a todo agrupamento de k elementos distintos numa certa ordem. •Atenção: Não há repetição de elementos; a ordem dos elementos é considerada (A ORDEM É IMPORTANTE).

Calcula-se o número de arranjo simples: (arranjo de n

elementos tomados k a k)

)!(

!,

kn

nA kn


Análise Combinatória • A Permutação Simples é um caso especial de Arranjo Simples quando o número de elementos tomados k = n (tamanho do conjunto) • Problemas de Arranjos Simples também poderão ser resolvidos pelo Princípio Fundamental da Contagem. Você poderá optar por aquele processo que achar mais conveniente.

!

!1

!

!0

!

)!(

!

,

,

nPA

nnn

nn

nA

nnn

nn


Análise Combinatória • Exemplo: Quantos números de três algarismos distintos podemos formar com os elementos do conjunto {1, 2, 3 ,4, 5} ? • ou: pelo Princípio Fundamental da Contagem Portanto, poderemos formar 60 números com três algarismos distintos.

60!2

!2.3.4.5

!2

!5

)!35(

!53,5

A

603.4.5 T


Análise Combinatória • Exemplo: Três rapazes e duas moças vão ao cinema e desejam

sentar-se, os cinco, lado a lado, na mesma fila. O número de maneiras diferentes que eles podem sentar-se em uma mesma fila de modo que as moças fiquem todas juntas é igual a: • Solução: São 5 lugares e as moças ficam sempre juntas (A ORDEM É IMPORTANTE) •1 caso: M M H H H : 3! = 3.2.1 = 6 opções para os rapazes (A3,3=3!=6)

•2 caso: H M M H H : 3! = 3.2.1 = 6 opções para os rapazes (A3,3=3!=6)

•3 caso: H H M M H : 3! = 3.2.1 = 6 opções para os rapazes (A3,3=3!=6)

•4 caso: H H H M M : 3! = 3.2.1 = 6 opções para os rapazes (A3,3=3!=6)

•Devemos lembrar agora que são 2 mulheres, então elas poderão revezar de lado (2 opções = A2,2 = 2! = 2). • Logo o número de combinações será: 4x6x2 = 48 maneiras s de sentar.


Análise Combinatória • Exemplo: O número de maneiras diferentes que três rapazes e duas

moças podem sentar-se em uma mesma fila de modo que somente as moças fiquem todas juntas é igual a: •Solução: São 5 lugares e SOMENTE as moças ficam sempre juntas • Temos somente os seguintes casos: •1 caso: H M M H H : 3! = 3.2.1 = 6 opções para os rapazes •2 caso: H H M M H : 3! = 3.2.1 = 6 opções para os rapazes •Devemos lembrar agora que são 2 mulheres, então elas poderão revezar de lado (2 opções). • Logo o número de combinações será: 2x6x2 = 24 maneiras s de sentar.


Análise Combinatória • Com os algarismos 0, 1, 2, 5 e 6 sem os repetir, quantos números compreendidos entre 100 e 1.000 poderemos formar ? • Os números serão de 3 algarismos

• Não pode haver repetição => a ordem é importante (ARRANJO SIMPLES)

• Núm. Iniciados por 1: 1_ _ => A4,2 = 12 • Núm. Iniciados por 2: 2_ _ => A4,2 = 12 • Núm. Iniciados por 5: 5 _ _=> A4,2 = 12 • Núm. Iniciados por 6: 6 _ _=> A4,2 = 12

• O NÚMERO TOTAL É 4.12 = 48 •RESOLVENDO PELO PRINCÍPIO FUNDAMENTAL DA CONTAGEM:

T = 4.4.3 = 48 Na 1ª opção temos 4 opções (não pode ser zero), na 2ª opção temos 4 opções (3 + 1 do zero), 3ª opção temos 3 (2 + 1 do zero). Aulas de Matemática / Física / Química – Contato: Horacimar (21) 9-8126-2831 [email protected]

Análise Combinatória • Exemplo: Quantos números entre 30.000 e 65.000 distintos com os

algarismos {2, 3, 4, 6, 7} podemos formar ? •Solução: A ORDEM É IMPORTANTE => ARRANJO SIMPLES •Para resolvermos o problema fica mais fácil separar dos números em duas faixas: de 30.000 a 60.000 e de 60.000 a 65.000 porque não é possível impor uma restrição para o segundo dígito sem incorrer com a perda de combinações de números {6, 7} no 2º dígito.

•Primeiro iremos resolver pelo PFC e depois pela fórmula de Arranjo Simples: •Temos 5 algarismos que devem ser distintos entre 30.000 e 60.000 •Se não tivéssemos a condição do intervalo teríamos a seguinte condição:


Análise Combinatória •1º algarismo: 5 opções (temos 5 opções de números) •2º algarismo: 4 •3º algarismo: 3 •4º algarismo: 2 •5º algarismo: 1 • Contudo para obedecer à condição de estar entre 30.000-60.000 os números possíveis para o 1º algarismo são {3, 4}, ou seja, 2 opções. Então para a faixa de 30.000-60.000 podemos formar T1=2x4x3x2x1=48; • Para a faixa 60.000-65.000, aplicando o mesmo princípio, ficaríamos:


Análise Combinatória •1º algarismo: 5 opções •2º algarismo: 4 •3º algarismo: 3 •4º algarismo: 2 •5º algarismo: 1 • Contudo para obedecer à condição de estar entre 60.000-65.000 o único número possível para o 1º algarismo é {6}, portanto 1 opção. O segundo algarismo somente pode comportar {2, 3, 4}, portanto 3 opções. Logo para a faixa de 60.000-65.000 podemos formar T2=1x3x3x2x1=18; • Por fim, ficamos com um total de T1 + T2 = 48 + 18 = 66 formas diferentes.


Análise Combinatória •Resolvendo por fórmula também devemos fazer a separação das duas faixas: • Na primeira faixa ficamos: A5,5 – 3.A4,4 {devido aos números 2, 6, 7} que ficaram no 1º algarismo; •Na segunda faixa ficamos: A4,4-A3,3 {devido o número 7 que pode ocorrer no 2º dígito} •No total ficamos com: A5,5 – 3.A4,4 + A4,4-A3,3 = 5! – 2.4! – 3! = 120 - 48 - 6 = 66 •Pelo PFC fica muito mais fácil resolver problemas de arranjo simples e fazer os cálculos!


Análise Combinatória • Exemplo: Sete modelos entre elas Ana, Beatriz, Carla e Denise vão

participar de um desfile de modas. A promotora do desfile determinou que as modelos não desfilarão sozinhas, mas sempre em filas de quatro modelos. Além disso, a última da fila podem ser somente Ana, Beatriz, Carla, Denise e a Denise não pode ocupar o primeiro lugar da fila. Quantas combinações diferentes podemos formar de modo que as filas fiquem todas distintas ? •Solução: A ORDEM É IMPORTANTE => ARRANJO SIMPLES •Neste exemplo devemos notar que em 3 casos teremos como restrição o fim da fila podendo ser formado pela Ana, Beatriz e Carla e a 1ª não sendo a Denise. No 4º caso teremos a Denise em último lugar e nenhuma restrição para o 1º lugar.


Análise Combinatória •Pelo PFC temos:

• 1º lugar: 6 opções • 2º lugar: 5 • 3º lugar: 4

•No 1º lugar devemos tirar 1 opção para evitar que a Denise a ocupe. Portanto, Temos 5x5x4 = 100 combinações. Para 3 casos serão 300 combinações; •No 4º caso teremos 6 opções e 3 lugares, então 6x5x4 = 120; •Portanto, no total formaremos 420 filas diferentes. •Por fórmula ficaremos com: 3x(A6,3 - A5,2)+A6,3 = 3x(120 - 20)+120 = 420.


Análise Combinatória Arranjo com Repetição • O número de arranjos com repetição de n elementos k a k é dado por:

k

kn nA *

,


Análise Combinatória Arranjo com Repetição Uma placa de motocicleta contenha duas letras distintas do alfabeto completo, seguida por três dígitos. Quantas placas diferentes podem ser impressas ? Pelo PFC: 26.25.10.10.10 = 650.000

000.65010.25.2610.!24

!26. 33*

3,102,26 AA


Análise Combinatória Combinação Simples • É a combinação de n elementos distintos tomados k a k aos subconjuntos formados por k elementos distintos escolhidos entre os n elementos. São agrupamentos onde a ordem com que os elementos comparecem não é considerada.

•Exemplo: Seja o conjunto formado por {a, b, c, d} •O número de combinações tomados 2 a 2:

• {ab, ac, ad, bc, bd, cd}


Análise Combinatória Combinação Simples •Exemplo: Seja o conjunto formado por {a, b, c, d} •O número de combinações tomados 3 a 3:

• {abc, abd, acd, bcd} • O número de combinações tomados 4 a 4:

• {abcd}

* Repare que agora, se mudarmos a posição dos elementos em um

agrupamento não obteremos um novo agrupamento. Isto é a dupla ab é igual à dupla ba. Ou seja, A ORDEM NÃO É IMPORTANTE!


Análise Combinatória Combinação Simples • É calculado como: •Exemplo:

k

n

kkn

nC kn

!)!(

!,

452

9.10

1.2!.8

!8.9.10

!2!.8

!10

!2)!210(

!102,10

C


Análise Combinatória Combinação Simples • Macete:

knC ,k números em cima de n, e k números embaixo de k

451.2

9.102,10 C

kn

n

k

nk n

452

10

8

102,108,10

CC


Análise Combinatória • Exemplo: Em uma prova de 15 questões o aluno deve resolver 10 questões. De quantas formas pode escolher as 10 questões: •Obs.: A ordem não é importante => Combinação Simples

!10!5

!15

!10)!1015(

!15

!)!(

!10,15

kkn

nC

3.003!10.1.2.3.4.5

!10.11.12.13.14.15

!10!5

!1510,15 C


Análise Combinatória • Exemplo: Quantas comissões formadas de 4 elementos cada uma podemos formar com 10 alunos de uma classe ? •Obs.: A ordem não é importante => Combinação Simples

2101.2.3.4!6

!6.7.8.9.10

!4!6

!10

!4)!410(

!104,10

C

2101.2.3.4

7.8.9.104,10 C


Análise Combinatória • Exemplo: Uma organização dispõe de 10 economistas e 6

administradores. Quantas comissões de 6 pessoas podem ser formadas

de modo que cada comissão tenha no mínimo 3 administradores ?

•Obs.: A ordem não é importante => Combinação Simples Teremos que considerar as seguintes considerações: 3 Adm. e 3 Econ. : C6,3 x C10,3 = 20. 120 = 2.400 4 Adm. e 2 Econ. : C6,4 x C10,2 = 15. 45 = 675 5 Adm. e 1 Econ. : C6,5 x C10,1 = 6.10 = 60 6 Adm. e 0 Econ.: C6,6 x C10,0 = 1.1 = 1

Logo o total de comissões que poderemos formar será então:

2.400 + 675 + 60 + 1 = 3.136 comissões


Análise Combinatória • Exemplo: Em um grupo de dança participam dez meninos e dez

meninas. O número de diferentes grupos de cinco crianças que podem ser formadas de modo que em cada um dos grupos participem três meninos e duas meninas é dado por: Solução: Observe que a não é dito como os meninos ou meninas serão escolhidos, somente o número de cada. Neste caso, temos que a ORDEM NÃO É IMPORTANTE!. Logo, é COMBINAÇÃO SIMPLES. Devemos formar um grupo de 5 com 3 meninos e 2 meninas: Logo: C10,3 x C10,2 =

400.545.1201.2

9.10.

1.2.3

8.9.10


Análise Combinatória Combinação Simples Resolva a equação C19,x = 3.C19,x-1

1,19,19 .3 xx CC

)!1()]!1(19[

!19.3

!)!19(

!19

xxxx

)!1()]!1(19[

!19.3

!)!19(

!19

xxxx


Análise Combinatória Combinação Simples

)!1()!19).(20(

!19.3

)!1.()!19(

!19

xxxxxx

xx

20

1.3

1

5204320 xxxx


Análise Combinatória Combinação Simples O valor de Cn,0 + Cn,1+ Cn,2 + ...+ Cn,n-1 com nN* :

1

1

1 k

n

k

n

k

nRelação de Stifel

n

n

n

n

nnnn2

1...

210

Cn,0 + Cn,1+ Cn,2 + ...+ Cn,n-1 = 2n - 1

Triângulo de Pascal


Análise Combinatória Combinação Simples – Com REPETIÇÃO • O número de combinações com repetição de n elementos k a k é dado por:

!)!1(

)!1(1,1,

*

kn

kn

k

knCC kknkn


Análise Combinatória Combinação Simples – Com REPETIÇÃO • Exercício: De quantas maneiras, uma oficina pode pintar 5 automóveis iguais, recebendo cada um, tinta de uma única cor, se a oficina dispõe apenas de 3 cores e não quer misturá-las ? •Solução: Como são 5 automóveis iguais, a ordem que irão pintar eles não importa (Combinação Simples). Necessariamente irá ocorrer repetição de cor, pois são 5 carros e apenas 3 cores:

211.2

6.72,75,75,1535,3

* CCCC


Education

Análise combinatória