9-Combinações-repetições

Prévia do material em texto

Lembrando: Permutac¸a˜o com repetic¸a˜o
Vamos considerar o seguinte problema:
De quantas maneiras podemos arrumar 5 trac¸os e 8 pontos?
I Para resolver este problema, vamos arrumar 13 objetos, sendo
8 deles pontos e 5 trac¸os, usamos a permutac¸a˜o com
repetic¸a˜o:
P5,813 =
13!
5!8!
= 1.287
ou seja, temos 1.287 maneiras de arrumar 8 pontos e 5 trac¸os.
1 / 20
Continuac¸a˜o do problema
I E se usarmos apenas 7 deles? (7 dos 13 objetos)
Podemos ter:
I 5 trac¸os e 2 pontos
I 4 trac¸os e 3 pontos
I 3 trac¸os e 4 pontos
I 2 trac¸os e 5 pontos
I 1 trac¸os e 6 pontos
I 0 trac¸os e 7 pontos
exclusivos.
I Neste caso, teremos, pelo princ´ıpio aditivo:
P5,27 + P
4,3
7 + P
3,4
7 + P
2,5
7 + P
1,6
7 + P
0,7
7 = 120
2 / 20
Permutac¸a˜o com repetic¸a˜o
De uma maneira geral, queremos arrumar n objetos sendo que:
I n1 sa˜o do tipo 1;
I n2 sa˜o do tipo 2;
I ...
I nk sa˜o do tipo k,
onde n1 + n2 + · · ·+ nk = n
Pn1,n2,··· ,nkn =
n!
n1! · · · nk !
3 / 20
Combinac¸o˜es com repetic¸a˜o (Combinac¸o˜es completas)
Se uma loja tem 7 sabores de sorvete, quantas maneiras e´
poss´ıvel comprar 4 sorvetes?
Se os 4 sabores sa˜o diferentes, temos C 47 = 35 maneiras de
escolher, mas, posso querer comprar, por exemplo: 1 sorvete
de chocolate, 2 de morango e 1 de flocos.
Enta˜o, como deveremos proceder para resolver este problema?
4 / 20
Notac¸a˜o
I Denote por CR47 o nu´mero de modos de escolher 4 sorvetes
entre sabores distintos, valendo escolher o mesmo sabor mais
de 1 vez.
I De uma maneira geral
I CRpn e´ o nu´mero de modos de escolher p objetos, distintos ou
na˜o, entre n objetos dados, podendo escolher o mesmo objeto
mais de 1 vez.
5 / 20
Soluc¸a˜o do problema
I Para efetuar a compra dos 4 sorvetes, escolhendo entre 7
sabores distintos dados, considere as varia´veis
x1, x2, x3, x4, x5, x6 e x7, definidas como segue:
I x1 quantidade do sorvete de sabor 1;
I x2 quantidade do sorvete de sabor 2;
I ...
I x7 quantidade do sorvete de sabor 7,
onde x1, x2, x3, x4, x5, x6, x7 ≥ 0
I Comprar 4 sorvetes, nestas condic¸o˜es, e´ o mesmo que
encontrar uma soluc¸a˜o inteira na˜o-negativa, (xi ≥ 0), para a
equac¸a˜o:
x1 + x2 + x3 + x4 + x5 + x6 + x7 = 4
onde xi ≥ 0
6 / 20
Equivaleˆncia
Portanto, sa˜o equivalentes:
1. CRpn e´ o nu´mero de modos de escolher p objetos, distintos ou
na˜o, entre n objetos distintos dados, podendo escolher o
mesmo objeto mais de 1 vez.
2. CRpn e´ o nu´mero de soluc¸o˜es inteiras na˜o-negativas da
equac¸a˜o x1 + x2 + · · ·+ xn = p, onde xi ≥ 0.
7 / 20
Resolvendo o problema
I CR47 e´ o nu´mero de soluc¸o˜es em inteiros na˜o-negativos da
equac¸a˜o x1 + x2 + x3 + x4 + x5 + x6 + x7 = 4 onde xi ≥ 0,
para i = 1, · · · , 7.
Seja a representac¸a˜o no esquema bola-trac¸o (cada bola
representa uma unidade no valor da inco´gnita; cada trac¸o e´
usado para separar duas inco´gnitas):
8 / 20
Continuac¸a˜o
I Para formar uma representac¸a˜o devemos arrumar em fila 4
bolas e 6 trac¸os, isto e´, para cada soluc¸a˜o da equac¸a˜o
x1 + x2 + x3 + x4 + x5 + x6 + x7 = 4 (∗),
Logo, o nu´mero de soluc¸o˜es de (∗) = nu´mero de maneiras de
arrumar 6 trac¸os e 4 bolas, que e´ dado por:
P4,64+6 =
10!
4!6!
= C 410,
logo, CR47 = C
4
10 = 210
9 / 20
Caso Geral
I Para Calcular CRpn , isto e´, determinar o nu´mero de soluc¸o˜es
inteiras na˜o-negativas de x1 + · · ·+ xn = p, xi ≥ 0, ter´ıamos
que arrumar p bolas e n − 1 trac¸os. Logo,
CRpn = P
p,n−1
p+n−1 = C
p
n+p−1
10 / 20
Exemplo 1
I Quantas sa˜o as soluc¸o˜es inteiras e na˜o-negativas de
x + y + z + w = 9
Este problema e´ equivalente a:
I De quantos modos e´ poss´ıvel escolher 9 objetos (valendo
repetic¸o˜es) entre 4 objetos distintos.
Soluc¸a˜o:
CR94 = C
9
12 =
12!
9!3!
11 / 20
Exemplo 2
I Quantas sa˜o as soluc¸o˜es inteiras e na˜o-negativas de
x + y + z + w ≤ 9
As soluc¸o˜es dividem-se em va´rios grupos:
I x + y + z + w = 9;
I x + y + z + w = 8;
I ...
I x + y + z + w = 0
x , y , z ,w ≥ 0 que sa˜o eventos exclusivos.
Pelo princ´ıpio aditivo:
CR94 + CR
8
4 + · · ·+ CR14 + CR04 =
= C 912 + C
8
11 + · · ·+ C 14 + C 03
12 / 20
Outra maneira de pensar para o Exemplo 2:
Em cada soluc¸a˜o inteira na˜o-negativa de x + y + z + w ≤ 9
podemos definir a folga da soluc¸a˜o por: F = 9− (x + y + z + w),
F e´ a folga e F ≥ 0.
x y z w x + y + z + w F
3 2 2 2 9 0
1 3 0 0 5 4
1 2 1 1 5 4
Observe que existe uma correspondeˆncia biun´ıvoca entre as
soluc¸o˜es inteiras na˜o-negativas de x + y + z + w ≤ 9 e as soluc¸o˜es
inteiras na˜o negativas de x + y + z + w + F = 9.
13 / 20
I Logo, o nu´mero de soluc¸o˜es inteiras na˜o-negativas de
x + y + z + w ≤ 9 e´ o mesmo que o nu´mero de soluc¸o˜es
inteiras e na˜o-negativas da equac¸a˜o x + y + z + w + F = 9,
onde x , y , z ,w ,F ≥ 0 que e´ dado por:
CR95 = C
9
13
14 / 20
Caso Geral
I Considere n objetos diferentes a1, · · · , an. Uma combinac¸a˜o
com repetic¸a˜o de n objetos distintos tomados r a r e´ uma
selec¸a˜o de r objetos distintos ou na˜o, escolhidos entre os n
objetos dados
I Problema: Dados n objetos distintos a1, · · · , an, encontrar o
nu´mero de combinac¸o˜es com repetic¸a˜o de n objetos tomados
r a r .
15 / 20
Exemplo 3
I Quantas sa˜o as soluc¸o˜es inteiras e na˜o-negativas da equac¸a˜o
x + y + z = 24 com (1) x ≥ 3, y ≥ 3, z ≥ 3?
Soluc¸a˜o Sabemos resolver o problema de contar o nu´mero de
soluc¸o˜es de x + y + z = 24 quando x , y , z ≥ 0. Para fazer um
problema recair no outro fazemos a mudanc¸a de varia´vel:
x = 3 + a;
y = 3 + b e
z = 3 + c
com a, b, c ≥ 0
16 / 20
Continuac¸a˜o
I Substituindo na equac¸a˜o
(3 + a) + (3 + b) + (3 + c) = 24⇒ a+ b + c = 24− 9 = 15
(2) a+ b + c = 15, a, b, c ≥ 0
Cuja soluc¸a˜o e´
CR153 = C
15
15+(3−1) = C
15
17 =
17!
15!2!
= 136
Cada soluc¸a˜o de (1) corresponde a uma soluc¸a˜o de (2). Logo
o nu´mero de soluc¸o˜es de (1) = nu´mero de soluc¸o˜es de (2).
17 / 20
Exemplo 4
I De quantos modos podemos colocar 5 bolas ideˆnticas em 3
caixas numeradas?
Fazendo xi = nu´mero de bolas na caixa i , xi ≥ 0.
x1 + x2 + x3 = 5, com x1, x2, x3 ≥ 0 ou seja de CR53 = C 57
modos.
18 / 20
Exemplo 5
I De quantos modos diferentes podemos distribuir 10 bombons
ideˆnticos em 4 caixas diferentes (C1,C2,C3,C4)?
x1 = nu´mero de bombons em C1;
x2 = nu´mero de bombons em C2;
x3 = nu´mero de bombons em C3;
x4 = nu´mero de bombons em C4.
E´ o mesmo que encontrar o nu´mero de soluc¸o˜es inteiras
na˜o-negativas da equac¸a˜o x1 + x2 + x3 + x4 = 10.
Logo, a soluc¸a˜o e´ CR104 = C
10
13 = 286
19 / 20
Caso geral
I O nu´mero de maneiras de distribuirmos p objetos ideˆnticos
em n caixas diferentes e´ CRpn = C
p
n+p−1
20 / 20