- Quantos são os
-conjuntos (isto é, subconjuntos com
elementos) de
nos quais:
a)
figura;
b)
não figura;
c)
e
figuram;
d) pelo menos um dos elementos
figura;
a)
b)
c)
d) pelo menos um dos elementos
Passo 1
O enunciado pede para contar quantos são os subconjuntos com
elementos (chamados de
-conjuntos) do conjunto
nas seguintes situações:
a) figura no subconjunto;
b) não figura;
c) e
figuram;
d) pelo menos um dos elementos figura.
a)
b)
c)
d) pelo menos um dos elementos
Informações dadas e parâmetros:
- O universo é o conjunto com
elementos . - Queremos contar subconjuntos que têm exatamente
elementos (ou seja, -conjuntos). -
e são números inteiros com (assumo isso porque a questão é padrão de combinatória). - Não há outras restrições além das especificadas em (a)-(d).
Passo 2
Conceito-chave: número total de
-conjuntos de um conjunto com
elementos.
Definição e fórmula: o número de maneiras de escolher elementos dentre
sem ordem (ou seja, subconjuntos) é o coeficiente binomial
Definição e fórmula: o número de maneiras de escolher
Aqui
(lê-se “
fatorial”) é
, e por convenção
.
Interpretação prática: é “quantos subconjuntos de tamanho
existem” — escolhemos
elementos entre
e a ordem de escolha não importa.
Interpretação prática:
Exemplo rápido para fixar: para
e
,
. Há 10 pares distintos.
Passo 3
(a) Contar
-conjuntos nos quais
figura.
Raciocínio: se já está no subconjunto, faltam escolher mais
elementos para completar o
-conjunto. Esses
elementos devem ser escolhidos entre os restantes
elementos
. Assim o número procurado é o número de maneiras de escolher
dentre
, isto é
Raciocínio: se
Explicação da fórmula: fixamos
e contamos subconjuntos de tamanho
no resto; por exemplo, se
e
, então escolhemos 2 de entre 4, dando
subconjuntos que contêm
.
Passo 4
(b) Contar
-conjuntos nos quais
não figura.
Raciocínio: se não pode ser usado, então todos os
elementos vêm dos
restantes
. Logo o número é
Raciocínio: se
Interpretação simples: escolhemos
elementos de um conjunto de
elementos.
Passo 5
(c) Contar
-conjuntos nos quais
e
figuram.
Raciocínio: se ambos e
já estão no subconjunto, faltam escolher
elementos entre os
restantes
. Portanto o número é
Raciocínio: se ambos
Exemplo:
,
→ escolher 1 entre 4 restantes →
subconjuntos que contêm
e
.
Passo 6
(d) Contar
-conjuntos nos quais “pelo menos um” dos elementos
figura.
Duas abordagens equivalentes (explico as duas porque é útil na prova):
Duas abordagens equivalentes (explico as duas porque é útil na prova):
Método 1 — inclusão-exclusão: seja
o conjunto de
-conjuntos que contêm
e
o conjunto que contêm
. Queremos
. Pela fórmula de inclusão-exclusão,
Usando resultados já obtidos:
,
e
. Substituindo,
Método 2 — complemento: conte todos os
-conjuntos e subtraia os que não têm nem
nem
. O número de
-conjuntos sem
nem
é
(escolher os
entre os
restantes). Logo
Ambas as expressões são equivalentes; se quiser ver a igualdade rapidamente, use identidades de Pascal:
mostrando que as duas formas coincidem (aqui usei sucessivamente
e
e depois de novo Pascal).