|
|
Matérias :: Matemática |
|
|
|
Autoria:
Jennifer Rizzi |
|
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<m.
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<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.
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<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.
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:
Número de
Arranjos simples
Seja C um
conjunto com m elementos. De quantas maneiras diferentes poderemos escolher p
elementos (p<m) deste conjunto? Cada uma dessas escolhas será chamada um arranjo
de m elementos tomados p a p. Construiremos uma sequência com os m elementos de
C.
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?
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:
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:
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:
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:
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á:
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?
| |
-
-
Contato