[MCTB019-17] §10 — Funções geradoras

De quantas maneiras distintas podemos lançar uma dado quatro vezes de modo que os resultados somam 14?

O resultado do primeiro lançamento é representado por um polinômio

$\displaystyle x^1 + x^2 + x^3 + x^4 + x^5 + x^6 \ \ \ \ \ (66)$

O símbolo ${x}$ aqui é chamado de indeterminada, o que significa que não é uma variável que assume valores, seu único papel é codificar uma enumeração, neste papel ele contém duas informações: (1) as potências de ${x}$ representam as diferentes faces dos dados; (2) os coeficientes das potências de ${x}$ mostram o número de ocorrências de cada face.
Se o dado fosse defeituoso com faces 1,2,2,2,5,5 então o polinômio seria

$\displaystyle x^1 + 3x^2 + 2 x^5$

Se o segundo lançamento é codificado pelo mesmo polinômio, então o produto

$\displaystyle (x^1 + x^2 + x^3 + x^4 + x^5 + x^6)(x^1 + x^2 + x^3 + x^4 + x^5 + x^6) =$

$\displaystyle x^{12}+2x^{11}+3x^{10}+4x^9+5x^8+6x^7+5x^6+4x^5+3x^4+2x^3+x^2$

e nesse polinômio ${ax^k}$ significa que há ${a}$ maneiras de obtermos a soma ${k}$ (pela maneira que multiplicamos polinômio). Por exemplo, só há uma maneira de obtermos 12, é como ${6+6}$ , há 0 modos de obtermos soma ${0}$ ou soma maior que ${12}$ , há 3 maneiras de obter soma 4 (a saber ${1+3}$ , ${2+2}$ e ${3+1}$ ).

Para responder a pergunta inicial, precisamos conhecer o coeficiente de ${x^{14}}$ em

$\displaystyle ( x^1 + x^2 + x^3 + x^4 + x^5 + x^6)^4$

que expandido é o polinômio

$\displaystyle {{x}^{24}}+4 {{x}^{23}}+10 {{x}^{22}}+20 {{x}^{21}}+35 {{x}^{20}}+56 {{x}^{19}}+80 {{x}^{18}}+104 {{x}^{17}}+125 {{x}^{16}}+140 {{x}^{15}}+146 {{x}^{14}}+$

$\displaystyle 140 {{x}^{13}}+125 {{x}^{12}}+104 {{x}^{11}}+80 {{x}^{10}}+56 {{x}^{9}}+35 {{x}^{8}}+20 {{x}^{7}}+10 {{x}^{6}}+4 {{x}^{5}}+{{x}^{4}}$

portanto há 146 maneiras diferentes de obter a soma 14.

Exercício 53 Um pai generoso deseja dividir R$20,00 entre seus três filhos de modo que cada um receba pelo menos R$5,00 e ninguém receba mais que R$10,00 e a quantia do filho mais velho é par. Quantas maneiras existem de fazer isso?

Solução: Procuramos pelo coeficiente de ${x^{20}}$ no polinômio

$\displaystyle (x^6 + x^8 + x^{10})(x^5+x^6+x^7+x^8+x^9+x^{10})^2 =$

$\displaystyle {{x}^{30}}+2 {{x}^{29}}+4 {{x}^{28}}+6 {{x}^{27}}+9 {{x}^{26}}+12 {{x}^{25}}+13 {{x}^{24}}+14 {{x}^{23}}+13 {{x}^{22}}+12 {{x}^{21}}+$

$\displaystyle 9 {{x}^{20}}+6 {{x}^{19}}+4 {{x}^{18}}+2 {{x}^{17}}+{{x}^{16}}$

portanto são 9 maneiras. $\Box$

Exercício 54 Quantas soluções inteiras tem ${x_1+x_2+x_3=11}$ com ${x_1\in\{1,2,3\}}$ e ${x_2,x_3\in\{4,5\}}$ ?

