9 análise+combinatória

Prévia do material em texto

20/05/2014
1
� Análise Combinatória é um conjunto de 
procedimentos que possibilita a construção de grupos 
diferentes formados por um número finito de 
elementos de um conjunto sob certas circunstâncias.
� Arranjos, Permutações ou Combinações, são os três 
tipos principais de agrupamentos, sendo que eles 
podem ser simples, com repetição ou circulares.
Antes disso:
� Lembrar o que é o operador matemático “fatorial” –
símbolo: !
Exemplos Princípio fundamental da 
contagem
� Se determinado acontecimento ocorre em n etapas 
diferentes, e se a primeira etapa pode ocorrer de 
k1 maneiras diferentes, a segunda de k2 maneiras 
diferentes, e assim sucessivamente, então o número 
total T de maneiras de ocorrer o acontecimento é dado 
por:
T = k1. k2 . k3 . ... . kn
20/05/2014
2
Exemplo
� Qual o total de combinações possíveis para placas de 
identificação de veículos no Brasil?
� Quando houve a mudança do sistema de numeração 
de placas, por que aumentaram uma letra e não um 
número?
Arranjos
� São agrupamentos formados com p elementos, (p<m) 
de forma que os p elementos sejam distintos entre sí
pela ordem ou pela espécie. Os arranjos podem ser 
simples ou com repetição.
� Dado o conjunto B dos algarismos B={1,2,3,4}. 
� Qual a quantidade de números naturais de 3 
algarismos que podemos formar utilizando os 
elementos do grupo B?
Uma forma de resolver é a seguinte:
� Esse esquema representa todos os números naturais de 
3 algarismos que podemos formar com os algarismos 
1,2,3,4, portanto, concluindo que é possível formar 24 
agrupamentos.
� Porém, há outra forma de chegarmos a essa conclusão.
20/05/2014
3
Arranjo simples Do exemplo acima:
� m=4;
� p=3.
Exemplo
� Seja Z={A,B,C,D}, m=4 e p=2. Os arranjos simples 
desses 4 elementos tomados 2 a 2 são 12 grupos que 
não podem ter a repetição de qualquer elemento mas 
que podem aparecer na ordem trocada. Todos os 
agrupamentos estão no conjunto:
� As={AB,AC,AD,BA,BC,BD,CA,CB,CD,DA,DB,DC}
� Portanto, é possível formar 12 grupos.
Arranjo com repetição
� Todos os elementos podem aparecer repetidos em cada 
grupo de p elementos.
Exemplo
� Seja C={A,B,C,D}, m=4 e p=2. Os arranjos com 
repetição desses 4 elementos tomados 2 a 2 são 16 
grupos que onde aparecem elementos repetidos em 
cada grupo. Todos os agrupamentos estão no conjunto
� Ar={AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, 
DA, DB, DC, DD}
20/05/2014
4
� Portanto, é possível formar 16 grupamentos.
Arranjo condicional
� Todos os elementos aparecem em cada grupo de p 
elementos, mas existe uma condição que deve ser 
satisfeita acerca de alguns elementos.
� Quantos arranjos com 4 elementos do conjunto 
{A,B,C,D,E,F,G}, começam com duas letras escolhidas 
no subconjunto {A,B,C}?
� Aqui temos um total de m=7 letras, a taxa é p=4, o 
subconjunto escolhido tem m1=3 elementos e a taxa 
que este subconjunto será formado é p1=2.
As duas primeiras letras:
� Com as letras A, B e C, tomadas 2 a 2, temos 6 grupos 
que estão no conjunto:
� PABC = {AB, BA, AC, CA, BC, CB}
� Com as letras D,E,F e G tomadas 2 a 2, temos 12 grupos 
que estão no conjunto:
� PDEFG = {DE, DF, DG, ED, EF, EG, FD, FE, FG, GD, GE, 
GF}
� Aplicando a regra do produto, teremos 72 
possibilidades obtidas pela junção de um elemento do 
conjunto PABC com um elemento do conjunto PDEFG.
Sendo :
20/05/2014
5
� Portanto, são 72 combinações possíveis.
Permutações
� Quando formamos agrupamentos com m elementos, 
de forma que os m elementos sejam distintos entre sí
pela ordem.
� As permutações podem ser simples, com repetição ou 
circulares.
Permutação simples
� São agrupamentos com todos os m elementos 
distintos.
20/05/2014
6
Exemplo:
� Seja C={A,B,C} e m=3. As permutações simples desses 3 
elementos são 6 agrupamentos que não podem ter a 
repetição de qualquer elemento em cada grupo mas 
podem aparecer na ordem trocada.
� Todos os agrupamentos estão no conjunto:
� Ps={ABC, ACB, BAC, BCA, CAB, CBA}
Permutação com repetição
� Dentre os m elementos do conjunto C={x1, x2, x3, ..., 
xn}, faremos a suposição que existem a iguais a x1, b 
iguais a x2, c iguais a x3, ... , n iguais a xn, de modo que 
a+b+c+...=n.
� Se n=a+b+c+..., então:
Anagrama
� Um anagrama é uma (outra) palavra (conjunto de 
caracteres mesmo sem significado) construída com as 
mesmas letras da palavra original trocadas de posição.
Exemplo
� Quantos anagramas podemos formar com as 6 letras 
da palavra ARARAT.
� Observe que a letra A ocorre 3 vezes, a letra R ocorre 2 
vezes e a letra T ocorre 1 vez.
� a=3
� b=2
20/05/2014
7
Permutação circular
� Situação que ocorre quando temos grupos com m 
elementos distintos formando uma circunferência de 
círculo.
Exemplo
� Seja um conjunto com 4 pessoas K={A,B,C,D}. De 
quantos modos distintos estas pessoas poderão sentar-
se junto a uma mesa para realizar o jantar sem que haja 
repetição das posições?
� Se considerássemos todas as permutações simples 
possíveis com estas 4 pessoas, teríamos 24 grupos, 
apresentados no conjunto:
� Pc={ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, 
BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, 
CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, 
DBCA, DCAB, DCBA}
� Acontece que junto a uma mesa "circular" temos que:
� ABCD=BCDA=CDAB=DABC
ABDC=BDCA=DCAB=CABD
ACBD=CBDA=BDAC=DACB
ACDB=CDBA=DBAC=BACD
ADBC=DBCA=BCAD=CADB
ADCB=DCBA=CBAD=BADC
� Existem somente 6 grupos distintos, dados por:
� Pc={ABCD, ABDC, ACBD, ACDB, ADBC, ADCB}
20/05/2014
8
� Sendo m=4:
Combinações
� Quando formamos agrupamentos com p elementos, 
(p<m) de forma que os p elementos sejam distintos 
entre sí apenas pela espécie.
Combinação simples
� Não ocorre a repetição de qualquer elemento em cada 
grupo de p elementos.
� Seja C={A,B,C,D}, m=4 e p=2. As combinações simples 
desses 4 elementos tomados 2 a 2 são 6 grupos que não 
podem ter a repetição de qualquer elemento nem 
podem aparecer na ordem trocada. Todos os 
agrupamentos estão no conjunto:
� Cs={AB, AC, AD, BC, BD, CD}
� Sendo
� m=4
� p=2
Combinação com repetição
� Todos os elementos podem aparecer repetidos em cada 
grupo até p vezes.
20/05/2014
9
Exemplo
� Seja C={A,B,C,D}, m=4 e p=2.
� As combinações com repetição desses 4 elementos 
tomados 2 a 2 são 10 grupos que têm todas as 
repetições possíveis de elementos em grupos de 2 
elementos não podendo aparecer o mesmo grupo com 
a ordem trocada.
� De um modo geral neste caso, todos os agrupamentos 
com 2 elementos formam um conjunto com 16 
elementos:
� Cr={AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, 
DA, DB, DC, DD}
� mas para obter as combinações com repetição, 
deveremos excluir deste conjunto os 6 grupos que já 
apareceram antes, pois AB=BA, AC=CA, AD=DA, 
BC=CB, BD=DB e CD=DC, assim as combinações com 
repetição dos elementos de C tomados 2 a 2, são:
� Cr={AA, AB, AC, AD, BB, BC, BD, CC, CD, DD}
� Sendo:
� m=4
� p=2
Exercícios
� Calcule as chances de acertar as 6 dezenas na 
Megassena apostando 6 dezenas.
20/05/2014
10
Permutação Simples
1) Com as vogais: A,E,I,O e U, quantas permutações 
podem ser formadas contendo as letras: A,E e I.
2) De quantos modos distintos podemos colocar 3 livros 
juntos em uma estante de biblioteca?
3) De quantos modos distintos 5 pessoas podem sentar-
se em um banco de jardim com 5 lugares?
4) Qual é o número possível de anagramas que se pode 
montar com as letras da palavra AMOR?
5) Quantos números com cinco algarismos podemos 
construir com os números ímpares 1,3,5,7,9.
6) Quantos são os anagramas possíveis com as letras: 
ABCDEFGHI?
Permutação com repetição
7) Quantos são os anagramas possíveis com as letras da 
palavra: ARARA?8) Quantos são os anagramas possíveis para a palavra: 
ULYSSES?
9) Quantos são os anagramas possíveis com as letras da 
palavra: MATEMATICA?
Permutações circulares
10) De quantos modos distintos 5 pessoas podem sentar-
se em volta de uma mesa circular?
Combinação Simples
11) Um indivíduo possui 25 livros diferentes. De quantas 
formas distintas ele poderá empacotar tais livros em 
grupos de 6 livros?
12) Em uma sala existem 40 pessoas, 18 mulheres e 22 
homens. Quantas comissões podem ser montadas 
nesta sala contendo 3 mulheres e 5 homens?
Combinação com Repetição
13) Determinar o número de combinações com 4 
elementos tomados com repetição de 7 livros.
14) Determinar o número de combinações com repetição 
de 4 objetos tomados 2 a 2.
20/05/2014
11
Arranjo Simples
15) Quantos números distintos com 2 algarismos 
diferentes, podemos formar com os dígitos: 
0,1,2,3,4,5,6,7,8,9. Números iniciados por 0 (zero) não 
serão considerados como tendo dois algarismos.
16) Usando-se as 26 letras do alfabeto: A,B,C,D,...,Z 
quantos arranjos distintos com 3 letras podem ser 
montados?
Arranjos com repetição
17) Quantos números com 4 algarismos podemos formar 
com os algarismos: 0,1,2,3,4,5,6,7,8 e 9.
18) Quantas placas são possíveis em nosso sistema de 
trânsito, se em todas devem aparecer 3 letras seguidas 
por 4 números?
Arranjos condicionais
19) Quantos arranjos dos elementos A,B,C,D,E,F,G 
tomados 4 a 4, começam com duas letras dentre A,B e 
C?
20) Dentre os arranjos de 6 letras: A,B,C,D,E,F, tomados 
4 a 4, quantos contêm a letra A?