Resumos LEIC-A
IST LEIC-AGitHub
Edit page

Funções Geradoras

Definição

Tome-se o número de maneiras que se pode fazer xx euros com moedas de 1 euro:

1z0+1z1+1z2+1z3+…1zx1z^0+1z^1+1z^2+1z^3+\dots1z^x

Onde o coeficiente de zxz^x representa o número de formas possíveis de distribuir as moedas.

Assim, o número de maneiras que se pode fazer xx euros com moedas de 2 euros é:

1z0+0z1+1z2+0z3+⋯+0z2x−1+1z2x1z^0+0z^1+1z^2+0z^3+\dots+0z^{2x-1}+1z^{2x}

Abaixo está como averiguar o número de formas possíveis de obter 8 euros com moedas de 1 euro e de dois.

8Euros

ou, de modo geral:

cn=∑k=0nakbn−kc_n = \sum^n_{k=0} a_k b_{n-k}

Generalização e Exemplos

Em geral, uma sucessão unu_n é gerada por:

un⟶v(z)=∑k=0+∞ukzku_n \longrightarrow v(z) = \sum_{k=0}^{+\infty}u_kz^k

seja un=1,1,1,1,1,1,0,0,…u_n = 1,1,1,1,1,1,0,0,\dots:

v(z)=1+z+z2+z3+z4+z5 ouv(z)=1−z61−z=z6−1z−1v(z) = 1+z+z^2+z^3+z^4+z^5 \\ \text{ ou} \\ v(z) = \frac{1-z^6}{1-z} = \frac{z^6-1}{z-1}

ou então un=1,3,3,1,0,0,…u_n = 1,3,3,1,0,0,\dots:

v(x)=1+3z+3z2+z3=(1+z)3v(x)=1+3z+3z^2+z^3 = (1+z)^3

ou então un=1∀n∈Nu_n = 1\quad\forall_{n \in \N}:

v(z)=1+z+z2+z3+z4+…z⋅v(z)=z+z2+z3+z4+⋯⇔v(z)−z⋅v(z)=1⇔v(z)=11−zv(z)=1+z+z^2+z^3+z^4+\dots\\ z\cdot v(z)=\quad z+z^2+z^3+z^4+\dots \Leftrightarrow\\ v(z)-z\cdot v(z)=1 \Leftrightarrow\\ \\ v(z) = \frac 1 {1-z}

Com estes exemplos, já podemos conhecer a função geradora de un=n+1u_n=n+1 :

v(z)=1z0+2z1+3z2+4z3+…z⋅v(z)=z+2z2+3z3+4z4+…(1−z)v(z)=1+z+z2+z3+z4+⋯=11−z⇔v(z)=1(1−z)2v(z) =1z^0+2z^1+3z^2+4z^3+\dots\\ z\cdot v(z)=z+2z^2+3z^3+4z^4+\dots\\ \\ (1-z)v(z)= 1+z+z^2+z^3+z^4+\dots=\frac 1 {1-z} \Leftrightarrow \\ v(z) = \frac 1 {(1-z)^2}

Repare-se que a partir desta fórmula pode-se também chegar a geradora de un=nu_n=n:

un=n+1  ⟹  v(z)n+1=∑k=0+∞(k+1)zk=∑k=0+∞kzk+∑k=0+∞zku_n=n+1 \implies v(z) _{n+1}=\sum_{k=0}^{+\infty}(k+1)z^k = \sum_{k=0}^{+\infty}kz^k+\sum_{k=0}^{+\infty}z^k

onde o primeiro somatório da última igualdade representa a geradora da sucessão un=nu_n=n. Assim, viria:

v(z)n=z(1−z)2v(z)_{n} = \frac{z}{(1-z)^2}

Agora, para un=3nu_n=3^n:

v(z)=∑k=0+∞3kzk=∑k=0+∞(3z)k=(11−w)w=3z=11−3zv(z)=\sum_{k=0}^{+\infty}3^kz^k\\ = \sum_{k=0}^{+\infty}(3z)^k = \left(\frac 1 {1-w}\right)_{w=3z} = \frac 1 {1-3z}

Ou, de um modo geral:

un=an  ⟹  v(z)un=11−azu_n=a^n\implies v(z)_{u_n}=\frac 1 {1-az}

Já agora, a função geradora para as moedas de dois euros seria:

D(z)=∑k=0+∞(z2)k=11−z2D(z) = \sum_{k=0}^{+\infty}(z^2)^k = \frac 1 {1-z^2}

Voltando agora ao exemplo inicial, vamos ver quantas formas há de obter xx euros a partir de moedas de 1 e 2 euros:

G(z)=v(z)D(z)=1(1−z)(1−z2)=1(1−z)2(1−(−z))G(z) = v(z)D(z) = \frac 1 {(1-z)(1-z^2)} = \frac 1 {(1-z)^2(1-(-z))}

Agora, tem-se:

1(1−z)2(1−(−z))=141−z+12(1−z)2+141−(−z)\frac 1 {(1-z)^2(1-(-z))} = \frac{\frac 1 4}{1-z}+\frac{\frac 1 2}{(1-z)^2}+\frac{\frac 1 4}{1-(-z)}

agora, relacionando com as fórmulas já vistas:

1(1−z)2(1−(−z))=14×1+14(n+1)+14×(−1)n 2n+3+(−1)n4\frac 1 {(1-z)^2(1-(-z))}= \frac 1 4\times 1+\frac 1 4(n+1)+\frac 1 4\times(-1)^n \\~\\ \frac {2n+3+(-1)^n}{4}

Exemplo, há 2(6)+3+(−1)64=4\frac{2(6)+3+(-1)^6}{4} = 4 formas possíveis de formar 66 euros a partir de moedas de 1 e 2 euros.