Solução

Exercício 55 Imagine um país no qual há apenas três moedas: uma moeda de 1 centavo, uma moeda de 2 centavos e uma moeda de 4 centavos. De quantas maneiras podemos “trocar” 100 centavos?

Solução: Precisamos resolver a equação ${a + 2b + 4c = 100}$ para números inteiros não-negativos ${a,b,c}$ . Fazemos isso encontrando o coeficiente de ${x^{100}}$ no “polinômio”

$\displaystyle P (x) = (\underbrace{1 + x + x^2 + \cdots }_{\text{ quantas moedas de } 1}) \cdot (\underbrace{1 + x^2 + x^4 + \cdots }_{\text{ quantas moedas de } 2}) \cdot (\underbrace{1 + x^4 + x^8 + \cdots }_{\text{ quantas moedas de } 4})$

Podemos multiplicar os termos e com alguma perseverança eventualmente encontramos o coeficiente de ${x^{ 100}}$ . Mas agora precisamos buscar um modo mais inteligente para isso. $\Box$

Funções geradoras

Definição 32 Se ${a_0,a_1,a_2,\dots}$ é uma sequência de números a função geradora (ordinária) dessa sequência é a série de potências

$\displaystyle A(x) = \sum_{n\geq 0} a_nx^n \ \ \ \ \ (67)$

O coeficiente ${a_n}$ é denotado por

$\displaystyle [x^n]A(x)$

Por exemplo,

$\displaystyle (1+x)^n = \binom n0 + \binom n1 x + \cdots + \binom nn x^n \ \ \ \ \ (68)$

é função geradora da sequência ${\binom n0, \binom n1 , \dots , \binom nn, 0,0,\dots }$

$\displaystyle \frac{1-x^{n+1}}{1-x} = 1+x+x^2+\cdots+x^n \ \ \ \ \ (69)$

é função geradora da sequência ${1,1,\dots,1,0,0,0\dots}$ ( ${n+1}$ ocorrências de 1); se considerarmos ${|x|<1}$ e tomarmos o limite quando ${n\rightarrow\infty}$ em (69) obtemos

$\displaystyle \frac 1{1-x} = 1+x+x^2+x^3+\cdots \ \ \ \ \ (70)$

é função geradora da sequência constante ${1,1,1,\dots}$ . Também, sabemos que, por exemplo,

$\displaystyle \mathrm{e}^x= 1+ \frac x1 +\frac {x^2}{2!} + \frac {x^3}{3!}+\cdots \ \ \ \ \ (71)$

é função geradora da sequência ${( 1/n! : n\in{\mathbb N})}$ e

$\displaystyle \frac 1{\sqrt{1-4x}} = \sum_{n\geq 0}\binom{2n}n x^n \ \ \ \ \ (72)$

é função geradora da sequência ${\left(\binom{2n}n : n\in{\mathbb N} \right)}$ e

$\displaystyle \ln\left( \frac 1{1-x}\right) = \sum_{n\geq 1}\frac 1n x^n \ \ \ \ \ (73)$

é função geradora da sequência ${\left( \frac 1n : n\in{\mathbb N}^*\right)}$

$\displaystyle \mathrm{sen}(x) = \sum_{n\>0}(-1)^n \frac 1{2n+1\,!}{x^{2n+1}} \ \ \ \ \ (74)$

é função geradora da sequência ${1,\frac{-1}{3!},\frac 1{5!},\frac{-1}{7!},\dots}$ , e

$\displaystyle \cos (x) = \sum_{n\>0} (-1)^n \frac{1}{2n\, !}x^{2n} \ \ \ \ \ (75)$

é função geradora da sequência ${1,\frac{-1}{2!},\frac 1{4!},\frac{-1}{6!},\dots}$ .

Em nossas aplicações (contagem) os coeficientes da série (67) são inteiros, porém todas as propriedades discutidas são válidas para números complexos. Ademais, ${A(x)}$ em (67) só é uma função para os valores de ${x}$ em que a série converge.

