p2_1_2014

Prévia do material em texto

UERJ - Universidade do Estado do Rio de Janeiro 
Instituto de Matemática e Estatística 
Departamento de Matemática Aplicada 
Disciplina: Matemática Discreta 
Professor: Augusto César de Castro Barbosa 
2a Prova 12/08/2014 
Nome:____________________________________________________________ 
__________________________________________________________________ 
 
1 – Encontrar o número de soluções em inteiros positivos para a inequação 
 
6xxxx0 4321 ≤+++< . 
 
(Exemplo 3.6, resolvido em sala de aula) 
 
2 – Quantas permutações dos inteiros 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, têm exatamente 
4 dos números em suas posições originais. 
(Exemplo 4.10, resolvido em sala de aula) 
 
3 – Utilizando funções geradoras, encontrar o número de maneiras nas quais 4 
pessoas, cada uma jogando um único dado, podem obter um total de 17. 
(Exemplo 5.16, resolvido em sala de aula) 
 
4 – De quantas maneiras podemos permutar 3 a’s, 3 b’s e 3 c’s de tal modo que 3 
letras iguais nunca sejam adjacentes? 
(Lista 7, exercício 6) 
 
 
Observação: Não serão consideradas respostas sem os cálculos correspondentes! 
 
Tempo de prova: 1 h 20 min 
 
Pontuação: 2,5 pontos por questão 
 
 
 
BOA PROVA 
 
 
 
 
 
 
 
 
 
 
 
FORMULÁRIO 
 
 
n!12...2)1)(nn(nPn =⋅⋅⋅−−= . 
p)!(n
n!1))(p2)...(n1)(nn(nA pn,
−
=−−−−=
 . 
p)!(np!
n!
p!
A
C pn,pn,
−
==
 
pnn,pn, CC −=
 
1n
1pn
p
n CCR
−
−+= 
!!...nn!n!n
n!)n,...,n,nPR(n;
r321
r21 =
 
p
pm, m(AR) = 
1)!(n
n
n!(PC)n −==
 
∑
=
−
=+
n
0i
inii
n
n baCb)(a
 






−





−





−=
r21 p
11...
p
11
p
11m φ(m) 
∑∑∑
≤<<≤≤<≤=
+−=
nkji1
kji
nji1
ji
n
1i
in21 )AAn(A)An(A)n(A)A...An(A IIIUUU 
∑
≤<<<≤
−
npkji1
pkji )AAAn(A III +...+ )A...An(A1)( n211-n III− 






−++−+−=
n!
11)(...
3!
1
2!
1
1!
11n!D nn
 
∑
=
−−=
k
0i
p
ik,
i )ik(C1)(k)T(p,
 
 ...x
!r
1)r)...(u1u(u
...x
!3
)2)(u1u(u
x
!2
)1u(u
ux1x)(1 r32u ++−−++−−+−++=+ 
 
r
0r
x
r
u
∑
∞
=






=
 




=
>
+−−
=





0r, 1
0r, 
!r
1)r)...(u1u(u
r
u
 





 −+
−=




−
r 
1rn)1(
r 
n r
 
...
r!
x
...
4!
x
3!
x
2!
x
x1e
r432
x +++++++=
∑
=
−





−==
k
0i
ni )ik(
i
k)1(
k!
1k)T(n,
k!
1k)S(n,
 
p
1pnCp)f(n, +−= 
 
 
GABARITO 
 
 
1 – Devemos contar o número de soluções em inteiros positivos para as seguintes 
equações: 
 
1xxxx 4321 =+++ , 
 
2xxxx 4321 =+++ , 
 
3xxxx 4321 =+++ , 
 
4xxxx 4321 =+++ , 
 
5xxxx 4321 =+++ , 
 
6xxxx 4321 =+++ . 
 
 
O número de soluções em inteiros positivos para cada uma das três primeiras 
equações é zero. Para as últimas três, temos 
 
151041CCCCCCN 35343314 1614 1514 14 =++=++=++= −−−−−− . 
 
2 – Os 4 números que permanecem nas posições originais podem ser escolhidos 
de 410C maneiras distintas. Devemos então multiplicar esse número pela 
permutação caótica dos 6 números restantes. Assim, 
 
 
55650
6!
1
5!
1
4!
1
3!
1
2!
1
1!
116!
!6!4
!10DCN 6
4
10 =





+−+−+−== . 
 
3 – =+++++= 465432 )xxxxx(xg(x) 
⋅=+++++⋅ 4454324 x)xxxxx(1x 4464
46
)x1()x1(x
x1
x1
−
−⋅−⋅=





−
−
 . 
 
Temos que 
 
241812646 xx4x6x41)x1( +−+−=− 
e 
 ∑
∞
=
−
−




−
=−
0r
r4 )x(
r 
4)x1( 
...x
3!
654
x
2!
54
x
1!
41 32 +⋅⋅+⋅++= 
 
Assim, o coeficiente de 13x em 446 )x1()x1( −−− é 
 
a17= 1041!
46
3!
10984
3!
615114
1!
46
7!
10...6544
13!
16...654
=+
⋅⋅
−
⋅⋅
=+
⋅⋅⋅⋅
−
⋅⋅⋅⋅
 
 
 
4 – 3a 3b 3c 
 aaa bbb ccc 
 
A → conjunto das permutações 
A1 → conjunto das permutações nas quais 3a são adjacentes 
A2 → conjunto das permutações nas quais 3b são adjacentes 
A3 → conjunto das permutações nas quais 3c são adjacentes 
9!
n(A)
3! 3! 3!
= 
 
1 2 3
7!
n(A ) n(A ) n(A )
3! 3!
= = = 
 
Exemplo: aaa bbb ccc 
 ↓ 
 7 posições 
 
1 2 1 3 2 3
5!
n(A A ) n(A A ) n(A A )
3!
∩ = ∩ = ∩ = 
 
Exemplo: aaa bbb ccc 
 ↓ 
 5 posições 
 
1 2 3n(A A A ) 3!∩ ∩ = , 
 
pois nesse caso temos aaa bbb ccc 
 ↓ 
 3 posições 
 
1 2 3n n(A) n(A A A )= − ∪ ∪ 
 
1 2 3 1 2 1 3n(A) n(A ) n(A ) n(A ) n(A A ) n(A A )= − − − + ∩ + ∩ 
 
2 3 1 2 3n(A A ) n(A A A )+ ∩ − ∩ ∩ 
 
9! 7! 5!
n 3 3 3! 1314
3! 3! 3! 3! 3! 3!
= − + − =