Aula01_Contagem.pptx

Prévia do material em texto

10/29/13	
  
1	
  
Contagem,	
  Permutações	
  e	
  Combinações	
  
Matemá.ca	
  Discreta	
  II	
  
(Cap.	
  6	
  Rosen)	
  	
  
André	
  Câmara	
  (andrecamara@deinfo.ufrpe.br)	
  
•  Teorema	
  
•  Uma	
  declaração	
  que	
  pode	
  ser	
  demonstrada	
  
verdadeira	
  
•  Formados	
  por	
  uma	
  ou	
  mais	
  premissas	
  e	
  uma	
  
conclusão	
  
•  Podem	
  ser	
  chamados	
  também	
  de	
  fatos	
  ou	
  
resultados	
  
•  Demonstramos	
  que	
  um	
  teorema	
  é	
  verdadeiro	
  
através	
  de	
  uma	
  prova	
  
Terminologia	
  
•  Axioma	
  
•  Declarações	
  assumidas	
  como	
  verdadeiras	
  (ex.:	
  x=x)	
  
•  Lemma	
  
•  Teorema	
  menos	
  importante	
  (usado	
  como	
  passo	
  
intermediário	
  em	
  uma	
  prova)	
  
•  Corolário	
  
•  Teorema	
  estabelecido	
  diretamente	
  a	
  par.r	
  do	
  
teorema	
  provado	
  
•  Conjectura	
  
•  Declaração	
  assumida	
  como	
  verdadeira,	
  baseados	
  em	
  
evidências	
  parciais,	
  argumentos	
  heurís.cos,	
  ou	
  
intuição	
  de	
  especialista	
  
•  Quando	
  provadas,	
  tornam-­‐se	
  Teoremas	
  
Terminologia	
  (cont.)	
  
•  Princípios	
  básicos	
  de	
  contagem	
  
•  Regra	
  do	
  Produto:	
  
•  Suponha	
  que	
  um	
  evento	
  E	
  pode	
  ocorrer	
  de	
  m	
  
formas	
  diferentes,	
  e	
  ,	
  independentemente	
  
deste	
  evento,	
  um	
  segundo	
  evento	
  F	
  pode	
  
ocorrer	
  de	
  n	
  maneiras.	
  
•  Então,	
  E	
  ou	
  F	
  podem	
  ocorrer	
  de	
  mŸn	
  maneiras.	
  
Revisão:	
  Combinatória	
  
Regra	
  do	
  Produto	
  
•  Exemplo:	
  
•  Uma	
  empresa	
  com	
  apenas	
  dois	
  funcionários	
  aluga	
  
um	
  andar	
  de	
  um	
  prédio	
  com	
  12	
  escritórios.	
  	
  
•  De	
  quantas	
  formas	
  podemos	
  atribuir	
  estas	
  salas	
  
aos	
  dois	
  funcionários?	
  
•  R:	
  Atribuir	
  uma	
  sala	
  ao	
  funcionário	
  1	
  (que	
  pode	
  ocorrer	
  
de	
  12	
  formas	
  diferentes)	
  e	
  atribuir	
  uma	
  sala	
  ao	
  
funcionário	
  2	
  (de	
  11	
  formas	
  diferentes)	
  
•  Pela	
  regra	
  do	
  produto,	
  temos:	
  12	
  Ÿ	
  11	
  =	
  132	
  formas	
  
diferentes	
  	
  
Exemplo	
  2	
  
•  Quantas	
  sequências	
  de	
  bit	
  diferentes	
  com	
  
tamanho	
  7	
  existem?	
  
•  R:	
  Cada	
  um	
  dos	
  7	
  bits	
  pode	
  ser	
  preenchido	
  de	
  
2	
  maneiras	
  (0	
  ou	
  1)	
  
•  2*2*2*2*2*2*2	
  =	
  27	
  =	
  128	
  
10/29/13	
  
2	
  
Exemplo	
  3	
  
•  Existem	
  26	
  escolhas	
  para	
  cada	
  uma	
  das	
  três	
  
letras	
  maiúsculas	
  e	
  10	
  escolhas	
  para	
  cada	
  um	
  
dos	
  3	
  dígitos.	
  Quantas	
  placas	
  podem	
  ser	
  
geradas?	
  
•  R:	
  26*26*26*10*10*10	
  =	
  17.576.000	
  placas	
  
possíveis	
  
Exemplo	
  4	
  