10.2. Sobre convergência (opcional, clique aqui para ler)

Não nos preocuparemos com questões de convergência, embora seja relevante para aplicar ferramentas do cálculo, e podemos tratar a série simbolicamente, como uma série formal de potências, que nos permite ignorar problemas de convergência e manipular séries de potências formais do mesmo modo como fazemos com polinômios.

Notemos que se ${A(x)}$ é função geradora de ${a_0,a_1,\dots}$ então para qualquer número ${c}$ a função ${A(cx)}$ é função geradora de ${a_0,a_1c,a_2c^2,a_3c^3\dots}$ . Por exemplo

$\displaystyle \frac 1{1+x} = 1-x+x^2-x^3+\cdots \ \ \ \ \ (76)$

é função geradora da sequência ${1,-1,1,-1,1\dots}$ pois de (70)

$\displaystyle \frac 1{1+x} = \frac 1{1-(-x)} = 1+(-x)+(-x)^2+(-x)^3+\cdots= 1-x+x^2-x^3+\cdots$

${\frac 1{1-2x}}$ é função geradora da sequência ${1,2,4,8,16,\dots}$ pois de (70)

$\displaystyle \frac 1{1-(2x)} = 1+(2x)+(2x)^2+(2x)^3+\cdots$

Sejam ${A(x) = \sum_{n\geq 0} a_nx^n}$ e ${B(x) = \sum_{n\geq 0} b_nx^n}$ funções geradoras, definimos:

deslocamento a direita	$xA(x)=\sum_{n\ge1}a_{n-1}x^n$
deslocamento a esquerda	${A(x)-a_0\over x}=\sum_{n\ge0}a_{n+1}x^n$
diferenciação	$A' (x)=\sum_{n\ge0}(n+1)a_{n+1}x^n$
integração	$\int_0^xA(t)dt=\sum_{n\ge1}{a_{n-1}\over n}x^n$
adição	$A(x)+B(x)=\sum_{n\ge0}(a_n+b_n)x^n$
convolução (produto)	${A(x)B(x)}=\sum_{n\ge0}\Bigl(\,\sum_{0\le k\le n}a_kb_{n-k}\Bigr)x^n$
somas parciais	${A(x)\over1-x}=\sum_{n\ge0}\Bigl(\,\sum_{0\le k\le n}a_k\Bigr)x^n$

Por exemplo, se ${a_0,a_1,\dots}$ tem função geradora ${f(x)}$ então ${x^kf(x)}$ é função geradora de ${0,0,\dots,0,a_0,a_1,\dots}$ com ${k}$ ocorrências de 0 no início da sequência. Em particular, ${0,0,0,1,1,1,1,\dots}$ tem função geradora ${\frac {x^3}{1-x}}$ .

Usando adição e os exemplos dados acima

$\displaystyle \frac 1{1-x} + \frac 1{1+x} = \frac 2{1-x^2} \ \ \ \ \ (77)$

é função geradora da sequência ${2,0,2,0,2,\dots}$ .

Fibonacci: A sequência de Fibonacci ${F_0,F_1,F_2,\dots}$ dada por ${F_0=0,F_1=1}$ e ${F_{n}=F_{n-1}+F_{n-2}}$ para todo ${n\geq 2}$ , ou seja,

$\displaystyle 0,F_0+1,F_1+F_0,F_2+F_1,F_3+F_2$

é obtida da soma das três sequências

$\displaystyle \begin{array}{rcl} &0,1,0,0,0,0,\dots \\ &0,F_0,F_1,F_2,F_3,\dots\\ &0,0,F_0,F_1,F_2,F_3,\dots \end{array}$

cujas funções geradoras são, respectivamente, ${x}$ , ${x F(x)}$ e ${x^2 F(x)}$ , onde ${F(x)}$ é a função geradora da sequência de Fibonacci. Logo

