3 - AULA 19

Prévia do material em texto

AULA Nº19
LÓGICA E MATEMÁTICA DISCRETA 
Combinações I
Profa. Deborah M. Raphael
Combinação
Quantos subconjuntos de 6 elementos podemos formar a partir de um conjunto com 10 elementos?
De quantas maneiras podemos escolher 6 objetos de um conjunto com 10 objetos?
A resposta a ambas as questões é a mesma.
Não importa a ordem da escolha. Ou seja, o efeito final é o mesmo para
 ou .
Devemos dividir (*) por para compensar isso.
Resposta: 
Combinação
Dados dois números inteiros , a combinação de elementos, tomados a é o número de subconjuntos de elementos distintos tomados de um conjunto de elementos.
Este número é denotado por . 
Cálculo de . 
Estamos contando como diferentes escolhas que permutam os elementos. O número de permutações é . Logo, devemos dividir por 
Uma fórmula conhecida, pode ser obtida multiplicando numerador e denominador por 
.
E quando Quantos são os subconjuntos com zero elementos de um conjunto com elementos? A resposta é , o conjunto vazio.
Definindo , a fórmula acima continua válida.
Resumindo o que vimos.
Definição. Dados inteiros , o número de subconjuntos com elementos de um conjunto com elementos é denotado . 
Proposição 1. Vale a igualdade
Notação
Dados inteiros , as notações e também são usadas para indicar , mas são menos universais.
Exemplo 1. Um treinador tem 11 jogadores na sua equipe de vôlei e precisa selecionar 6 titulares para um jogo. Os outros 5 ficarão na reserva. De quantas maneiras pode ser feita a escolha?
Resposta. Pode-se escolher 6 jogadores entre 11 de maneiras distintas. 
Repare que ao escolher 6 jogadores titulares está definida a escolha dos reservas. E vice- versa.
De quantas maneiras pode-se escolher 5 jogadores para a reserva?
Pode-se escolher 5 jogadores entre 11 de maneiras distintas. 
Proposição 2. Dados inteiros , vale a igualdade . 
A maneira mais fácil de provar essa igualdade é utilizando que
As duas frações à direita das igualdades são claramente iguais.
É interessante interpretar pelas definições. 
 é o número de subconjuntos com elementos, a partir de um conjunto com elementos.
 é o número de subconjuntos com 
elementos, a partir de um conjunto com elementos.
Dado um conjunto , ao escolher elementos desse conjunto deixamos de fora elementos. Logo, ao escolher um subconjunto com elementos, estamos também escolhendo um subconjunto com elementos. E vice-versa. 
Há uma correspondência bijetora entre os subconjuntos com elementos e os subconjuntos com elementos.
Por exemplo, dado o conjunto , vamos fazer a correspondência bijetora entre os subconjuntos com elementos e os subconjuntos com elemento.
Exemplo 2. Para organizar uma comemoração, de uma classe com 20 alunos, quer-se formar três grupos: para comida e bebida, para a música e para infraestrutura (cadeiras, pratos, copos, enfeites etc). O grupo encarregado da música deve ter 4 pessoas, o grupo da comida e bebida deve ter 6 pessoas e o grupo da infraestrutura deve ter 8 pessoas. Ninguém deve participar de mais de um grupo. De quantos modos é possível formar os 3 grupos?
20 alunos
música: 4 comida: 6 infraestrutura: 8
Resposta:
Exemplo 3.
Num grupo de 10 pessoas, serão distribuídos 3 prêmios: uma viagem, uma bicicleta e uma lanterna. De quantos modos podem ser distribuídos os prêmios?
De um grupo de 10 pessoas, selecionamos 3 para uma viagem. De quantos modos é possível escolher?
a) Num grupo de 10 pessoas, serão distribuídos 3 prêmios: uma viagem, uma bicicleta e uma lanterna. De quantos modos podem ser distribuídos os prêmios?
Aqui a ordem importa. Não se trata de combinação.
Resposta: 
b) De um grupo de 10 pessoas, selecionamos 3 para uma viagem. De quantos modos é possível escolher?
Caso típico para o uso da combinação. A ordem da escolha não importa. Resposta: 
Ou, usando o princípio da contagem: 
Resposta: 
Exemplo 4. De um grupo de 8 pessoas, de quantas maneiras podemos formar dois grupos de 4 que não tenham ninguém em comum?
Basta selecionar um dos grupos de 4, o outro será formado pelos restantes. Mas tome cuidado!
Há maneiras de escolher um grupo de 4, mas essa não é a resposta.
Da maneira como contamos, se começamos com o conjunto com elementos a,b,c,d,e,f,g e h, podemos escolher a,b,c,d (e o outro grupo será e,f,g,h)
Repare que se escolhermos e,f,g,h, teremos os mesmos dois grupos.
Resposta: Há maneiras de formar 2 grupos com 4 elementos cada.
Resumo
Definimos combinação e provamos a fórmula
 . Fizemos vários exemplos.