Análise Combinatória, Probabilidade e Aplicações - Lista 2.
Ex 1 Prove usando um argumento combinatório que:
n
X
n
k
= n2n−1
k
k=1
Solução: Seja um grupo de n pessoas e as duas seguintes maneiras de se
determinar o número de possíveis seleções de uma diretoria de qualquer tamanho
com um diretor presidente. O lado esquerdo pode ser visto como o número de possíveis maneiras de se formar uma diretoria de tamanho k, k ∈ {1, ..., n} em que
há um diretor presidente. O lado direito corresponde a escolha do diretor presidente, n possibilidades, e a posterior escolha dos membros pertencentes à diretoria,
para cada um dos n−1 restantes há duas possibilidades, pertencer ou não à diretoria.
Ex 2 Seja Ω = {a1 , a2 , ..., an }. Em quantos subconjuntos de tamanho p:
a) a1 pertence?
n−1
p−1
Temos que escolher p − 1 elementos de {a2 , ..., an }, logo há
.
b) a1 não pertence?
Temos que escolher p elementos de {a2 , ..., an }, logo há
n−1
p
.
c) a1 e a2 figuram?
Temos que escolher p − 2 elementos de {a3 , ..., an }, logo há
n−2
p−2
.
d) Pelo menos um dos elementos a1 e a2 pertencem?
Há n−2
subconjuntos em que não figuram a1 e a2 entre seus elementos. Há
p
n
subconjutos de tamanho p. Logo o total de subconjuntos em que figura pelo
p
menos um dos elementos a1 ou a2 é np − n−2
.
p
e) exatamente um dos elementos a1 , a2 pertence?
.
O núemro de subconjuntos em que pelo menos um deles figura é np − n−2
p
n−2
O número de subconjuntos em que os elementos a1 e a2 figuram é p−2 . Logo, o
n−2
número de subconjuntos em que exatamente um deles figura é np − n−2
−
.
p
p−2
Ex 3 Prove, usando um argumento combinatório, que:
n
n−k
n 2 −1
−
<
k n
k
k
k
1
Ex 4 De quantos modos é possível colocar em fila h homens e m mulheres, todos de alturas diferentes, de modo que os homens entre si e as mulheres entre si
fiquem em ordem crescente de alturas?
Solução: Uma vez escolhido o lugar dos homens, o das mulheres fica determinado. Feito isso, há também uma só maneira de se dispor os homens e as
mulheres, que é na ordem crescente de suas alturas.
Logo, temos apenas que deter
h+m
minar a escolha das posições dos homens h que obviamente é igaul ao número
de maneiras de se escolher a posição das mulheres h+m
, pois cada escolha de um
m
deles, corresponde a nào escolha dos outros.
Ex 5 De quantos modos é possível colocar em uma prateleira 5 livros de matemática,
3 de física e 2 de estatística, de modo que livros de um mesmo assunto permaneçam
juntos?
Solução: Considerando os livros de um mesmo assunto como "blocos", há 5!,
3! e 2! possibilidades de permutações intra "blocos"de livros. Há também outras 3!
possibilidades de se permutarem os "blocos"entre si. Logo há 5!3!2!3! possibilidades.
Ex 6 De quantos modos r rapazes e m moças podem se colocar em fila de modo
que as moças fiquem juntas?
Solução: Repetindo o raciocínio do exercício quinto e considerando as moças
como pertencentes a um "bloco"único, segue-se então que: há (r + 1)! possibilidades
de permutações entre os r rapazes e o "bloco"de moças, estas por sua vez, podem
permutar-se de m! maneiras. Logo há (r + 1)!m! possibilidades.
Ex 7 Uma fila de cadeiras no cinema tem 20 poltronas. De quantos modos 6 casais
podem se sentar nessas poltronas de modo que nenhum marido se sente separado de
sua mulher?
Solução: Imaginando cada casal como um "bloco", temos 2 possibilidades
de permutação em cada bloco, e portanto 26 possibilidades em todos os "blocos".
Há também 6! possibilidades de se permutarem os casais nas posições que os mesmo
ocupam. Resta saber agora, o total de possibilidades que os 6 casais podem ocupar as 20 posições satisfazendo às condições do problema. Temos então 6 "blocos"representando os casais e 8 espaços vazios. Então há 14
maneiras de se escol6
.
herem seis casais específicos para ocuparem as posições deles. Logo há 26 6! 14
6
Ex 8 Mostre que:
n X
n
k=1
k
k 2 = 2n−2 n(n + 1)
2
Solução: Seja uma empresa formada por n pessoas e que se queira escolher
uma diretoria em que há um diretor e sub diretor, possivelmente sendo a mesma
pessoa.
O lado esquerdo corresponde a todas as possíveis diretorias formadas da
seguinte maneira: escolhem-se os k menbros da diretoria e depois o diretor e sub
diretor.
Agora pensemos primeiro na escolha dos diretores e depois em todas as eventuais possíveis diretorias. Há n2n−1 em que a mesma pessoa ocupa os cargos de
diretor e sub diretor. Há n(n − 1)2n−2 diretorias em qe os cargos de diretor e subdiretor são ocupados por pessoas diferentes. Como o número de diretorias formadas a
partir da escolha inicial dos diretores é a soma dessas duas possibilidades, ou seja,
n2n−1 + n(n − 1)2n−2 = 2n−2 n(n + 1), segue-se o resultado.
Ex 9 Um conjunto A possui p elementos e um conjunto B possui n elementos.
Determine o número de funções f : A→B sobrejetoras para p = n + 2.
Solução:
Se três elementos de A têm a mesma imagem em B temos um total
n(n − 1)! escolhas de funções.
Há doispares de elementos de A com imagens idênticas em B temos então
n
um total de n2 n+2
(n − 2)! escolhas de funções.
2
2
Logo, o total de funções é:
n+2
n n+2 n
n(3n + 1)(n + 2)!
n(n − 1)! +
(n − 2)! =
24
3
2
2
2
de:
n+2
3
Ex 10 Quantas partições de n elementos em k subconjuntos, com n1 , n2 , ..., nk
elementos respectivamente?
Solução: Há nn1 possibilidades de escolha para o primeiro subconjunto,
n−n1
k−1
para o segundo subconjunto,..., 1 possibilidade n−n1 −...−n
para o último
n2
nk
subconjunto.
Logo, o total de partições é:
n
n − n1
n − n1 − ... − nk−1
n!
n1 ,n2 ,...,nk
=
Pn
...
=
n1 !n2 !...nk !
n1
n2
nk
3