$\displaystyle F(x) = \frac x{1-x-x^2}$

Teorema binomial estendido

Definição 33 Vamos definir ${(x)_k}$ para qualquer ${x\in {\mathbb R}}$ por

$\displaystyle (x)_k = x(x-1)(x-2)\cdots(x-k+1)$

de modo que o coeficiente binomial estendido fica definido por

$\displaystyle \binom xk = \begin{cases} \frac{(x)_k}{k!} & \text{ se }k>0\\ 1 & \text{ se }k=0 \end{cases} .$

Por exemplo, ${\binom {-2}3 = -4}$ e ${\binom {1/2}3=1/16}$ e para todo ${n\in {\mathbb N}}$ , ${\binom nk = 0}$ se ${n<k}$ .

Notemos que se ${x\in {\mathbb Z}^+}$ então

$\displaystyle \begin{array}{rcl} \binom {-x}k &=& \frac{-x(-x-1)(-x-2)\cdots(-x-k+1)}{k!} \\ &=&\frac{(-1)^k x(x+1)(x+2)\cdots(x+k-1)}{k!} \\ &=&\frac{(-1)^k (x+k-1)!}{(x-1)!\,k!} = (-1)^k \binom{n+k-1}k \end{array}$

Teorema 48 (Teorema binomial estendido) Para todo ${x\in(-1,1)}$ e todo real ${u}$

$\displaystyle (1+x)^u = \sum_{n\geq 0} \binom un x^n.$

Demonstração: Omitimos, decorre da série da Maclaurin para ${(1+x)^u }$ . $\Box$

Com a definição e teorema acima temos para ${k\in{\mathbb N}}$

$\displaystyle (1+x)^{-k} = \sum_{n\geq 0} \binom{-k}n x^n = \sum_{n\geq 0}(-1)^n \binom{k+n-1}{k-1}x^n$

$\displaystyle (1-x)^{-k} = \sum_{n\geq 0} \binom{-k}n (-x)^n = \sum_{n\geq 0}\binom{k+n-1}{k-1}x^n$

10.4. Expansão de funções de geradoras

Dada uma forma funcional para uma função geradora, gostaríamos de um mecanismo para encontrar a sequência associada. Esse processo é chamado de expandir a função geradora. Muitas funções são facilmente manipuladas a partir do teorema de Taylor

$\displaystyle f(x) = f(0) + \frac{f'(0)}{1!}x + \frac{f''(0)}{2!}x^2+ \frac{f'''(0)}{3!}x^3+ \cdots = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}x^n$

de modo que

$\displaystyle [x^n]f(x) = \frac 1{n!} f^{(n)}(0)$

sempre que diferenciação for possível.

Também, obtemos coeficientes por manipulações algébricas envolvendo as identidades básicas que já são conhecidas e transformações dadas nas tabelas acima. Por exemplo

$\displaystyle [x^n] \frac c{1-bx} = cb^n \ \ \ \ \ (78)$

para quaisquer constantes ${b}$ e ${c}$ , pois de (70) temos

$\displaystyle \frac c{1-bx} = c \sum_{n\geq 0} (bx)^n.$

Exemplo: Considere o problemas dos dados enunciado no início dessa seção: De quantas maneiras distintas podemos lançar uma dado quatro vezes de modo que os resultados somam 14? A função geradora é

$\displaystyle \begin{array}{rcl} D(x) &=& (x+x^2+x^3+x^4+x^5+x^6)^4 \\ &=& x^4(1+x^2+x^3+x^4+x^5)^4 \\ &=& x^4\left( \frac{1-x^6}{1-x}\right)^4 \\ &=& x^4 \left( 1-x^6 \right)^4 \left( 1-x \right)^{-4} \end{array}$

de modo que ${[x^{14}]D(x) = [x^{10}] \left( 1-x^6 \right)^4 \left( 1-x \right)^{-4} }$ . Ainda,