•  Qual	
  o	
  valor	
  de	
  k	
  após	
  a	
  execução	
  deste	
  código	
  
(n1,	
  n2,	
  ...	
  nm	
  são	
  inteiros	
  posi.vos):	
  
•  R:	
  n1*	
  n2*...*	
  nm	
  
•  Suponha	
  que	
  um	
  evento	
  E	
  pode	
  ocorrer	
  de	
  m	
  
formas	
  diferentes,	
  e	
  um	
  segundo	
  evento	
  F	
  pode	
  
ocorrer	
  de	
  n	
  maneiras	
  diferentes,	
  e	
  suponha	
  
também	
  que	
  ambos	
  eventos	
  não	
  podem	
  ocorrer	
  
simultaneamente.	
  
•  Então,	
  E	
  ou	
  F	
  podem	
  ocorrer	
  de	
  m+n	
  formas.	
  
Regra	
  da	
  soma	
   Exemplo	
  1	
  
•  Suponha	
  que	
  ou	
  um	
  docente	
  ou	
  um	
  aluno	
  será	
  
escolhido	
  como	
  representante	
  de	
  um	
  comitê	
  
universitário.	
  Este	
  comitê	
  pode	
  ser	
  formado	
  de	
  
quantas	
  maneiras	
  diferentes	
  se	
  existem	
  37	
  
professores	
  e	
  83	
  alunos?	
  
•  R:	
  Existem	
  37	
  maneiras	
  de	
  escolher	
  um	
  
professor	
  e	
  83	
  maneiras	
  de	
  escolher	
  um	
  aluno.	
  
Estas	
  escolhas	
  são	
  independentes	
  uma	
  da	
  
outra,	
  portanto	
  existem	
  37+83	
  =	
  120	
  maneiras	
  
diferentes.	
  
Exemplo	
  2	
  
•  Qual	
  o	
  valor	
  de	
  k	
  após	
  a	
  execução	
  do	
  seguinte	
  
trecho	
  de	
  código	
  (n1,	
  n2,	
  ...	
  nm	
  são	
  inteiros	
  
posi.vos):	
  
•  R:	
  n1+	
  n2+	
  ...	
  +	
  nm	
  
•  Para	
  3	
  ou	
  mais	
  eventos...	
  
E1	
  à	
  n1	
  
E2	
  à	
  n2	
  
E3	
  à	
  n3	
  
...	
  
Estendendo...	
  
Regra	
  da	
  soma:	
  (dois	
  eventos	
  não	
  ocorrem	
  ao	
  
mesmo	
  tempo)	
  
	
  
Num.	
  maneiras	
  =	
  n1	
  +	
  n2	
  +	
  n3	
  +	
  ...	
  	
  
	
  
Regra	
  da	
  mul5plicação:	
  (eventos	
  ocorrem	
  um	
  
após	
  o	
  outro)	
  
	
  
Num.	
  maneiras	
  =	
  n1	
  Ÿ	
  n2	
  Ÿ	
  n3	
  Ÿ	
  ...	
  	
  
	
  
10/29/13	
  
3	
  
•  Suponha	
  que	
  uma	
  universidade	
  tem	
  3	
  disciplinas	
  
diferentes	
  de	
  história,	
  4	
  disciplinas	
  diferentes	
  de	
  
literatura,	
  e	
  2	
  disciplinas	
  diferentes	
  de	
  sociologia.	
  
	
  
a)	
  O	
  número	
  m	
  de	
  formas	
  que	
  um	
  estudante	
  pode	
  
escolher	
  os	
  cursos	
  é:	
  
m	
  =	
  (3)Ÿ(4)Ÿ(2)	
  =	
  24	
  
	
  
b)	
  O	
  número	
  m	
  de	
  formas	
  que	
  um	
  estudante	
  pode	
  
escolher	
  apenas	
  um	
  dos	
  cursos	
  é:	
  
m	
  =	
  (3)	
  +	
  (4)	
  +	
  (2)	
  =	
  9	
  
	
  
Exemplo	
  3	
   Exemplo:	
  contando	
  endereços	
  IP	
  
•  Na	
  internet,	
  cada	
  computador	
  possui	
  um	
  
endereço	
  chamado	
  endereço	
  IP.	
  
•  No	
  IPv4,	
  este	
  endereço	
  é	
  composto	
  de	
  32	
  bits	
  
•  ne.d=número	
  da	
  rede	
  
