Professor de Matemática Antonio Carlos Carneiro Barroso
Colégio Estadual Dinah Gonçalves
email accbarroso@hotmail.com
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
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. Apresentaremos alguns detalhes de tais agrupamentos.
Observação: É comum encontrarmos na literatura termos como: arranjar, combinar ou permutar, mas todo o cuidado é pouco com os mesmos, que às vezes são utilizados em concursos em uma forma dúbia!
Arranjos
São agrupamentos formados com p elementos, (p
Arranjo simples: Não ocorre a repetição de qualquer elemento em cada grupo de p elementos.
Fórmula: As(m,p) = m!/(m-p)!
Cálculo para o exemplo: As(4,2) = 4!/2!=24/2=12.
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}
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.
Fórmula: Ps(m) = m!.
Cálculo para o exemplo: Ps(3) = 3!=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 m1 iguais a x1, m2 iguais a x2, m3 iguais a x3, ... , mn iguais a xn, de modo que m1+m2+m3+...+mn=m.
Fórmula: Se m=m1+m2+m3+...+mn, então
Pr(m)=C(m,m1).C(m-m1,m2).C(m-m1-m2,m3) ... C(mn,mn)
Anagrama: Um anagrama é uma (outra) palavra construída com as mesmas letras da palavra original trocadas de posição.
Cálculo para o exemplo: m1=4, m2=2, m3=1, m4=1 e m=6, logo: Pr(6)=C(6,4).C(6-4,2).C(6-4-1,1)=C(6,4).C(2,2).C(1,1)=15.
Exemplo: Quantos anagramas podemos formar com as 6 letras da palavra ARARAT. A letra A ocorre 3 vezes, a letra R ocorre 2 vezes e a letra T ocorre 1 vez. As permutações com repetição desses 3 elementos do conjunto C={A,R,T} em agrupamentos de 6 elementos são 15 grupos que contêm a repetição de todos os elementos de C aparecendo também na ordem trocada. Todos os agrupamentos estão no conjunto:
Pr={AAARRT,AAATRR,AAARTR,AARRTA,AARTTA,
AATRRA,AARRTA,ARAART,ARARAT,ARARTA,
ARAATR,ARAART,ARAATR,ATAARA,ATARAR}
Permutação circular: Situação que ocorre quando temos grupos com m elementos distintos formando uma circunferência de círculo.
Fórmula: Pc(m)=(m-1)!
Cálculo para o exemplo: P(4)=3!=6
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 circular (pode ser retangular) 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, teriamos 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}
Combinações
Quando formamos agrupamentos com p elementos, (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
extraido de www.colaweb.com.br
Nenhum comentário:
Postar um comentário