$\displaystyle \left( 1-x^6 \right)^4 = \sum_{j\geq 0}\binom 4j(-x^6)^j = 1 -4x^6 + 6x^{12} - 4x^{18} + x^{24}$

$\displaystyle \left( 1-x \right)^{-4} = \sum_{j\geq 0} \binom{4+j-1}{j}x^j = \sum_{j\geq 0} \binom{3+j}{j}x^j$

Agora, ${ [x^{10}] \left( 1-x^6 \right)^4 \left( 1-x \right)^{-4} }$ pode ser obtido de ${[x^0] \left( 1-x^6 \right)^4 = 1 }$ e ${[x^{10}] \left( 1-x \right)^{-4} = \binom {13}{10} = 286}$ e ser obtido de ${[x^6] \left( 1-x^6 \right)^4 = -4 }$ e ${[x^{4}] \left( 1-x \right)^{-4} = \binom {7}{4} = 35}$ , logo temos ${286-140=146}$ modos distintos.

Exemplo: Determine o coeficiente de ${[x^{15}](x^2+x^3+x^4+\cdots)^4}$ .

Notemos que

$\displaystyle [x^{15}](x^2+x^3+x^4+\cdots)^4 = [x^{15}]\big(x^2(1+x+x^3+\cdots)\big)^4$

$\displaystyle = [x^{15}]\left(\frac{x^2}{1-x} \right)^4= [x^{15}]\left(\frac{x^8}{(1-x)^4}\right)= [x^{7}]\left(\frac{1}{(1-x)^4}\right)$

$\displaystyle \frac{1}{(1-x)^4}= \sum_{r\geq 0}\binom{-4}r(-x)^r = \sum_{r\geq 0}\binom{4+r-1}rx^r$

portanto ${[x^{15}](x^2+x^3+x^4+\cdots)^4= \binom{4+7-1}7}$ .

Exemplo: Quantos subconjuntos de ${\{1,2,\dots,15\}}$ formado de 4 elementos não consecutivos existem? Se ${\{a,b,c,d\}}$ é um tal subconjunto de modo que

$\displaystyle 1\leq a < b< c < d \leq 15$

então

$\displaystyle \underbrace{(15-d)}_{x_1} + \underbrace{(d-c)}_{x_2} + \underbrace{(c-b)}_{x_3} + \underbrace{(b-a)}_{x_4} + \underbrace{(a-1)}_{x_5}=14$

portanto, queremos o número de soluções inteiras de

$\displaystyle x_1+x_2+x_3+x_4+x_5=15$

com ${x_1,x_5\geq 0}$ e ${x_2,x_3,x_4 \geq 2}$ , o qual é o coeficiente

$\displaystyle [x^{14}](1+x+x^2+\cdots)^2(x^2+x^3+x^4+\cdots)^3 = [x^{14}]x^6(1-x)^{-5} = [x^8](1-x)^{-5} = \binom{5+8-1}{8} = 495.$

Exercício 56 De quantos modos podemos comprar ${n}$ frutas de modo que ${(1)}$ o número de maçãs é par, ${(2)}$ o número de bananas é múltiplo de 5, ${(3)}$ no máximo 4 laranjas, e ${(4)}$ no máximo uma pêra.

Solução

No caso de funções racionais podemos usar a técnica da frações parciais, por exemplo

$\displaystyle \frac x{1-x-x^2} = \frac x {(1-\varphi x)(1 -\bar\varphi x)}$

onde ${\varphi = (1+\sqrt 5)/2}$ e onde ${\bar\varphi = (1-\sqrt 5)/2}$ são as raízes de ${1-x-x^2}$ . Fazendo

$\displaystyle \frac x {(1-\varphi x)(1 -\bar\varphi x)} = \frac A{1-\varphi x} + \frac B{1-\bar\varphi x}$