•  hos.d=número	
  do	
  host	
  
Exemplo:	
  contando	
  endereços	
  IP	
  
•  Classe	
  A:	
  redes	
  grandes	
  
•  0	
  seguido	
  por	
  7-­‐bits	
  para	
  rede	
  e	
  24-­‐bits	
  para	
  hosts	
  
•  ne.d	
  não	
  pode	
  ser	
  1111111	
  
•  Classe	
  B:	
  redes	
  médias	
  
•  10	
  seguido	
  por	
  14-­‐bits	
  para	
  rede	
  e	
  16-­‐bits	
  para	
  
hosts	
  
•  Classe	
  C:	
  redes	
  menores	
  
•  110	
  seguido	
  de	
  21-­‐bits	
  para	
  rede	
  e	
  8-­‐bits	
  para	
  
hosts	
  
•  11111111	
  e	
  00000000	
  tem	
  uso	
  especial	
  e	
  não	
  
podem	
  ser	
  designados	
  como	
  end.	
  de	
  host	
  válidos	
  
Exemplo:	
  contando	
  endereços	
  IP	
  
•  Quantos	
  endereços	
  IP	
  estão	
  disponíveis	
  na	
  
internet?	
  	
  
•  R:	
  Seja	
  x	
  o	
  número	
  de	
  endereços	
  disponíveis	
  
•  xA	
  =	
  números	
  de	
  endereços	
  da	
  Classe	
  A	
  
•  xB	
  =	
  números	
  de	
  endereços	
  da	
  Classe	
  B	
  
•  xC	
  =	
  números	
  de	
  endereços	
  da	
  Classe	
  C	
  
•  x	
  =	
  xA	
  +	
  xB	
  +	
  xC	
  	
  
Exemplo:	
  contando	
  endereços	
  IP	
  
•  xA	
  =	
  27	
  –	
  1	
  =	
  127	
  redes	
  (rede	
  1111111	
  é	
  indisponível)	
  
•  Para	
  cada	
  rede	
  existem	
  224-­‐2	
  =	
  16.777.214	
  hosts	
  
•  xA	
  =	
  127	
  	
  *	
  	
  16.777.214	
  =	
  2.130.706.178	
  
•  xB	
  =	
  214	
  =	
  16.384	
  redes	
  
•  Para	
  cada	
  rede	
  existem	
  216-­‐2	
  =	
  65.534	
  hosts	
  
•  xB=	
  16.384	
  *	
  	
  65.534	
  =	
  1.073.709.056	
  
•  xC	
  =	
  221	
  =	
  2.097.152	
  redes	
  
•  Para	
  cada	
  rede	
  existem	
  28-­‐2	
  =	
  254	
  hosts	
  	
  
•  xC	
  =	
  2.097.152	
  *	
  254	
  =	
  532.676.608	
  
•  x	
  =	
  3.737.091.842	
  endereços	
  
Princípio	
  da	
  Inclusão-­‐Exclusão	
  
•  Ou	
  “Regra	
  da	
  Subtração”	
  
•  Suponha	
  que	
  uma	
  tarefa	
  possa	
  ser	
  feita	
  de	
  uma	
  dentre	
  duas	
  
maneiras,	
  mas	
  algumas	
  dessas	
  maneiras	
  são	
  comuns	
  entre	
  eles.	
  
•  Não	
  podemos	
  usar	
  a	
  regra	
  da	
  soma!	
  
•  Devemos	
  subtrair	
  as	
  formas	
  que	
  se	
  repetem,	
  para	
  que	
  não	
  sejam	
  
contadas	
  duas	
  vezes	
  
•  “Se	
  uma	
  tarefa	
  pode	
  ser	
  feita	
  de	
  n1	
  ou	
  n2	
  maneiras,	
  então	
  o	
  número	
  
de	
  formas	
  de	
  se	
  realizar	
  a	
  tarefa	
  é	
  n1+n2	
  menos	
  o	
  número	
  de	
  formas	
  
de	
  se	
  realizar	
  a	
  tarefa	
  que	
  são	
  comuns	
  às	
  duas	
  maneiras”.	
  
•  Sejam	
  A	
  e	
  B	
  conjuntos	
  finitos	
  
	
  
•  Teorema	
  
•  Para	
  quaisquer	
  conjuntos	
  finitos	
  A,	
  B	
  e	
  C	
  
10/29/13	
  
4	
  
