Problemas de Combinatória e Probabilidade

Prévia do material em texto

1- a) ​ Quantas maneiras diferentes podemos selecionar 5 letras de 
um conjunto de: 5A, 6B, 4C, 3D. Sabendo que A e B devem 
comparecer pelo menos uma vez ? 
 
b)​ Quantos anagramas podemos formar ? 
 
2- a) ​ Encontre a função geradora do problema com 
as condições: , e . 
 
b)​ Calcule o número de soluções que geram soma 16. 
 
3)​ Qual é a probabilidade de fazer 13, 14 ou 15 lançando 4 dados. 
 
4)​ Considerando os 3 blocos de cores diferentes: 
 
Sabendo que temos N blocos de cada cor, quantos blocos 
diferentes de N podemos formar ? 
 
 
 
 
 
 
 
 
 
 
 
 
Resolução do teste do dia 16/11
November 18, 2016
1 Letras disponíveis: 7A, 8B, 9C, 10D
1. Conjuntos de 5 e 6 letras
2. Anagramas de 5 e 6 letras
Resolução:
CASO 1: Como queremos conjuntos nesse caso, a ordem entre as letras não importa. Assim,
teremos as seguintes funções geradoras para cada letra disponível:
A : 1 + x+ x2 + x3 + x4 + x5 + x6 + x7 =
1− x8
1− x
B : 1 + x+ x2 + x3 + x4 + x5 + x6 + x7 + x8 =
1− x9
1− x
C : 1 + x+ x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 =
1− x10
1− x
D : 1 + x+ x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 =
1− x11
1− x
OBS: A forma simplificada saiu da fórmula da soma dos elementos de uma progressão geométrica
de razão x.
Como temos mais de 6 letras de cada uma disponível e não estamos interessados nos casos
em que pegamos 7 A’s ou 8 C’s, simplificaremos a nossa vida diminuindo as funções geradoras
respectivas para podermos pegar no máximo 6 de cada letra:
F (A) : 1 + x+ x2 + x3 + x4 + x5 + x6 =
1− x7
1− x
F (B) : 1 + x+ x2 + x3 + x4 + x5 + x6 =
1− x7
1− x
F (C) : 1 + x+ x2 + x3 + x4 + x5 + x6 =
1− x7
1− x
F (D) : 1 + x+ x2 + x3 + x4 + x5 + x6 =
1− x7
1− x
Dessa forma, temos a nossa função geradora (f):
f = F (A) · F (B) · F (C) · F (D) = (1− x
7)4
(1− x)4
Para encontrarmos o número de combinações possíveis com 5 e 6 letras, devemos encontrar os
termos de ordem x5 e x6, respectivamente.
Para isso, precisaremos de duas fórmulas:
1
(1− xa)N
=
∞∑
r=0
(
N + r − 1
r
)
xar (1)
1
(1− xa)N =
N∑
r=0
(
N
r
)
(−1)rxar (2)
Aplicando (1) e (2) em f, temos:
f =
∞∑
r=0
(
3 + r
r
)
xr
4∑
s=0
(
4
s
)
(−1)sx7s
Para acharmos o termo de ordem x5, r e s devem ser 5 e 0, respectivamente:(
3 + 5
5
)
=
(
8
5
)
=
8!
5!3!
=
8 · 7 · 6
3 · 2 · 1
= 8 · 7 = 56
Para acharmos o termo de ordem x6, r e s devem ser 6 e 0, respectivamente:(
3 + 6
6
)
=
(
9
6
)
=
9!
6!3!
=
9 · 8 · 7
3 · 2 · 1
= 3 · 4 · 7 = 82
CASO 2: Neste caso a ordem nos importa. Assim, teremos as seguintes funções geradoras para
cada letra disponível:
A : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
+
x7
7!
B : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
+
x7
7!
+
x8
8!
C : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
+
x7
7!
+
x8
8!
+
x9
9!
D : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
+
x7
7!
+
x8
8!
+
x9
9!
+
x10
10!
Novamente temos mais de 6 letras de cada uma disponível e não estamos interessados nos casos
em que pegamos 7 A’s ou 8 C’s, simplificaremos a nossa vida diminuindo as funções geradoras
respectivas para podermos pegar no máximo 6 de cada letra:
A : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
B : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
C : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
D : 1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
Dessa forma, temos a nossa função geradora:
f =
(
1 + x+
x2
2!
+
x3
3!
+
x4
4!
+
x5
5!
+
x6
6!
)4
Mas, sabemos que
expx =
∞∑
i=0
xi
i!
Como não estamos interessados nos termos de ordem superior a 6, podemos dizer que
f = (expx)4 = exp4x =
∞∑
i=0
(4x)i
i!
2
Para acharmos o termo que multiplica x
5
5! , i deve ser 5:
45 = 1024
Para acharmos o termo que multiplica x
6
6! , i deve ser 6:
46 = 4096
2 Soma de inteiros X1 + 4X2 = 5, 12, 23
1. 1 ≤ X1 ≤ 4
X2 ≥ 1
2. 1 ≤ X1 ≤ 4
X2 ≥ 2
CASO 1: 4X2 ≥ 4
Assim, teremos as seguintes funções geradoras para cada variável:
X1 : x+ x
2 + x3 + x4 = x(1 + x+ x2 + x3) = x
1− x4
1− x
X2 : x
4 + x8 + x12 + ... = x4(1 + x4 + x8 + ...) =
x4
1− x4
OBS: As formas simplificadas sairam da fórmula da soma (infinita para X2) dos elementos
de uma progressão geométrica de razão x.
Dessa forma, temos a nossa função geradora (f):
f = F (X1) · F (X2) =
x5
(1− x)
Para encontrarmos o número de valores possíveis para X1 e X2 que fazem a soma dar 5, 12
e 23, devemos encontrar os termos de ordem x5, x12 e x23, respectivamente.
Para isso, precisaremos de uma fórmula:
1
(1− xa)N
=
∞∑
r=0
(
N + r − 1
r
)
xar (1)
Aplicando-a em f, temos:
f = x5
∞∑
r=0
(
r
r
)
xr
Para acharmos o termo de ordem x5, r deve ser 0:(
0
0
)
= 1
3
Para acharmos o termo de ordem x12, r deve ser 6:(
6
6
)
= 1
E, para acharmos o termo de ordem x23, r deve ser 18:(
18
18
)
= 1
CASO 2: 4X2 ≥ 8
Assim, teremos as seguintes funções geradoras para cada variável:
X1 : x+ x
2 + x3 + x4 = x(1 + x+ x2 + x3) = x
1− x4
1− x
X2 : x
8 + x12 + x16 + ... = x8(1 + x4 + x8 + ...) =
x8
1− x4
OBS: As formas simplificadas sairam da fórmula da soma (infinita para X2) dos elementos
de uma progressão geométrica de razão x.
Dessa forma, temos a nossa função geradora (f):
f = F (X1) · F (X2) =
x9
(1− x)
Para encontrarmos o número de valores possíveis para X1 e X2 que fazem a soma dar 5, 12
e 23, devemos encontrar os termos de ordem x5, x12 e x23, respectivamente.
Para isso, precisaremos de uma fórmula:
1
(1− xa)N
=
∞∑
r=0
(
N + r − 1
r
)
xar
Aplicando-a em f, temos:
f = x9
∞∑
r=0
(
r
r
)
xr
Repare que os termo de ordem inferior a x9 são 0, assim, não existe a possibilidade da soma
dar 5 com tais restrições.
Para acharmos o termo de ordem x12, r deve ser 3:(
3
3
)
= 1
E, para acharmos o termo de ordem x23, r deve ser 14:(
14
14
)
= 1
4
3 Probabilidade de, lançando 4 dados, a soma dar 9 ou
10
Temos a seguinte função geradora para cada dado:
x+ x2 + x3 + x4 + x5 + x6 = x(1 + x+ x2 + x3 + x4 + x5) = x
1− x6
1− x
OBS: A forma simplificada saiu da fórmula da soma dos elementos de uma progressão ge-
ométrica de razão x.
Mas, como temos 4 funções geradoras iguas(4 dados), a nossa função geradora geral será a
de um dado elevada a quarta potência:
f =
(
x
1− x6
1− x
)4
=
x4(1− 4x6 + 6x12 − 4x18 + x24)
(1− x)4
=
x4 − 4x10 + 6x16 − 4x22 + x28
(1− x)4
Para encontrarmos o numero de possibilidades da soma dar 9 ou 10, devemos encontrar os
termos de ordem x9, x10, respectivamente.
Para isso, precisaremos de uma fórmula:
1
(1− xa)N
=
∞∑
r=0
(
N + r − 1
r
)
xar
Aplicando-a em f, temos:
f = (x4 − 4x10 + 6x16 − 4x22 + x28)
∞∑
r=0
(
3 + r
r
)
xr
Para acharmos o termo de ordem x9, r deve ser 5:(
3 + 5
5
)
=
(
8
5
)
=
8!
3!5!
=
8 · 7 · 6
3 · 2 · 1
= 56
E, para acharmos o termo de ordem x10, r deve ser 6 ou 0:(
3 + 6
6
)
− 4
(
3 + 0
0
)
=
(
9
6
)
− 4
(
3
0
)
=
9!
6!3!
− 4 · 3!
3!0!
=
9 · 8 · 7
3 · 2 · 1
− 4 = 3 · 4 · 7− 4 = 84− 4 = 80
Então temos 56+80 = 136 possibilidades de somarmos 9 ou 10 em 4 dados dentre 64 possíveis.
Probabilidade =
136
64
=
136
1296
≈ 10, 5%
5
4 Fórmula de recorrência para blocos de N cm, sendo que
tenho blocos A e B de 1 cm e C, D e E de 2 cms
Como temos 2 blocos de 1 cm e 3 de 2 cms, temos a seguinte fórmula de recorrência:
Cn = 2Cn−1 + 3Cn−2 (I)
N = 1
A
B
Portanto, temos 2 opções.
N = 2
AB
BA
AA
BB
C
D
E
Portanto, temos 7 opções.
N = 3
AAA
AAB
ABA
BAA
BBB
BBA
BAB
ABB
CA
CB
AC
BC
DA
DB
AD
BD
AE
BE
EA
EB
6
Portanto, temos 20 opções.
De fato, se considerarmos n=3 em (I), teremos:
C3 = 2C2 + 3C1 = 2 · 7 + 3 · 2 = 14 + 6 = 20
Então, resolvendo o problema de recorrência da mesma maneira que resolvemos equações
diferencias, temos:
α2 = 2α+ 3
α2 − 2α− 3 = 0
Por Bhaskara:
α =
2±
√
4 + 12
2
=
2± 4
2
= 1± 2
α1 = 3
α2 = −1
Podemos escrever Cn como:
Cn = A(3)
n +B(−1)n
, em que A e B são constantes a serem determinadas.
Como sabemos que C3 = 20 e C2 = 7, temos:
C3 = A(3)
3 +B(−1)3 = 27A−B = 20 (II)
C2 = A(3)
2 +B(−1)2 = 9A+B= 7 (III)
(III)→ B = 7− 9A
(II)→ 27A− 7 + 9A = 36A− 7 = 20
36A = 27
A =
3
4
B = 7− 9 · 3
4
= 7− 27
4
=
28− 27
4
=
1
4
Assim,
Cn =
3
4
· (3)n + (−1)
n
4
7
	Letras disponíveis: 7A, 8B, 9C, 10D
	Soma de inteiros X1+4X2=5,12,23
	Probabilidade de, lançando 4 dados, a soma dar 9 ou 10
	Fórmula de recorrência para blocos de N cm, sendo que tenho blocos A e B de 1 cm e C, D e E de 2 cms