Slides_16_0607

Prévia do material em texto

Matemática Discreta
Aula nº 16
Francisco Restivo
2007-05-03
2
Relações de recorrência:
Dados n objectos distintos, é fácil verificar que para cada arranjo 
de n objectos r – 1 a r – 1, sobram n – r + 1 objectos e portanto o 
número de arranjos de n r a r é
A(n, r) = A(n, r – 1).(n – r + 1).
Esta é uma relação de recorrência. Sabendo-se que A(n, 1) = n, é
possível determinar A(n, r) para qualquer r
A(n, r) = n.(n – 1)...(n – r + 1)
Há casos em que não é fácil determinar uma expressão fechada 
para o termo de ordem n. Um exemplo é a série de Fibonaci
f0 = f1 = 1
fn = fn-1 + fn-2
{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...}
Mas há!
r – 1 n – r + 1 
3
Experimentem...
1n1n
n 2
51
5
1
2
51
5
1f
++
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−⎟⎟⎠
⎞⎜⎜⎝
⎛ +=
Dada uma sucessão de números a0, a1, a2, . . . , an, . . . chama-se
relação de recorrência a uma equação que relaciona o termo an
com os termos que o antecedem e que é válida para todo o n 
maior que um dado inteiro fixado n0.
As relações de recorrência estudam-se com equações de 
diferenças, que estarão para a matemática discreta como as 
equações diferenciais estão para a análise matemática.
Exemplo:
A relação de recorrência
an = nan−1, n = 1, 2, 3, . . .
com a condição incial a0 = 1 tem a seguinte solução
an = n!, n = 0, 1, 2, 3, . . .
4
Funções geradoras:
A função geradora da sequência 1, 1, 1, 1, . . . é
A função geradora da sequência 2, 4, 1, 1, 1, 1, . . . é
x1
1x...xxx1g(x)
0n
n32
−==++++= ∑
∞
=
x1
13x1...xxx4x2g(x) 432 −++=+++++=
Somando-se as sequências, somam-se as funções geradoras
Exemplo: qual é a função geradora da sequência 3, 1, 3, 1, 3, ...?
Como 3, 1, 3, 1, 3 ... = 1, 1, 1, 1, 1, ... + 2, 0, 2, 0, 2, ... tem-se
2x1
2
x1
1g(x) −+−=
5
Mais um exemplo: função geradora de 1, 2, 3, 4, ...?
Como
( )2
432
43232
x1
1
x1
x
dx
d...)xxx(x
dx
dg(x)
...)xxx(x
dx
d...4x3x2x1
−=−=++++=
++++=++++
Multiplicar uma função geradora por xk equivale a atrasar de k a 
sequência original: a sequência 0, 0, 0, 0, 0, 1, 1, 1, 1, ... tem por 
função geradora
x1
1xg(x) 5 −=
Função geradora de n2 + n? (0, 12, 22, 32, 42, ...) + (0, 1, 2, 3, 4, ...)
( ) ( ) ( ) ( ) ...=−+−=−++++= 22232 x1 1x1 xdxdx1 1...3x2xxdxdg(x)x1
6
Problema:
Determinar o número de soluções inteiras da equação 
a + b + c = 10 
onde cada variável só pode tomar valores inteiros entre 2 e 4.
Neste caso, é simples descobrir as seis soluções possíveis
Aplicações:
a b c
2 4 4
3 3 4
3 4 3
4 2 4
4 3 3
4 4 2
Como se poderia encontrar este resultado?
Se associarmos a cada variável um polinómio x2 + x3 + x4, o 
número pedido é o coeficiente de x10 do polinómio
p(x) = (x2 + x3 + x4)(x2 + x3 + x4)(x2 + x3 + x4)
7
p(x) = (x2 + x3 + x4)(x2 + x3 + x4)(x2 + x3 + x4)
= (x4 + 2x5 + 3x6 + 2x7 + x8)(x2 + x3 + x4)
= x6 + x7 + x8 + 2x7 + 2x8 + 2x9 + 3x8 + 3x9 + 3x10 + 2x9 + 2x10 + 2x11 + x10 + x11 + x12
= · · · + (3 + 2 + 1)x10 + · · ·
O resultado é 6. p(x) resolve para as 7 somas possíveis.
Definição:
Chama-se série de potências a uma série da forma 
a0 + a1x + a2x2 + · · · + anxn + · · ·
onde an (n = 0, 1, 2, 3, . . .) são números reais ou complexos e x 
designa uma variável.
Se an (n = 0, 1, 2, . . .) for, para cada n, o número de soluções de 
um dado problema combinatório, chama-se função geradora 
ordinária para aquele problema combinatório à série de potências
g(x) = a0 + a1x + a2x2 + · · · + anxn + · · ·
Qualquer polinómio é uma série de potências particular.
p(x) = x6 + 3x7 + 6x8 + 7x9 + 6x10 + 3x11+ x12
8
Problema:
Determinar a função geradora ordinária na qual o coeficiente de
xr seja o número de soluções inteiras não negativas da equação
2a + 3b + 5c = r.
Escrevendo x = 2a, y = 3b e z = 5c procura-se então o número de
soluções inteiras não negativas da equação
x + y + z = r
onde 
x ∈ {0, 2, 4, 6, 8, . . .}, y ∈ {0, 3, 6, 9, . . .} e z ∈ {0, 5, 10, 15, 20, . . .}.
Então, associando às variáveis x, y, z as séries de potências
gx(t) = 1 + t2 + t4 + t6 + · · ·
gy(t) = 1 + t3 + t6 + t9 + · · ·
gz(t) = 1 + t5 + t10 + t15 + · · ·
a função geradora ordinária associada a este problema é dada por
g(t) = (1 + t2 + t4 + t6 + · · ·)(1 + t3 + t6 + t9 + · · ·)(1 + t5 + t10 + t15 + · · ·)
532 t1
1
t1
1
t1
1g(t) −−−=
9
Teorema:
Seja ar o coeficiente de xr na função geradora ordinária
g(x) = (1 + x + x2 + x3 + x4 + x5 + · · ·)n
Então ar = C(r+n-1, r).
Teorema:
Verifica-se que 
(1 - xm)n = 1 – C(n, 1)xm + C(n, 2)x2m - · · · + (-1)nxnm
Teorema:
Verifica-se que
(1 + x + x2 + x3 + · · · + xm-1)n = (1 - xm)n(1 + x + x2 + · · ·)n
Corolário (regra dos separadores):
A função g(x) é a função geradora associada ao problema
da determinação do número de soluções inteiras não negativas da 
equação
y1 + y2 + · · · + yn = r
que é, assim, igual a C(r+n-1, r).
10
Problema: 
Determinar o número de soluções inteiras da equação
a + b + c + d = 27
onde cada variável toma valores entre 3 e 8.
A solução deste problema é o coeficiente de x27 na função 
geradora
Pensando como se pode obter o termo x27, é fácil ver que há três 
contribuições, a primeira podendo ser x0, x6, x12, …, a segunda x12
e a terceira qualquer. Há assim três formas distintas:
x0.x12.x15 = 1.C(18, 15) = 3 × 17 × 16 
x6.x12.x9 = -C(4, 1).C(12, 9) = - 4 × 2 × 11 × 10 
x12.x12.x3 = C(4, 2)C(6,3) = 2 × 3 × 5 × 4 
que totalizam 56.
454321246
4543212
4876543
...)xxxxx(1x)x(1
)xxxxx(1x
)xxxxx(xg(x)
++++++−=
+++++=
+++++=
11
Relações de recorrência e funções geradoras:
Dada uma sucessão (an), n=0,1,2,... seja
g(x) = a0 + a1x + a2x2 + · · · + anxn + · · ·
a função geradora associada aquela sucessão. Esta função 
geradora g(x) contém toda a informação relativa à sucessão (an), 
n=0,1,2,... sendo muitas vezes mais fácil de manipular do que a 
própria sucessão.
O termo geral da sucessão, an, pode ser recuperado a partir do 
coeficiente de xn no desenvolvimento em série de potências de 
g(x). Muitas vezes é possível obter g(x) algebricamente e então, 
depois de expressar esta função em série de potências, obtêm-se 
os termos an da sucessão correspondente.
12
Exemplo:
Resolver a relação de recorrência an = 2an-1.
Multiplicando os dois termos desta igualdade pelas potências 
sucessivas xn e somando, obtem-se
a1x + a2x2 + · · · + anxn + · · · = 2(a0x + a1x2 + a2x3 + · · · + an-1xn + · · ·)
-a0+(a0+a1x+a2x2+· · ·+anxn+· · ·) = 2x(a0+a1x+a2x2+· · ·+an-1xn-1+· · ·)
-a0 + g(x) = 2xg(x)
g(x) = a0(1+2x+22x2+23x3+…+2nxn+…)
an = a0.2n
	Matemática Discreta