Exemplo	
  1	
  
•  Encontre	
  o	
  número	
  de	
  estudantes	
  matriculados	
  
em	
  pelo	
  menos	
  uma	
  das	
  aulas	
  de	
  Francês,	
  
Alemão	
  e	
  Inglês,	
  dado	
  que:	
  
•  65	
  estudam	
  Francês,	
  20	
  estudam	
  Francês	
  e	
  
Alemão	
  
•  45	
  estudam	
  Alemão,	
  25	
  estudam	
  Francês	
  e	
  
Inglês,	
  	
  
•  42	
  estudam	
  Inglês,	
  15	
  estudam	
  Alemão	
  e	
  
Inglês	
  
•  8	
  estudam	
  todas	
  as	
  três	
  línguas	
  	
  
Exemplo	
  
	
  
•  Ou	
  por	
  diagramas	
  de	
  Venn	
  
	
  
	
  
10	
  
28	
   12	
  
8	
  
18	
  
7	
  17	
  
F	
  
A	
  
I	
  
n(F∪A∪ I ) = n(F)+ n(A)+ n(I )
−n(F∩G)− n(F∩ I )− n(A∩ I )+ n(F∩A∩ I )
= 65+ 45+ 42− 20− 25−15+8 =100
Exemplo	
  2	
  
•  Quantas	
  strings	
  de	
  bits	
  de	
  tamanho	
  8	
  começam	
  
com	
  1	
  ou	
  terminam	
  com	
  dois	
  bits	
  00?	
  
formas	
  
formas	
  
formas	
  
Pode	
  estar	
  
dentro	
  de	
  
ambos	
  os	
  
conjuntos	
  de	
  
soluções	
  
n	
  =	
  128+64-­‐32	
  =	
  160	
  	
  
Regra	
  da	
  divisão	
  
•  Existem	
  n/d	
  maneiras	
  de	
  se	
  realizar	
  uma	
  tarefa	
  
se	
  ela	
  pode	
  ser	
  feita	
  usando	
  um	
  procedimento	
  
que	
  pode	
  ser	
  realizado	
  de	
  n	
  maneiras,	
  e	
  para	
  
cada	
  maneira	
  w,	
  exatamente	
  d	
  das	
  n	
  maneiras	
  
correspondem	
  à	
  maneira	
  w.	
  
Exemplo	
  
•  De	
  quantas	
  maneiras	
  diferentes	
  4	
  pessoas	
  
podem	
  se	
  sentar	
  em	
  torno	
  de	
  uma	
  mesa	
  circular,	
  
onde	
  duas	
  arrumações	
  são	
  consideradas	
  a	
  
mesma	
  quando	
  cada	
  pessoa	
  tem	
  o	
  mesmo	
  
vizinho	
  da	
  esquerda	
  e	
  o	
  mesmo	
  vizinho	
  da	
  
direita?	
  
Exemplo	
  
•  R:	
  Rotulando	
  os	
  assentos:	
  
•  Temos	
  4	
  formas	
  de	
  escolher	
  	
  
quem	
  vai	
  sentar	
  no	
  assento	
  1	
  
•  3	
  para	
  o	
  assento	
  2,	
  ...	
  
•  4!	
  =	
  24	
  maneiras	
  	
  
das	
  pessoas	
  sentarem	
  
•  Considerar	
  apenas	
  as	
  maneiras	
  
com	
  vizinhos	
  diferentes!	
  
•  4	
  formas	
  diferentes	
  de	
  selecionar	
  a	
  pessoa	
  do	
  
assento	
  1	
  à	
  24/4	
  =	
  6	
  maneiras	
  
Assento	
  
1	
  
Assento	
  
2	
  
Assento	
  
3	
  
Assento	
  
4	
  
10/29/13	
  
5	
  
Diagrama	
  de	
  Árvore	
  
•  Uma	
  forma	
  comum	
  de	
  representar	
  todas	
  as	
  
saídas	
  de	
  uma	
  sequência	
  de	
  eventos	
  
•  Ex.:	
  A	
  =	
  {1,2},	
  B={a,b,c},	
  C={x,y}	
  
n=(2)(3)(2)=12	
  
Diagrama	
  de	
  Árvore	
  
•  Exemplo:	
  