temos ${A=1/\sqrt 5}$ e ${B=11/\sqrt 5}$ de modo que

$\displaystyle \frac x{1-x-x^2} = \frac 1{\sqrt5} \frac 1{1-\varphi x} - \frac 1{\sqrt5} \frac 1{1-\bar\varphi x}$

Agora

$\displaystyle \frac 1{\sqrt5} \frac 1{1-\varphi x} = \frac 1{\sqrt5} \sum_{n\geq 0} (\varphi x)^n$

$\displaystyle \frac 1{\sqrt5} \frac 1{1-\bar\varphi x} = \frac 1{\sqrt5} \sum_{n\geq 0} (\bar\varphi x)^n$

portanto ${ \frac x{1-x-x^2} = \sum_{n\geq 0} \frac 1{\sqrt5} (\varphi^n - \bar\varphi^n) x^n}$ de modo que

$\displaystyle [x^n] \frac x{1-x-x^2} = \frac 1{\sqrt5} (\varphi^n - \bar\varphi^n) \ \ \ \ \ (79)$

Exemplo: Determina o coeficiente de ${x^n}$ na série de potências de

$\displaystyle \frac 1{x^3 - 7 x^2 + 16 x - 12}$

Primeiro, temos que

$\displaystyle x^3 - 7 x^2 + 16 x - 12 = (x-3)(x-2)^2$

portanto devemos determinar constantes ${A,B,C}$ tais que

$\displaystyle \frac 1{x^3 - 7 x^2 + 16 x - 12} = \frac A{x-3}+ \frac B{x-2} + \frac C{(x-2)^2}$

e temos que ${A=1}$ e ${B=C=-1}$ , logo

$\displaystyle \frac 1{x^3 - 7 x^2 + 16 x - 12} = \frac 1{x-3} -\frac 1{x-2} - \frac 1{(x-2)^2}$

Agora, reescrevemos cada fração para cairmos no caso ${\frac 1{1-ax}}$

$\displaystyle \frac 1{x-3} = \frac 1{-3(1-x/3)} = -\frac {1}3 \frac 1{1-x/3}$

$\displaystyle \frac 1{x-2} = \frac 1{-2(1-x/2)} = -\frac {1}2 \frac 1{1-x/2}$

e no caso ${\frac 1{(1-ax)^2}}$

$\displaystyle \frac 1{(x-2)^2} = \frac {-1}4 \frac 1{(1-x/2)^2}$

logo

$\displaystyle \frac 1{x^3 - 7 x^2 + 16 x - 12} = - \frac {1}3 \frac 1{(1- \frac x3)} + \frac {1}2 \frac 1{(1- \frac x2)} + \frac {1}4 \frac 1{(1-x/2)^2}$

$\displaystyle = -\frac 13 \sum_{n\geq 0} \left( \frac x3\right)^n + \frac 12 \sum_{n\geq 0} \left( \frac x2\right)^n + \frac 14 \sum_{n\geq 0} \binom{-2}n \left(\frac{-x}2\right)^n$

$\displaystyle =\sum_{n\geq 0} \left( \left(\frac 12 \right)^{n+1} - \left(\frac 13 \right)^{n+1} + \frac 14 (-1)^n\binom {-2}n \right)x^n$

$\displaystyle =\sum_{n\geq 0} \left( \left(\frac 12 \right)^{n+1} - \left(\frac 13 \right)^{n+1} + \frac 14 (-1)^n\binom {n+3}n \right)x^n$

portanto

$\displaystyle [x^n] \frac 1{x^3 - 7 x^2 + 16 x - 12} = \frac 1{2^{n+1}} - \frac 1{3^{n+1}} + \frac{(n+3)(n+2)(n+1)}{24}.$

Notas de aula

Jair Donadelli

[MCTB019-17] §10 — Funções geradoras

Deixe um comentário Cancelar resposta

Compartilhe isso:

Relacionado

Deixe um comentário Cancelar resposta