cead20136

quarta-feira, 7 de setembro de 2016

Análise Combinatório

Professor de Matemática Antonio Carlos Carneiro Barroso
Colégio Estadual Dinah Gonçalves
email accbarroso@hotmail.com


Extraido do colaweb

► Análise Combinatória


Introdução

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.

Na maior parte das vezes, tomaremos conjuntos Z com m elementos e os grupos formados com elementos de Z terão p elementos, isto é, p será a taxa do agrupamento, com p
Combinação simples: Não ocorre a repetição de qualquer elemento em cada grupo de p elementos.

Fórmula: C(m,p) = m!/[(m-p)! p!]

Cálculo para o exemplo: C(4,2)=4!/[2!2!]=24/4=6

Exemplo: 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}


Número de Arranjos simples

Seja C um conjunto com m elementos. De quantas maneiras diferentes poderemos escolher p elementos (p
c1, c2, c3, c4, c5, ..., cm-2, cm-1, cm

Cada vez que um elemento for retirado, indicaremos esta operação com a mudança da cor do elemento para a cor vermelha.

Para escolher o primeiro elemento do conjunto C que possui m elementos, temos m possibilidades. Vamos supor que a escolha tenha caído sobre o m-ésimo elemento de C.

c1, c2, c3, c4, c5, ..., cm-2, cm-1, cm

Para escolher o segundo elemento, devemos observar o que sobrou no conjunto e constatamos que agora existem apenas m-1 elementos. Suponhamos que tenha sido retirado o último elemento dentre os que sobraram no conjunto C. O elemento retirado na segunda fase é o (m-1)-ésimo.

c1, c2, c3, c4, c5, ..., cm-2, cm-1, cm

Após a segunda retirada, sobraram m-2 possibilidades para a próxima retirada. Do que sobrou, se retirarmos o terceiro elemento como sendo o de ordem (m-2), teremos algo que pode ser visualizado como:

c1, c2, c3, c4, c5, ..., cm-2, cm-1, cm

Se continuarmos o processo de retirada, cada vez teremos 1 elemento a menos do que na fase anterior. Para retirar o p-ésimo elemento, restarão m-p+1 possibilidades de escolha.

Para saber o número total de arranjos possíveis de m elementos tomados p a p, basta multiplicar os números que aparecem na segunda coluna da tabela abaixo:


Retirada
Número de possibilidades

1
m

2
m-1

3
m-2

...
...

p
m-p+1

No.de arranjos
m(m-1)(m-2)...(m-p+1)



Denotaremos o número de arranjos de m elementos tomados p a p, por A(m,p) e a expressão para seu cálculo será dada por:

A(m,p) = m(m-1)(m-2)...(m-p+1)

Exemplo: Consideremos as 5 vogais de nosso alfabeto. Quais e quantas são as possibilidades de dispor estas 5 vogais em grupos de 2 elementos diferentes? O conjunto solução é:

{AE,AI,AO,AU,EA,EI,EO,EU,IA,IE,
IO,IU,OA,OE,OI,OU,UA,UE,UI,UO}

A solução numérica é A(5,2)=5×4=20.

Exemplo: Consideremos as 5 vogais de nosso alfabeto. Quais e quantas são as possibilidades de dispor estas 5 vogais em grupos de 2 elementos (não necessariamente diferentes)?

Sugestão: Construir uma reta com as 5 vogais e outra reta paralela à anterior com as 5 vogais, usar a regra do produto para concluir que há 5x5=25 possibilidades.

O conjunto solução é:

{AA,AE,AI,AO,AU,EA,EE,EI,EO,EU,IA,IE,II,
IO,IU,OA,OE,OI,OO,OU,UA,UE,UI,UO,UU}

Exemplo: Quantas placas de carros podem existir no atual sistema brasileiro de trânsito que permite 3 letras iniciais e 4 algarismos no final?

XYZ-1234

Sugestão: Considere que existem 26 letras em nosso alfabeto que podem ser dispostas 3 a 3 e 10 algarismos que podem ser dispostos 4 a 4 e em seguida utilize a regra do produto.


Número de Permutações simples

Este é um caso particular de arranjo em que p=m. Para obter o número de permutações com m elementos distintos de um conjunto C, basta escolher os m elementos em uma determinada ordem. A tabela de arranjos com todas as linhas até a ordem p=m, permitirá obter o número de permutações de m elementos


Retirada
Número de possibilidades

1
m

2
m-1

...
...

p
m-p+1

...
...

m-2
3

m-1
2

m
1

No.de permutações


m(m-1)(m-2)...(m-p+1)...4.3.2.1


Denotaremos o número de permutações de m elementos, por P(m) e a expressão para seu cálculo será dada por:

P(m) = m(m-1)(m-2) ... (m-p+1) ... 3 . 2 . 1

Em função da forma como construímos o processo, podemos escrever:

A(m,m) = P(m)

Como o uso de permutações é muito intenso em Matemática e nas ciências em geral, costuma-se simplificar a permutação de m elementos e escrever simplesmente:

P(m) = m!

Este símbolo de exclamação posto junto ao número m é lido como: fatorial de m, onde m é um número natural.

Embora zero não seja um número natural no sentido que tenha tido origem nas coisas da natureza, procura-se dar sentido para a definição de fatorial de m de uma forma mais ampla, incluindo m=0 e para isto podemos escrever:

0!=1

Em contextos mais avançados, existe a função gama que generaliza o conceito de fatorial de um número real, excluindo os inteiros negativos e com estas informações pode-se demonstrar que 0!=1.

O fatorial de um número inteiro não negativo pode ser definido de uma forma recursiva através da função P=P(m) ou com o uso do sinal de exclamação:

(m+1)! = (m+1).m!, 0! = 1

Exemplo: De quantos modos podemos colocar juntos 3 livros A, B e C diferentes em uma estante? O número de arranjos é P(3)=6 e o conjunto solução é:

P={ABC,ACB,BAC,BCA,CAB,CBA}

Exemplo: Quantos anagramas são possíveis com as letras da palavra AMOR? O número de arranjos é P(4)=24 e o conjunto solução é:

P={AMOR,AMRO,AROM,ARMO,AORM,AOMR,MARO,MAOR,
MROA,MRAO,MORA,MOAR,OAMR,OARM,ORMA,ORAM,
OMAR,OMRA,RAMO,RAOM,RMOA,RMAO,ROAM,ROMA}


Número de Combinações simples

Seja C um conjunto com m elementos distintos. No estudo de arranjos, já vimos antes que é possível escolher p elementos de A, mas quando realizamos tais escolhas pode acontecer que duas coleções com p elementos tenham os mesmos elementos em ordens trocadas. Uma situação típica é a escolha de um casal (H,M). Quando se fala casal, não tem importância a ordem da posição (H,M) ou (M,H), assim não há a necessidade de escolher duas vezes as mesmas pessoas para formar o referido casal. Para evitar a repetição de elementos em grupos com a mesma quantidade p de elementos, introduziremos o conceito de combinação.

Diremos que uma coleção de p elementos de um conjunto C com m elementos é uma combinação de m elementos tomados p a p, se as coleções com p elementos não tem os mesmos elementos que já apareceram em outras coleções com o mesmo número p de elementos.

Aqui temos outra situação particular de arranjo, mas não pode acontecer a repetição do mesmo grupo de elementos em uma ordem diferente.

Isto significa que dentre todos os A(m,p) arranjos com p elementos, existem p! desses arranjos com os mesmos elementos, assim, para obter a combinação de m elementos tomados p a p, deveremos dividir o número A(m,p) por m! para obter apenas o número de arranjos que contem conjuntos distintos, ou seja:

C(m,p) = A(m,p) / p!

Como

A(m,p) = m.(m-1).(m-2)...(m-p+1)

então:

C(m,p) = [ m.(m-1).(m-2). ... .(m-p+1)] / p!

que pode ser reescrito

C(m,p)=[m.(m-1).(m-2)...(m-p+1)]/[(1.2.3.4....(p-1)p]

Multiplicando o numerador e o denominador desta fração por

(m-p)(m-p-1)(m-p-2)...3.2.1

que é o mesmo que multiplicar por (m-p)!, o numerador da fração ficará:

m.(m-1).(m-2).....(m-p+1)(m-p)(m-p-1)...3.2.1 = m!

e o denominador ficará:

p! (m-p)!


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

Exemplo:

O DETRAN decidiu que as placas dos veículos do Brasil serão codificadas usando-se 3 letras do alfabeto e 4 algarismos. Qual o número máximo de veículos que poderá ser licenciado?

Solução:

Usando o raciocínio anterior, imaginemos uma placa genérica do tipo PWR-USTZ.

Como o alfabeto possui 26 letras e nosso sistema numérico possui 10 algarismos (de 0 a 9), podemos concluir que: para a 1ª posição, temos 26 alternativas, e como pode haver repetição, para a 2ª, e 3ª também teremos 26 alternativas. Com relação aos algarismos, concluímos facilmente que temos 10 alternativas para cada um dos 4 lugares. Podemos então afirmar que o número total de veículos que podem ser licenciados será igual a: 26.26.26.10.10.10.10 que resulta em 175.760.000. Observe que se no país existissem 175.760.001 veículos, o sistema de códigos de emplacamento teria que ser modificado, já que não existiriam números suficientes para codificar todos os veículos.



Exercícios

Permutação

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?

Auxílio: P(n)=n!, n=3

Resposta: N=1×2×3=6

3-De quantos modos distintos 5 pessoas podem sentar-se em um banco de jardim com 5 lugares?

Auxílio: P(n)=n!, n=5

Resposta: N=1×2×3×4×5=120

4-Qual é o número possível de anagramas que se pode montar com as letras da palavra AMOR?

Auxílio: P(n)=n!, n=4

Resposta: N=1×2×3×4=24

5-Quantos números com cinco algarismos podemos construir com os números ímpares 1,3,5,7,9.

Auxílio:

Resposta: P(5)=120.

6-Quantos números com cinco algarismos podemos construir com os números ímpares 1,3,5,7,9, desde que estejam sempre juntos os algarismos 1 e 3.

Auxílio: Cada conjunto com os algarismos 13 e 31 forma um grupo que junto com os outros, fornece 4 grupos.

Resposta: N=2×P(4)=2×24=48

7-Consideremos um conjunto com n letras. Quantas permutações começam por uma determinada letra?

Resposta: N=P(n-1)=(n-1)!

8-Quantos são os anagramas possíveis com as letras: ABCDEFGHI?

Resposta: P(9)=9!

9-Quantos são os anagramas possíveis com as letras: ABCDEFGHI, começando por A?

Resposta: P(8)=8!

10-Quantos são os anagramas possíveis com as letras: ABCDEFGHI, começando por AB?

Resposta: P(7)=7!


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-Quantos grupos de 3 pessoas podem ser montados com 8 pessoas?

Auxílio: C=C(m,p)=m!/[p!(m-p)!]; m=8,p=3

Resposta: C=8!/(3!5!)=(8×7×6)/(1×2×3)=56

13-Quantos grupos de 2 pessoas podem ser montados com 1000 pessoas?

Auxílio: C=C(m,p)=m!/[p!(m-p)!], m=1000, p=2

Resposta: C=1000!/(2!998!)=1000×999=999000

14-Quantas combinações com 4 elementos podem ser montadas com as 10 primeiras letras do alfabeto?

Conceito: Combinação

Auxílio: C=C(m,p)=m!/[p!(m-p)!], m=10, p=4

Resposta: C=10!/(4!6!)=(10×9×8×7)/(1×2×3×4)=210

15-Quantas combinações com 4 elementos podem ser montadas com as 10 primeiras letras do alfabeto, de tal forma que sempre comecem pela letra A?

Auxílio: C=C(m1,p1).C(m-m1,p-p1), m=10, p=4, m1=1, p1=1

Resposta: C=C(1,1).C(9,3)=(1×9×8×7)/6=84

16-Quantas combinações com 4 elementos podem ser montadas com as 10 primeiras letras do alfabeto, de tal forma que sempre estejam juntas as letras A e B?

Auxílio: C=C(m1,p1).C(m-m1,p-p1), m=10, p=4, m1=2, p1=2

Resposta: C=C(2,2).C(8,2)=(1×8×7)/2=28

17-Quantas combinações com 4 elementos podem ser montadas com as 10 primeiras letras do alfabeto, de tal forma que não contenham nem as letras A e B?

Auxílio: C=C(m1,p1).C(m-m1,p-p1), m=10, p=4, m1=2, p1=0

Resposta: C=C(2,0).C(8,4)=(1×8×7×6×5)/24=70

18-Quantas combinações com 4 elementos podem ser montadas com as 10 primeiras letras do alfabeto, de tal forma que somente uma das letras A ou B esteja presente, mas não as duas?

Auxílio: C=C(m1,p1).C(m-m1,p-p1), m=10, p=4, m1=2, p1=1

Resposta: C=C(2,1).C(8,3)=(2×8×7×6)/6=112

19-Quantas combinações com 4 elementos podem ser montadas com as 10 primeiras letras do alfabeto, de tal forma que contêm 2 dentre as 3 letras A,B e C?

Auxílio: C=C(m1,p1).C(m-m1,p-p1), m=10, p=4, m1=3, p1=2

Resposta: C=C(3,2).C(7,2)=(3×7×6)/2=63

20-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?

21-Calcular o valor de m tal que 5 C(m+1,3)=2 C(m+2,2).


Arranjo simples

22-Quantos números diferentes com 1 algarismo, podemos formar com os algarismos: 0,1,2,3,4,5,6,7,8 e 9.

Resposta: N1=A(9,1)=9

23-Quantos números distintos com 2 algarismos diferentes, podemos formar com os dígitos: 0,1,2,3,4,5,6,7,8,9.

Auxílio: Os números iniciados por 0 não terão 2 dígitos e sua quantidade corresponde a A(9,1).

Resposta: N2=A(10,2)-A(9,1)=10×9-9=90-9=81

24-Quantos números distintos com 3 algarismos diferentes, podemos formar com os dígitos: 0,1,2,3,4,5,6,7,8 e 9.

Auxílio: Os números iniciados por 0 não terão 3 dígitos e sua quantidade corresponde a A(9,2).

Resposta: N3=A(10,3)-A(9,2)=720-720=648

25-Quantos números distintos com 4 algarismos diferentes, podemos formar com: 0,1,2,3,4,5,6,7,8 e 9.

Auxílio: Os números iniciados por 0 não terão 3 dígitos e sua quantidade corresponde a A(9,3).

Resposta: N4=A(10,4)-A(9,3)=5040-504=4536

26-Quantos números distintos menores que 10000 podem ser formados com algarismos diferentes da coleção: {0,1,2,3,4,5,6,7,8,9}.

Resposta: N=N1+N2+N3+N4=9+81+648+4536=5274

27-No sistema decimal de numeração, quantos números existem com 4 algarismos com 2 algarismos repetidos?

Auxílio: A quantidade de números distintos com 4 algarismos é 4536 e a quantidade total de números (com repetição ou não) com 4 algarismos é 9000.

Resposta: N=9000-4536=4464

28-Com as 5 vogais: A,E,I,O,U, obter o conjunto solução que contém todos os arranjos tomados 2 a 2.

29-Usando-se apenas os algarismos 1,3,5,7,9 quantos números com 3 algarismos podem ser montados?

Auxílio: A=A(m,p)=m!/(m-p)!, m=5, p=3

Resposta: A=5!/2!=60

30-Usando-se os algarismos 0,1,2,3,4,5,6,7,8,9 quantos números com 4 algarismos podem ser montados?

Auxílio: A=A(m,p)=m!/(m-p)!, m=10, p=4

Resposta: A=10!/6!=5040

31-Usando-se as 26 letras do alfabeto: A,B,C,D,...,Z quantos arranjos distintos com 3 letras podem ser montados?

Auxílio: A=A(m,p)=m!/(m-p)!, m=26, p=3

Resposta: A=26!/23!=26.25.24=15600

32-Com as 26 letras do alfabeto: A,B,C,D,...,Z e os algarismos 0,1,2,3,4,5,6,7,8,9, quantas placas de carros podem ser escritas contendo 3 letras seguidas de 4 algarismos?

Auxílio: A=A(m,p)=m!/(m-p)!, m=26, p=3, n=10, q=4

Resposta: A=(26!/23!).(10!/6!)=78624000

Nenhum comentário:

Postar um comentário