Prova Analise (2016.1) COM RESOLUÇÃO

Prévia do material em texto

Informática UFRGS
 
Análise Combinatória e Teoria dos Grafos 
 
Nome : Nota 
 
1) (2,0) Determine uma fórmula fechada que seja em função de n para a seguinte soma 
 
 
2) (2,0) Calcule a seguinte equação de recorrência 
 
para n≥ 3, a0=3 , a1=3 e a2=7 
 
3) (2,0) Numa competição cada um dos quatros juizes deve atribuir notas de 1 a 6 para 
cada participante. Para ser finalista, um participante deve ter no mínimo 22 pontos. Use 
funções geradoras para encontrar o número de maneiras que os juízes têm para atribuir 
notas de modo que um participante seja finalista. 
 
4) (2,0) Considere um conjunto P de 30 pontos do espaço e P1 um subconjunto de 12 
pontos coplanares de P. Sabe-se que sempre que 4 pontos de P são coplanares, então eles 
são pontos de P1. Quantos são os planos que contêm pelo menos 3 pontos de P? 
 
5) (2,0) Encontrar a função geradora ordinária para a seqüência 
 
 
 
 
 
Boa Prova, 24/04/2006 
Edson Prestes 
 
Ana´lise Combinato´ria e Teoria dos Grafos
Resoluc¸a˜o da Prova - 2016/1
1.
n∑
k=0
k3Ckn5
k
→
n∑
k=0
k2k
n(n− 1)!
k(k − 1)!(n− k)!5
k
→
n∑
k=0
k2nCk−1n−15
k
→
n∑
k=0
k((k − 1) + 1)nCk−1n−15k
→
n∑
k=0
kn(k − 1) (n− 1)(n− 2)!
(k − 1)(k − 2)!(n− k)!5
k +
n∑
k=0
knCk−1n−15
k
→
n∑
k=0
kn(n− 1)Ck−2n−25k +
n∑
k=0
((k − 1) + 1)nCk−1n−15k
→
n∑
k=0
((k − 2) + 2)n(n− 1)Ck−2n−25k +
n∑
k=0
n(k − 1) (n− 1)(n− 2)!
(k − 1)(k − 2)!(n− k)!5
k +
n∑
k=0
nCk−1n−15
k
→
n∑
k=0
n(n−1)(k − 2) (n− 2)(n− 3)!
(k − 2)(k − 3)!(n− k)!5
k+2
n∑
k=0
n(n−1)Ck−2n−25k+
n∑
k=0
n(n−1)Ck−2n−25k+
n∑
k=0
nCk−1n−15
k
→
n∑
k=0
n(n− 1)(n− 2)Ck−3n−35k + 3
n∑
k=0
n(n− 1)Ck−2n−25k +
n∑
k=0
nCk−1n−15
k
→ 53n(n− 1)(n− 2)
n∑
k=0
Ck−3n−35
k−31n−k + 3× 52n(n− 1)
n∑
k=0
Ck−2n−25
k−21n−k + 5n
n∑
k=0
Ck−1n−15
k−11n−k
→ 125n(n− 1)(n− 2)(5 + 1)n−3 + 75n(n− 1)(5 + 1)n−2 + 5n(5 + 1)n−2
125n(n− 1)(n− 2)6n−3 + 75n(n− 1)6n−2 + 5n6n−1
2.
an = 3an−1 − an−2 + 3an−3,∀n ∈ N : n ≥ 3
a0 = 3
a1 = 3
a2 = 7
Primeiramente encontramos alguns valores que continuam a sequeˆncia:
a3 = 3× 7− 3 + 3× 3 a4 = 3× 27− 7 + 3× 3 a5 = 3× 83− 27 + 3× 7
a3 = 21− 3 + 9 a4 = 81− 7 + 9 a5 = 249− 27 + 21
a3 = 27 a4 = 83 a5 = 243
Em seguida buscamos as ra´ızes da equac¸a˜o:
→ αn = 3αn−1 − αn−2 + 3αn−3
→ αn − 3αn−1 + αn−2 − 3αn−3 = 0/αn−3
→ α3 − 3α2 + α− 3 = 0
→ α2(α− 3) + α− 3 = 0
→ (α2 + 1)(α− 3) = 0
α2 + 1 = 0 α− 3 = 0
α2 = −1 α = 3
α = ±√−1
α = ±i
1
→ A(i)n +B(−i)n + C(3)n = αn
A+B + C = 3 Ai−Bi+ 3C = 3 −A−B + 9C = 7
Do qual se substituirmos A, B e C por 1 obtemos:
1 + 1 + 1 = 3 i− i+ 3 = 3 −1− 1 + 9 = 7
3 = 3 3 = 3 7 = 7
Logo:
an = (i)
n + (−i)n + (3)n
Podemos testar tal fo´rmula com os pro´ximos valores da sequeˆncia que obtivemos anteriormente:
27 = (i)3 + (−i)3 + (3)3 83 = (i)4 + (−i)4 + (3)4 243 = (i)5 + (−i)5 + (3)5
27 = −i+ i+ 27 83 = 1 + 1 + 81 243 = i− i+ 243
27 = 27 83 = 83 243 = 243
3. Segundo o enunciado podemos obter valores dentro do intervalo [1, 6] onde n = 4 do qual representa o
voto de cada um dos ju´ızes que devem ser ≥ 22, logo devemos encontrar a soma dos coeficientes de [x22],
[x23] e [x24]. Com isso temos a func¸a˜o geradora (x+x2 +x3 +x4 +x5 +x6)4 da qual podemos manipula´-la
da seguinte forma:
→ (x+ x2 + x3 + x4 + x5 + x6)4
→ x4(1 + x+ x2 + x3 + x4 + x5)4
→ x4
(
1− x6
1− x
)4
→ x4(1− x6)4(1− x)−4
Agora basta encontrarmos os coeficientes de cada uma das possibilidades:
[x22]x4(1− x6)4(1− x)−4
[x18](1− x6)4(1− x)−4
(
4
0
)(−4
18
)
+ (−1)×
(
4
1
)(−4
12
)
+
(
4
2
)(−4
6
)
+ (−1)×
(
4
3
)(−4
0
)
(
4
0
)(
21
18
)
+ (−1)×
(
4
1
)(
15
12
)
+
(
4
2
)(
9
6
)
+ (−1)×
(
4
3
)(
3
0
)
1× 1330 + (−1)× 4× 455 + 6× 84 + (−1)× 4× 1
1330 − 1820 + 504 − 4 = 10
[x23]x4(1− x6)4(1− x)−4
[x19](1− x6)4(1− x)−4
(
4
0
)(−4
19
)
+ (−1)×
(
4
1
)(−4
13
)
+
(
4
2
)(−4
7
)
+ (−1)×
(
4
3
)(−4
1
)
(
4
0
)(
22
19
)
+ (−1)×
(
4
1
)(
16
13
)
+
(
4
2
)(
10
7
)
+ (−1)×
(
4
3
)(
4
1
)
1× 1540 + (−1)× 4× 560 + 6× 120 + (−1)× 4× 4
1540 − 2240 + 720 − 16 = 4
2
[x24]x4(1− x6)4(1− x)−4
[x20](1− x6)4(1− x)−4
(
4
0
)(−4
20
)
+ (−1)×
(
4
1
)(−4
14
)
+
(
4
2
)(−4
8
)
+ (−1)×
(
4
3
)(−4
2
)
(
4
0
)(
23
20
)
+ (−1)×
(
4
1
)(
17
14
)
+
(
4
2
)(
11
8
)
+ (−1)×
(
4
3
)(
5
2
)
1× 1771 + (−1)× 4× 680 + 6× 165 + (−1)× 4× 10
1771 − 2720 + 990 − 40 = 1
10 + 4 + 1 = 15
4. Segundo o enunciado, temos dois conjuntos de pontos no R3:
• P que possui 30 pontos;
• P1 que possui 12 pontos coplanares entre si e que sa˜o subconjunto de P;
E´ dito tambe´m que os u´nicos pontos coplanares de P ⊂ P1, logo todos os pontos na˜o coplanares de P na˜o
esta˜o em P1. Para criarmos um plano e´ preciso de somente 3 pontos. Podemos ter mais de 3, pore´m para
isso os pontos a mais devem ser coplanares aos 3 anteriores. Com isso nos obtemos os 4 casos poss´ıveis:
I) Caso todos sejam de P1:
Sabendo disso basta escolher Cp12 sendo p a quantidade de pontos que queremos para criar o plano,
pore´m mesmo gerando infinitas possibilidades sempre estaremos nos tratando do mesmo plano ja´ que
todos os pontos de P1 sa˜o coplanares, logo tiramos desse caso 1 plano.
II) Caso nenhum ponto fac¸a parte de P1:
Se nenhum ponto faz parte de P1 escolhemos enta˜o os p pontos de P que na˜o esta˜o em P1, logo
ficamos com Cp18, pore´m precisamos que p ≥ 3 para obter um plano e que p < 4 pois, como os pontos
que na˜o pertencem a P1 na˜o sa˜o coplanares, na˜o obteremos um plano com isso, logo tiramos desse
caso C318.
III) Caso apenas 1 ponto fac¸a parte de P1:
Selecionamos enta˜o C112 e p pontos para escolher com a C
p
18, pore´m na˜o podemos escolher mais de 2
pontos juntos com o ponto de P1 teremos 4 ou mais pontos na˜o coplanares dos quais na˜o formara˜o
um plano, logo desse caso tiramos C112C
2
18.
IV) Caso apenas 2 pontos fac¸a parte de P1:
Selecionamos enta˜o C212 e, como no caso anterior, na˜o podemos escolher mais de 1 ponto que na˜o
pertence a P1, logo desse caso tiramos C212C
1
18.
Somando todas as 4 possibilidades obteremos:
1 + C318 + C
1
12C
2
18 + C
2
12C
1
18 = 3841
5. Para resolver este exerc´ıcio utilizamos uma das propriedades das func¸o˜es geradores ordina´rias:
1
1− cxp = (cx
p)0 + (cxp)1 + (cxp)2 + (cxp)3 + (cxp)4 + . . .+ (cxp)k
ak = c
0 + c1 + c2 + c3 + c4 + . . .+ ck
Basta substituir c por 2 e p por 1 na func¸a˜o obtendo:
ak = 1 + 2
1 + 22 + 23 + 24 + . . .+ 2k
1
1− 2x = 1 + 2x+ 2
2x2 + 23x3 + 24x4 + . . .+ 2kxk
3