•  Strings	
  de	
  bits	
  de	
  tamanho	
  4	
  sem	
  1`s	
  
consecu.vos	
  
Princípio	
  da	
  Casa	
  de	
  Pombos	
  
•  Muitos	
  resultados	
  na	
  teoria	
  combinatória	
  são	
  
versões	
  diferentes	
  do	
  mesmo	
  problema:	
  
	
  
“Se	
  n	
  casas	
  de	
  pombos	
  são	
  ocupadas	
  por	
  n+1	
  ou	
  
mais	
  pombos,	
  então	
  pelo	
  menos	
  uma	
  casa	
  é	
  
ocupada	
  por	
  mais	
  de	
  um	
  pombo”	
  
Exemplos	
  
•  Suponha	
  que	
  um	
  departamento	
  contém	
  13	
  
professores	
  
•  Então	
  dois	
  dos	
  professores	
  nasceram	
  no	
  
mesmo	
  mês	
  
•  Suponha	
  que	
  um	
  saco	
  de	
  lavanderia	
  contém	
  
muitas	
  meias	
  vermelhas,	
  brancas	
  e	
  azuis.	
  	
  
•  Então	
  é	
  necessário	
  pegar	
  apenas	
  4	
  meias	
  
(pombos)	
  para	
  ter	
  certeza	
  de	
  obter	
  um	
  par	
  
com	
  uma	
  única	
  cor	
  (casa	
  de	
  pombo)	
  
Exemplos	
  
•  Mostre	
  que	
  em	
  um	
  conjunto	
  de	
  6	
  aulas	
  existem	
  
duas	
  que	
  são	
  ministradas	
  no	
  mesmo	
  dia.	
  Assuma	
  
que	
  as	
  aulas	
  não	
  são	
  ministradas	
  nos	
  finais	
  de	
  
semana.	
  	
  
•  Temos	
  5	
  dias	
  úteis	
  durante	
  a	
  semana	
  e	
  temos	
  
6	
  aulas.	
  Se	
  todo	
  dia	
  tem	
  uma	
  aula,	
  então	
  serão	
  
5	
  aulas	
  por	
  semana,	
  sobrando	
  1	
  aula	
  que	
  será	
  
colocada	
  no	
  mesmo	
  dia	
  de	
  outra.	
  
Exemplos	
  
•  Mostre	
  que	
  em	
  um	
  conjunto	
  de	
  5	
  inteiros	
  (não	
  
necessariamente	
  consecu.vos)	
  existem	
  2	
  com	
  o	
  
mesmo	
  resto	
  quando	
  dividido	
  por	
  4.	
  	
  
•  Os	
  possíveis	
  restos	
  quando	
  dividimos	
  um	
  
número	
  por	
  4,	
  são:	
  0,	
  1,	
  2,	
  3	
  (4	
  restos)	
  
•  Se	
  tenho	
  5	
  inteiros,	
  então	
  quando	
  divididos	
  
por	
  4	
  terão	
  5	
  restos.	
  Como	
  temos	
  4	
  restos	
  
dis.ntos	
  2	
  serão	
  iguais.	
  
10/29/13	
  
6	
  
Exemplos	
  
•  Em	
  um	
  conjunto	
  de	
  367	
  pessoas,	
  pelo	
  menos	
  
quantas	
  pessoas	
  fazem	
  aniversário	
  no	
  mesmo	
  
dia?	
  
•  Pelo	
  menos	
  2,	
  pois	
  só	
  temos	
  no	
  máximo	
  366	
  
dias	
  possíveis	
  
Exemplos	
  
•  Encontre	
  o	
  número	
  mínimo	
  de	
  elementos	
  que	
  
são	
  necessários	
  ser	
  re.rados	
  do	
  conjunto	
  	
  
S	
  =	
  {1,2,3,...9}	
  para	
  que	
  se	
  tenha	
  certeza	
  que	
  
dois	
  dos	
  números	
  somados	
  resultam	
  em	
  10	
  
•  Aqui	
  as	
  casas	
  de	
  pombos	
  são	
  os	
  5	
  conjuntos	
  
{1,9},	
  {2,8},	
  {3,7},	
  {4,6},	
  {5}	
  
•  Portanto,	
  qualquer	
  escolha	
  de	
  6	
  elementos	
  de	
  
S	
  garante	
  que	
  2	
  dos	
  números	
  somados	
  
resultam	
  em	
  10	
  
Generalizando	
  
•  Se	
  n	
  casas	
  de	
  pombo	
  são	
  ocupadas	
  por	
  kn+1	
  ou	
  
mais	
  pombos,	
  onde	
  k	
  é	
  um	
  inteiro	
  posi.vo,	
  
então	
  pelo	
  menos	
  uma	
  casa	
  de	
  pombo	
  é	
  
ocupada	
  por	
  k+1	
  ou	
  mais	
  pombos.	
  
Exemplos	
  
•  Encontre	
  o	
  número	
  mínimo	
  de	
  estudantes	
  em	
  
uma	
  turma	
  de	
  modo	
  quese	
  tenha	
  certeza	
  de	
  
que	
  3	
  deles	
  nasceram	
  no	
  mesmo	
  mês	
  
•  Aqui,	
  n=12	
  é	
  o	
  número	
  de	
  casas	
  de	
  pombos	
  
•  K+1	
  devem	
  ocupar	
  a	
  mesma	
  casa	
  (mes)	
  
•  k+1	
  =	
  3,	
  portanto	
  k=2	
  
•  Entre	
  kn+1	
  =	
  25	
  estudantes	
  (pombos),	
  três	
  deles	
  serão	
  nascidos	
  no	
  
mesmo	
  mês	
  
Exemplos	
  
•  Suponha	
  que	
  um	
  saco	
  de	
  lavanderia	
  contém	
  
muitas	
  meias	
  vermelhas,	
  brancas	
  e	
  azuis.	
  Ache	
  o	
  
número	
  de	
  meias	
  que	
  se	
  deve	
  escolher	
  a	
  fim	
  de	
  
se	
  obter	
  	
  2	
  pares	
  (4	
  meias)	
  das	
  mesma	
  cor.	
  
•  n=3	
  cores	
  (casas	
  de	
  pombos)	
  
•  k+1	
  =	
  4	
  (meias	
  da	
  mesma	
  cor,	
  ou	
  pombos	
  ocupando	
  a	
  mesma	
  casa)	
  
•  k=3	
  
•  kn+1	
  =	
  3*3+1	
  =	
  10	
  
•  Dentre	
  quaisquer	
  10	
  meias,	
  4	
  tem	
  a	
  mesma	
  cor	
   PERMUTAÇÕES	
  E	
  COMBINAÇÕES	
  
10/29/13	
  
7	
  
Algumas	
  funções	
  importantes	
  
•  Função	
  Fatorial	
  
•  O	
  produto	
  dos	
  inteiros	
  posi.vos	
  de	
  1	
  a	
  n	
  
(inclusive)	
  é	
  denotado	
  por	
  n!	
  (“n	
  fatorial”)	
  
n!	
  =	
  1	
  Ÿ	
  	
  2	
  Ÿ	
  3	
  Ÿ	
  4	
  Ÿ	
  ...	
  Ÿ	
  (n-­‐2)	
  (n-­‐1)	
  n	
  
•  Importante:	
  
•  0!	
  =	
  1	
  
•  1!	
  =	
  1	
  
•  n!	
  =	
  n(n-­‐1)!	
  
Fatorial	
  Exemplos	
  
•  Exemplo	
  1:	
  
•  Exemplo	
  2:	
  
•  Observe	
  que:	
  
Permutações	
  
•  Qualquer	
  arranjo	
  de	
  um	
  conjunto	
  de	
  n	
  objetos	
  em	
  
uma	
  dada	
  ordem	
  é	
  chamada	
  de	
  uma	
  permutação	
  	
  
•  BDCA,	
  DCBA	
  e	
  ACDB	
  são	
  permutações	
  de	
  A,B,C,D	
  
•  Qualquer	
  arranjo	
  de	
  r	
  ≤	
  n	
  destes	
  objetos	
  em	
  uma	
  
dada	
  ordem	
  é	
  chamada	
  de	
  uma	
  	
  
r-­‐permutação	
  dos	
  n	
  objetos,	
  r	
  a	
  r	
  
•  BAD,	
  ACB,	
  DBC	
  são	
  permutações	
  das	
  4	
  letras	
  3	
  a	
  3	
  
•  AD,	
  BC,	
  CA	
  são	
  permutações	
  das	
  4	
  letras	
  2	
  a	
  2	
  
Permutações	
  
•  Normalmente	
  estamos	
  interessados	
  apenas	
  no	
  
número	
  de	
  permutações,	
  sem	
  necessitar	
  lista-­‐las	
  
•  O	
  número	
  de	
  permutações	
  de	
  n	
  objetos	
  r	
  a	
  r	
  é	
  
denotado	
  por:	
  
	
  
P(n,r)	
  
•  Alguns	
  livros	
  também	
  u.lizam	
  nPr	
  ,	
  Pn,r	
  ou	
  (n)r	
  
Permutações	
  	
  
•  Teorema	
  
•  Prova:	
  
•  Primeiro	
  elemento:	
  n	
  opções	
  
•  Segundo	
  elemento:	
  n-­‐1	
  opções	
  
•  ...	
  
•  r-­‐ésimo	
  elemento:	
  n-­‐(r-­‐1)	
  =	
  n-­‐r+1	
  
•  Pela	
  regra	
  do	
  produto,	
  chegamos	
  ao	
  Teorema	
  
r	
  termos	
  
Exemplo	
  1	
  
•  Encontre	
  o	
  número	
  m	
  de	
  permutações	
  de	
  seis	
  
objetos,	
  A,	
  B,	
  C,	
  D,	
  E,	
  F,	
  selecionando-­‐se	
  3	
  a	
  cada	
  
momento	
  (3	
  a	
  3).	
  
•  Palavras	
  com	
  três	
  letras	
  usando	
  apenas	
  as	
  seis	
  
letras	
  dadas,	
  sem	
  repe.ção	
  
10/29/13	
  
8	
  
Permutações	
  
•  Corolário	
  
•  Se	
  r	
  =	
  n,	
  então	
  existem	
  n!	
  permutações	
  dos	
  n	
  
objetos	
  
•  Exemplo	
  
•  Letras	
  A,	
  B,	
  C	
  
•  3!	
  =	
  6	
  permutações	
  
•  ABC,	
  ACB,	
  BAC,	
  BCA,	
  CAB,	
  CBA	
  
Permutações	
  com	
  Repetições	
  
•  Nas	
  permutações	
  anteriores,	
  não	
  há	
  repe.ção	
  
de	
  objetos	
  
•  Muitas	
  vezes,	
  queremos	
  saber	
  o	
  número	
  de	
  
permutações	
  de	
  n	
  objetos,	
  dos	
  quais	
  alguns	
  
podem	
  se	
  repe.r	
  
•  Exemplo	
  
•  “BABBY”	
  à	
  “B1	
  ,	
  A	
  ,	
  B2	
  ,	
  B3	
  ,	
  Y”	
  
•  5!	
  =	
  120	
  
•  Algumas	
  permutações	
  possíveis	
  são	
  
Permutações	
  com	
  Repetições	
  
•  O	
  fato	
  é	
  que	
  existem	
  3!	
  =	
  6	
  formas	
  diferentes	
  de	
  
preencher	
  as	
  três	
  primeiras	
  posições	
  com	
  os	
  três	
  
B’s	
  
•  Isso	
  é	
  verdade	
  para	
  cada	
  conjunto	
  de	
  três	
  
posições	
  em	
  que	
  os	
  B’s	
  podem	
  aparecer	
  
•  Teorema:	
  
n1,	
  n2,	
  n3,	
  ...	
  à	
  número	
  de	
  repe.ções	
  
Permutações	
  com	
  Repetições	
  
•  De	
  fato,	
  no	
  exemplo	
  anterior,	
  o	
  que	
  teremos	
  é	
  
•  “BABBY”	
  
•  “BENZENE”	
  
	
  
Amostras	
  Ordenadas	
  
•  Amostragem	
  com	
  reposição	
  
•  n	
  Ÿ	
  n	
  Ÿ	
  n	
  Ÿ	
  n	
  Ÿ	
  ...	
  Ÿ	
  n	
  (r	
  fatores)	
  	
  =	
  nr	
  
•  Amostragem	
  sem	
  reposição	
  (r-­‐permutação)	
  
Exemplo	
  
•  3	
  cartas	
  são	
  escolhidas	
  uma	
  após	
  a	
  outra	
  de	
  uma	
  
pilha	
  de	
  52	
  cartas.	
  Encontre	
  o	
  número	
  m	
  de	
  
formas	
  que	
  isto	
  pode	
  ser	
  feito:	
  
a.  Com	
  reposição	
  
b.  Sem	
  reposição	
  
m	
  	
  =	
  (52)	
  (52)	
  (52)	
  =	
  140.608	
  	
  
m	
  	
  =	
  P(52,3)	
  =	
  (52)	
  (51)	
  (50)	
  =	
  132.600	
  	
  
10/29/13	
  
9	
  
Combinatória	
  
•  “Arte	
  da	
  contagem”	
  
•  Permite	
  definir	
  o	
  número	
  de	
  objetos	
  em	
  um	
  
conjunto	
  rapidamente	
  
Combinações	
  
•  Seja	
  S	
  um	
  conjunto	
  com	
  n	
  elementos.	
  	
  
•  Uma	
  combinação	
  	
  destes	
  n	
  elementos	
  
selecionando-­‐se	
  r	
  a	
  cada	
  vez	
  é	
  qualquer	
  seleção	
  
de	
  r	
  objetos	
  (sem	
  ordem)	
  
•  r-­‐combinação	
  
•  Subconjunto	
  de	
  S	
  com	
  r	
  elementos	
  
•  C(n,r)	
  	
  
•  Ou	
  nCr	
  ,	
  Cn,r	
  ,	
  Crn	
  
Exemplo	
  
•  Encontrar	
  o	
  número	
  de	
  combinações	
  de	
  4	
  
objetos	
  A,	
  B,	
  C,	
  D,	
  sendo	
  selecionados	
  3	
  por	
  a	
  
cada	
  vez	
  
•  Cada	
  combinação	
  corresponde	
  a	
  3!	
  =	
  6	
  
permutações	
  dos	
  objetos	
  
Exemplo	
  (cont.)	
  
•  O	
  número	
  de	
  combinações	
  mul.plicado	
  por	
  3!	
  
nos	
  dá	
  o	
  número	
  de	
  permutações:	
  
•  Sendo	
  P(4,3)	
  =	
  4	
  Ÿ	
  3	
  Ÿ	
  2	
  =	
  24	
  e	
  3!=6,	
  temos	
  
C(4,3)	
  =	
  4	
  
ou	
  
Combinações	
  
•  Teorema	
  
Ou	
  seja,	
  	
  
C(n, r) = nr
!
"
#
$
%
&
Exemplo	
  
•  Um	
  fazendeiro	
  compra	
  3	
  vacas,	
  2	
  porcos,	
  e	
  4	
  
galinhas	
  de	
  um	
  homem	
  que	
  tem	
  6	
  vacas,	
  5	
  
porcos	
  e	
  8	
  galinhas.	
  
•  Qual	
  o	
  número	
  m	
  de	
  escolhas	
  que	
  o	
  fazendeiro	
  
tem?	
  
10/29/13	
  
10	
  
Exemplo	
  
•  Considere	
  que	
  uma	
  moeda	
  seja	
  lançada	
  5	
  vezes.	
  
De	
  quantas	
  formas	
  pode-­‐se	
  ter	
  três	
  caras?	
  
•  Combinação	
  (ordem	
  não	
  importa)	
  
•  Determine	
  o	
  número	
  de	
  formas	
  que	
  uma	
  moeda	
  
pode	
  cair	
  se	
  lançada	
  5	
  vezes.	
  	
  
•  O	
  resultado	
  pode	
  ser:	
  
•  5	
  caras,	
  4	
  caras,	
  3	
  caras,	
  2	
  caras,	
  1	
  cara,	
  0	
  cara	
  
Exemplo	
  
•  Determine	
  o	
  número	
  de	
  formas	
  que	
  uma	
  moedapode	
  cair	
  se	
  lançada	
  5	
  vezes.	
  	
  
•  O	
  resultado	
  pode	
  ser:	
  
•  5	
  caras,	
  4	
  caras,	
  3	
  caras,	
  2	
  caras,	
  1	
  cara,	
  0	
  cara	
  
•  O	
  Mesmo	
  que	
  	
  
2	
  x	
  2	
  x	
  2	
  x	
  2	
  x	
  2	
  =	
  32	
  =	
  25	
  
	
  
Ou	
  seja,	
  	
  
n
k
!
"
#
$
%
&
k=0
n
∑ = 2n
Exemplo	
  
•  De	
  quantas	
  maneiras	
  um	
  comitê,	
  cons.tuido	
  por	
  
3	
  homens	
  e	
  2	
  mulheres,	
  pode	
  ser	
  escolhido	
  
entre	
  7	
  homens	
  e	
  5	
  mulheres?	
  
•  Homens	
  podem	
  ser	
  escolhidos	
  de	
  	
  
•  Mulheres	
  podem	
  ser	
  escolhidas	
  de