\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{22 de outubro de 2007}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{epsfig,graphicx,color,latexsym,alltt,calc,ifthen,slides,hyperref} 
 
\newcounter{conta}
\begin{document}

\setbackgroundcolor{white}
\settextcolor{blue}
\setslidetitlecolor{red}
\setbordercolor{darkblue}


\setedition{slides.sty}
\newincluder{fulledition}
\setincluder{fulledition}{true}

\sffamily 
\bfseries 
\mathversion{bold}
\Hugesize 
%\Hugefont

\hypertarget{inicio}{}
\title{Fun\c{c}\~oes Geradoras \\ Baseado em Townsend (1987), Cap. 3}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 3}
\lfoot{UFMG}
%\rfoot{rsb}
\organization{UFMG}
\cfoot{\hyperlink{inicio}{\threebigotimes}~~~\hyperlink{sumario}{\threebigoplus}}
\date{\ultimamodificacao}
\titlepage


\newslide{SUMÁRIO}
\hypertarget{sumario}{}
%\begin{twoblocks}
\begin{itemize}
\item \hyperlink{funcoes-geradoras-1}{Funções Geradoras}
\item \hyperlink{modelagem-1}{Modelagem de Problemas com Funções Geradoras}
\item \hyperlink{coeficientes-1}{Extração de Coeficientes de Funções Geradoras Ordinárias Simples}
\item \hyperlink{exemplos-1}{Exemplos de Uso de Funções Geradoras Ordinárias}
\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

%--------------------------------------------------------------------------------------------

\section{FUNÇÕES GERADORAS}
\hypertarget{funcoes-geradoras-1}{}
\setskiplink{capitulo3}

\newslide{Um exemplo}

\noindent Duas maneiras de determinar o n\'{u}mero de solu\c{c}\~{o}es inteiras para
\[ x_1+x_2=r, \mbox{ com } 0\leq x_1\leq 1 \mbox{ e } 1\leq x_2\leq 2\mbox{:} \]

\vspace*{3mm}
\begin{enumerate}
 \item Enumera\c{c}\~{a}o expl\'{\i}cita:

       \begin{tabular}{cccc}
        & \ $x_1$ \ & \ $x_2$ \ & \ $r$ \ \\ \cline{2-4}
        & 0 & 1 & 1 \\
        $x_1\in \{0,1\}, x_2\in\{1,2\}$\ \ \  & 0 & 2 & 2 \\
        & 1 & 1 & 2 \\
        & 1 & 2 & 3 
       \end{tabular} 
\end{enumerate}
%--------------------------------------------------------------------------------------------

\newslide{Um exemplo}

\noindent Duas maneiras de determinar o n\'{u}mero de solu\c{c}\~{o}es inteiras para
\[ x_1+x_2=r, \mbox{ com } 0\leq x_1\leq 1 \mbox{ e } 1\leq x_2\leq 2\mbox{:} \]

\vspace*{3mm}
\begin{enumerate}
\item[2.] Multiplica\c{c}\~{a}o de \textcolor{black}{polin\^{o}mios}:

\vspace*{3mm}
      $\begin{array}{ll}
       (x^0+x^1)(x^1+x^2) & = x^0x^1+x^0x^2+x^1x^1+x^1x^2 \\
                          & = x^1+x^2+x^2+x^3 \\
                          & = 1x^1+2x^2+1x^3
      \end{array}$
      
\vspace*{3mm}
      $\Longrightarrow$ coeficiente de $x^i$: n\'{u}mero de solu\c{c}\~{o}es para $r=i$.
\end{enumerate}

%--------------------------------------------------------------------------------------------

\newslide{Outro exemplo}

\noindent Determinar o n\'{u}mero de solu\c{c}\~{o}es inteiras para
\[ x_1+x_2=r, \mbox{ com } x_1\geq 0 \mbox{ e } x_2\geq 0\mbox{:} \]

\vspace*{3mm}
\begin{itemize}
 \item Enumera\c{c}\~{a}o expl\'{\i}cita:

\vspace*{3mm}
       \begin{tabular}{cccc}
        & \ $x_1$ \ & \ $x_2$ \ & \ $r$ \ \\ \cline{2-4}
        & $0$ & $r$ & $r$ \\
        $x_1\geq 0, x_2\geq 0$\ \ \  & $1$ & $r-1$ & $r$ \\
        &  & $\vdots$ &  \\
        & $r$ & $0$ & $r$ 
       \end{tabular} 

\vspace*{3mm}
       $\Longrightarrow$ N\'{u}mero de solu\c{c}\~{o}es: $r+1$.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\item Racioc\'{\i}nio polinomial:

      \[(x^0+x^1+\cdots)(x^0+x^1+\cdots) = x^0x^0+x^0x^1+\cdots+x^1x^0+x^1x^1+
       \cdots\]
               
\vspace*{3mm}
      $\Longrightarrow$ N\'{u}mero de solu\c{c}\~{o}es: coeficiente de $x^r$.
      
\vspace*{3mm}
\item Determinando o coeficiente de $x^r$:
       
\vspace*{3mm}
             \[x^0x^r+x^1x^{r-1}+\cdots +x^rx^0=(r+1)x^r\]
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{S\'erie de pot\^encias}

\begin{itemize}
 \item Uma \textcolor{black}{s\'{e}rie de pot\^{e}ncias} \'{e} uma s\'{e}rie infinita da forma
         \[a_0x^0+a_1x^1+a_2x^2+\cdots\]
       sendo cada $a_i$ um n\'{u}mero real e $x$ uma vari\'{a}vel.

\vspace*{3mm}
 \item \textcolor{black}{Multiplica\c{c}\~{a}o}: o coeficiente de $x^r$ em
         \[(a_0x^0+a_1x^1+a_2x^2+\cdots)(b_0x^0+b_1x^1+b_2x^2+\cdots)\]
       \'{e} $a_0b_r+a_1b_{r-1}+\cdots +a_rb_0$

\vspace*{3mm}
 \item \textcolor{black}{Adi\c{c}\~{a}o}: o coeficiente de $x^r$ em
         \[(a_0x^0+a_1x^1+a_2x^2+\cdots)+(b_0x^0+b_1x^1+b_2x^2+\cdots)\]
       \'{e} $a_r+b_r$.
\end{itemize}


%--------------------------------------------------------------------------------------------

\newslide{Um exemplo}

\begin{itemize}
 \item $(x^0+x^1)(x^0+x^1+x^2+\cdots) = x^0+2x^1+2x^2+2x^3+\cdots$
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Defini\c{c}\~ao}

\begin{itemize}
 \item A \textcolor{black}{fun\c{c}\~{a}o geradora ordin\'{a}ria} para um problema combinat\'{o}rio de
       solu\c{c}\~{a}o $a_r$ \'{e}

\vspace*{3mm}
         \[g(x)=a_0x^0+a_1x^1+a_2x^2+\cdots\]
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item N\'{u}mero de solu\c{c}\~{o}es inteiras para
 
      \[ x_1+x_2=r, \mbox{ com } 0\leq x_1\leq 1 \mbox{ e }
         1\leq x_2\leq 2\mbox{:} \]

\vspace*{3mm}
       \begin{itemize}
        \item $a_0=0, a_1=1, a_2=2, a_3=1$, e para $r>3$ $a_r=0$.
\vspace*{3mm}
        \item Portanto, a fun\c{c}\~{a}o geradora \'{e}

\vspace*{3mm}
             $0x^0+1x^1+2x^2+1x^3+0x^4+\cdots+0x^r+\cdots$
             
             \hspace*{30mm} $=x+2x^2+x^3$.
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\item Fun\c{c}\~{a}o geradora para o n\'{u}mero de subconjuntos de tamanho $r$, tomados de
       um conjunto de tamanho $n$:
       
             \[C(n,0)x^0+C(n,1)x^1+C(n,2)x^2+\cdots+C(n,n)x^n\]
             
       que \'{e} $(1+x)^n$, pelo Teorema Binomial.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Estrat\'egia}

\noindent \textcolor{black}{Estrat\'{e}gia para resolver problemas usando fun\c{c}\~{a}o geradora:}

\vspace*{5mm}
\begin{enumerate}
 \item Encontrar uma fun\c{c}\~{a}o geradora para o problema geral.
 \item Extrair o coeficiente apropriado.
\end{enumerate}

%--------------------------------------------------------------------------------------------

\section{MODELAGEM DE PROBLEMAS COM FUNÇÕES GERADORAS}
\hypertarget{modelagem-1}{}

\newslide{Abordagem}

\begin{enumerate}
 \item Reformular o problema como um problema de encontrar o n\'{u}\-me\-ro de solu\c{c}\~{o}es
       inteiras para:
       \[ x_1+x_2+\cdots +x_n=r, \mbox{ com } x_i\in \{v_{i,1}, v_{i,2},
         \ldots\}\mbox{.} \]
 \item O n\'{u}mero de solu\c{c}\~{o}es \'{e} o coeficiente de $x^r$ em:
       \[ (x^{v_{1,1}}+x^{v_{1,2}}+\cdots)(x^{v_{2,1}}+x^{v_{2,2}}+\cdots)\cdots
          (x^{v_{n,1}}+x^{v_{n,2}}+\cdots)\mbox{.} \]
\end{enumerate}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item Fun\c{c}\~{a}o geradora para o problema de encontrar o n\'{u}mero de solu\c{c}\~{o}es
       inteiras de: 
       \[ x_1+2x_2+3x_3+4x_4=r, \mbox{ com } x_i\geq 0\mbox{:} \]
       \begin{enumerate}
        \item Reformula\c{c}\~{a}o do problema: encontrar o n\'{u}mero de solu\c{c}\~{o}es inteiras
              para:
              \[ y_1+y_2+y_3+y_4=r, \mbox{ com } y_i\in \{0, i, 2i, 3i,
              \ldots\}\mbox{.} \]
        \item A fun\c{c}\~{a}o geradora \'{e}, portanto:
        
              $(x^0+x^1+x^2+\cdots)(x^0+x^2+x^4+\cdots)(x^0+x^3+x^6+\cdots)$
              \newline
              $(x^0+x^4+x^8+\cdots)$.
        \item Solu\c{c}\~{a}o: coeficiente de $x^r$.
       \end{enumerate}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Fun\c{c}\~{a}o geradora para o problema de encontrar o n\'{u}mero de distribui\c{c}\~{o}es
       de 10 bolas id\^{e}nticas em 3 caixas distintas, com um n\'{u}mero par de bolas
       em cada caixa:
       \begin{enumerate}
        \item Reformula\c{c}\~{a}o do problema: encontrar o n\'{u}mero de solu\c{c}\~{o}es inteiras
              para:
              \[ x_1+x_2+x_3=r, \mbox{ com } x_i\in \{0, 2, 4,
                 \ldots\}\mbox{.} \]
        \item A fun\c{c}\~{a}o geradora \'{e}, portanto:
              \[ (x^0+x^2+x^4+\cdots)^3\mbox{.} \]
        \item Solu\c{c}\~{a}o: coeficiente de $x^{10}$.
       \end{enumerate}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Fun\c{c}\~{a}o geradora para o problema dos dados de Galileu:
       \begin{enumerate}
        \item Reformula\c{c}\~{a}o do problema: encontrar o n\'{u}mero de solu\c{c}\~{o}es inteiras
              para:
              \[ x_1+x_2+x_3=r, \mbox{ com } 1\leq x_i\leq 6\mbox{.} \]
        \item A fun\c{c}\~{a}o geradora \'{e}, portanto:
              \[ (x^1+x^2+x^3+x^4+x^5+x^6)^3\mbox{.} \]
        \item Solu\c{c}\~{a}o: coeficiente de $x^{10}$.
       \end{enumerate}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Fun\c{c}\~{a}o geradora para o problema de encontrar o n\'{u}mero de solu\c{c}\~{o}es
       inteiras de: 
       \[ x_1+x_2+\cdots+x_n\leq r, \mbox{ com } 1\leq x_i\leq 3\mbox{:} \]
       \begin{enumerate}
        \item Reformula\c{c}\~{a}o do problema: encontrar o n\'{u}mero de solu\c{c}\~{o}es inteiras
              para:
              
              $x_1+x_2+\cdots+x_n+x_{n+1}=r$,
              \newline
              com $1\leq x_i\leq 3, \mbox{ para } 1\leq i\leq n, \mbox{ e }
              x_{n+1} \geq 0$.
        \item A fun\c{c}\~{a}o geradora \'{e}, portanto:
        
              \[ (x^1+x^2+x^3)^n(x^0+x^1+x^2+x^3+\cdots)\mbox{.} \]
        \item Solu\c{c}\~{a}o: coeficiente de $x^r$.
       \end{enumerate}

%--------------------------------------------------------------------------------------------

%\newslide{Exemplo}

% \item Fun\c{c}\~{a}o geradora para o n\'{u}mero de maneiras de
%       escolher 5 n\'{u}meros distintos de $\{1,2,\ldots,n\}$, sem n\'{u}meros
%       consecutivos:
%       \begin{enumerate}
%        \item Reformula\c{c}\~{a}o do problema:
        
%              Sejam
%              \begin{itemize}
%               \item $1\leq n_1<n_2<n_3<n_4<n_5\leq n$ os n\'{u}meros a serem
%               escolhidos;
%               \item $x_1=n_1$, $x_2=n_2-n_1$, $x_3=n_3-n_2$, $x_4=n_4-n_3$,
%                     $x_5=n_5-n_4$, $x_6=n-n_5$.
%              \end{itemize} 
              
%              O problema se reduz, ent\~{a}o, a encontrar o n\'{u}mero de so\-lu\-\c{c}\~{o}es
%              inteiras para:
              
%              $x_1+x_2+x_3+x_4+x_5+x_6=n$,
%              \newline
%              com $x_1\geq 1$, $x_i\geq 2 \mbox{ para } 2\leq i\leq 5 \mbox{ e }
%              x_6 \geq 0$.

%\newslide{Exemplo (continua\c{c}\~ao)}

%              O problema foi reduzido a encontrar o n\'{u}mero de so\-lu\-\c{c}\~{o}es
%              inteiras para:
              
%              $x_1+x_2+x_3+x_4+x_5+x_6=n$,
%              \newline
%              com $x_1\geq 1$, $x_i\geq 2 \mbox{ para } 2\leq i\leq 5 \mbox{ e }
%              x_6 \geq 0$.

%        \item A fun\c{c}\~{a}o geradora \'{e}, portanto:
%              \[ (x^1+x^2+x^3+\cdots)(x^2+x^3+x^4+\cdots)^4
%                 (x^0+x^1+x^2+\cdots)\mbox{.} \]
%        \item Solu\c{c}\~{a}o: coeficiente de $x^n$.
%       \end{enumerate}

%--------------------------------------------------------------------------------------------

%\newslide{MODELAGEM DE PROBLEMAS COM FUNÇÕES GERADORAS (8)}
%\hypertarget{modelagem-8}{}

% \item Fun\c{c}\~{a}o geradora de 2 vari\'{a}veis, $x$ e $y$, tal que o coeficiente de
%       $x^ry^s$ \'{e} o n\'{u}mero de maneiras de distribuir $r$ bolas vermelhas
%       id\^{e}nticas e $s$ bolas azuis id\^{e}nticas em $n$ caixas distintas, com,
%       no m\'{a}ximo, 3 bolas azuis em cada caixa:
%       \begin{enumerate}
%        \item Reformula\c{c}\~{a}o do problema: encontrar o n\'{u}mero de solu\c{c}\~{o}es inteiras
%              para:
%              
%              \begin{itemize}
%               \item $x_1+x_2+\cdots+x_n=r$, com $x_i\geq 0$,
%              \end{itemize}
%              e para
%              \begin{itemize}
%               \item $y_1+y_2+\cdots+y_n=s$, com $0\leq y_i\leq 3$
%              \end{itemize}
%              e multiplicar os dois resultados.
              
%--------------------------------------------------------------------------------------------

%\newslide{MODELAGEM DE PROBLEMAS COM FUNÇÕES GERADORAS (9)}
%\hypertarget{modelagem-9}{}              
              
%        \item A fun\c{c}\~{a}o geradora \'{e}, portanto:
%              \[ (x^0+x^1+x^2+\cdots)^n(y^0+y^1+y^2+y^3)^n\]

%        \item Solu\c{c}\~{a}o: coeficiente de $x^ry^s$.
%       \end{enumerate}
       
\end{itemize} 

%--------------------------------------------------------------------------------------------

\section{EXTRAÇÃO DE COEFICIENTES DE FUNÇÕES GERADORAS ORDINÁRIAS SIMPLES}
\hypertarget{coeficientes-1}{}

%\noindent \underline{Exemplo de extra\c{c}\~{a}o por racioc\'{\i}nio combinat\'{o}rio}:

%\vspace*{5mm}
%\begin{itemize}
% \item Extra\c{c}\~{a}o do coeficiente de $x^r$ em $(1+x)^n$:
 
%       \vspace*{3mm}
%       Dado que \[ (1+x)^n=\underbrace{(1+x)(1+x)\cdots(1+x)}_{n}\]
%       o coeficiente de $x^r$ \'{e} o n\'{u}mero de maneiras de selecionar
%       $r$ $x$'s (e $n-r$ 1's), ou seja $C(n,r)$.
%\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Identidades \'{u}teis para a extra\c{c}\~{a}o de coeficientes}

\begin{list}{\textcolor{black}{(\alph{conta})}}{\usecounter{conta}}
 \item $(1+x+x^2+\cdots)^n$

       \hspace*{5mm}$=C(n-1+0,0)+C(n-1+1,1)x+\cdots+C(n-1+r,r)x^r+\cdots$
 
       \vspace*{3mm}
       \textcolor{black}{Prova:} $(1+x+x^2+\cdots)^n$ \'{e} a fun\c{c}\~{a}o geradora para o n\'{u}mero de
       solu\c{c}\~{o}es inteiras de
       
        \[ x_1+x_2+\cdots+x_n=r, \mbox{ com } x_i\geq 0\mbox{.} \]

%--------------------------------------------------------------------------------------------

\newslide{Identidades \'{u}teis para a extra\c{c}\~{a}o de coeficientes}

 \item $(1+x+x^2+\cdots+x^{m-1})^n=(1-x^m)^n(1+x+x^2+\cdots)^n$
 
       \vspace*{3mm}
       \textcolor{black}{Prova:} $1+x+\cdots+x^{m-1}= (1-x^m)(1+x+x^2+\cdots)$

%--------------------------------------------------------------------------------------------

\newslide{Identidades \'{u}teis para a extra\c{c}\~{a}o de coeficientes}

 \item $(1-x^m)^n$
       \hspace*{5mm}$=C(n,0)-C(n,1)x^m+C(n,2)x^{2m}+\cdots+(-1)^nC(n,n)x^{nm}$
 
       \vspace*{3mm}
       \textcolor{black}{Prova:} No Teorema Binomial, substitua $x$ por $-x^m$.

       \vspace*{3mm}

%--------------------------------------------------------------------------------------------

\newslide{Identidades \'{u}teis para a extra\c{c}\~{a}o de coeficientes}

 \item $1/(1-x)=1+x+x^2+x^3+\cdots$
 
       \vspace*{3mm}
       \textcolor{black}{Prova:} $(1-x)(1+x+x^2+x^3+\cdots)=1$.
\end{list}

%--------------------------------------------------------------------------------------------

\newslide{Defini\c{c}\~{o}es e identidades importantes}

\begin{list}{\textcolor{black}{(\arabic{conta})}}{\usecounter{conta}}
\MYlayout
 \item O coeficiente de $x^r$ em
      \[(a_0+a_1x+a_2x^2+\cdots)(b_0+b_1x+b_2x^2+\cdots)\]
       \'{e} $a_0b_r+a_1b_{r-1}+\cdots +a_rb_0$
 \item (Teorema Binomial) \[(1+x)^n=C(n,0)+C(n,1)x+C(n,2)x^2+\cdots
       +C(n,n)x^n\]
 \item $(1+x+x^2+\cdots)^n=$
       \newline
       $C(n-1+0,0)+C(n-1+1,1)x+\cdots+C(n-1+r,r)x^r+\cdots$

%--------------------------------------------------------------------------------------------

\newslide{Defini\c{c}\~{o}es e identidades importantes}   

 \item $(1+x+x^2+\cdots+x^{m-1})^n=(1-x^m)^n(1+x+x^2+\cdots)^n$
 \item $(1-x^m)^n=$
       \newline
       $C(n,0)-C(n,1)x^m+C(n,2)x^{2m}+\cdots+(-1)^nC(n,n)x^{nm}$
 \item $1/(1-x)=1+x+x^2+x^3+\cdots$
\end{list}

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES: Exemplo}

\begin{itemize}
 \item Coeficiente de $x^{20}$ na fun\c{c}\~{a}o geradora $(x^3+x^4+\cdots)^3$:
 
        \vspace*{3mm}
        $(x^3+x^4+\cdots)^3$
        
        \hspace*{10mm} $= [x^3(1+x+x^2+\cdots)]^3$
        
        \hspace*{10mm} $= x^9(1+x+x^2+\cdots)^3$
        
        \hspace*{10mm} $= x^9[C(3-1+0,0)+C(3-1+1,1)x+\cdots]$, por \textcolor{black}{(3)}
        
        \vspace*{3mm}
       Logo, o coeficiente de $x^{20}$ \'{e} $C(3-1+11,11)$.

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES: Exemplo}

 \item Coeficiente de $x^9$ em $(1+x+x^2+x^3+x^4+x^5)^4$:
 
        \vspace*{3mm}
        $(1+x+\cdots+x^5)^4$
        
        \hspace*{10mm} $= (1-x^6)^4(1+x+x^2+\cdots)^4$, por \textcolor{black}{(4)}
        
        \hspace*{10mm} $= (C(4,0)-C(4,1)x^6+\cdots+C(4,4)x^{24})$
        \newline
        \hspace*{12mm} \ \ \ $(C(4-1+0,0)+C(4-1+1,1)x+\cdots)$, por \textcolor{black}{(5)} e \textcolor{black}{(3)}
       
       \vspace*{3mm}
       Logo, o coeficiente de $x^9$ \'{e}
        \[C(4,0)C(4-1+9,9)-C(4,1)C(4-1+3,3)\mbox{.}\]
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES}

\noindent Os resultados a seguir s\~{a}o \'{u}teis para:

\vspace*{5mm}
\begin{itemize}
 \item Construir uma fun\c{c}\~{a}o geradora para um $a_n$ espec\'{\i}fico.
 \item Utilizar fun\c{c}\~{a}o geradora para resolver somat\'{o}rias.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES}

\noindent Sejam $g(x)$ a fun\c{c}\~{a}o geradora para $a_n$, e $h(x)$ a fun\c{c}\~{a}o geradora
para $b_n$. Ent\~{a}o:

\begin{list}{\textcolor{black}{(\alph{conta})}}{\usecounter{conta}}
 \item $g(x)/(1-x)$ \'{e} a fun\c{c}\~{a}o geradora para $a_0+a_1+\cdots+a_n$.
 
       \vspace*{3mm}
       \textcolor{black}{Prova:}
       
       $g(x)/(1-x)$
        
       \hspace*{10mm} $= (a_0+a_1x+a_2x^2+\cdots)/(1-x)$

       \hspace*{10mm} $= (a_0+a_1x+a_2x^2+\cdots)(1+x+x^2+\cdots)$, por \textcolor{black}{(6)}

       \hspace*{10mm} $= a_0+(a_0+a_1)x+\cdots+(a_0+a_1+\cdots+a_n)x^n+\cdots$

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICICIENTES}

 \item $C_1g(x)+C_2h(x)$ \'{e} a fun\c{c}\~{a}o geradora para $C_1a_n+C_2b_n$, onde $C_1$ e
       $C_2$ s\~{a}o constantes.
 
       \vspace*{3mm}
       \textcolor{black}{Prova:}
       
       $C_1g(x)+C_2h(x)$
 
       \hspace*{5mm} $= C_1(a_0+a_1x+a_2x^2+\cdots)+C_2(b_0+b_1x+b_2x^2+\cdots)$

       \hspace*{5mm} $= (C_1a_0+C_2b_0)+(C_1a_1+C_2b_1)x+\cdots+
                         (C_1a_n+C_2b_n)x^n+\cdots$

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES}

 \item $(1-x)g(x)$ \'{e} a fun\c{c}\~{a}o geradora para $a_n-a_{n-1}$.
 
       \vspace*{3mm}
       \textcolor{black}{Prova:}
       
       $(1-x)g(x)$
        
       \hspace*{10mm} $= (1-x)(a_0+a_1x+a_2x^2+\cdots)$

       \hspace*{10mm} $= (a_0+a_1x+a_2x^2+\cdots)-(a_0x+a_1x^2+a_2x^3+\cdots)$

       \hspace*{10mm} $= a_0+(a_1-a_0)x+(a_2-a_1)x^2+\cdots+(a_n-a_{n-1})x^n+
                         \cdots$

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES}

 \item $xg'(x)$ \'{e} a fun\c{c}\~{a}o geradora para $na_n$.
 
       \vspace*{3mm}
       \textcolor{black}{Prova:}
       
       $xg'(x)$
        
       \hspace*{10mm} $= x(a_1+2a_2x+3a_3x^2+\cdots)$

       \hspace*{10mm} $= a_1x+2a_2x^2+3a_3x^3+\cdots+na_nx^n+\cdots$

%--------------------------------------------------------------------------------------------

\newslide{EXTRAÇÃO DE COEFICIENTES}

 \item $h(x)g(x)$ \'{e} a fun\c{c}\~{a}o geradora para $a_0b_n+a_1b_{n-1}+\cdots+a_nb_0$.
 
       \vspace*{3mm}
       \textcolor{black}{Prova:} segue de \textcolor{black}{(1)}.
\end{list}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item Fun\c{c}\~{a}o geradora para $a_n=2n+3$:
 
       \vspace*{3mm}
       Fun\c{c}\~{a}o geradora para $1$: $1/(1-x)$, por \textcolor{black}{(6)}.
       
       Logo, a fun\c{c}\~{a}o geradora para $n$ \'{e}: $x[1/(1-x)]'=x/(1-x)^2$, por \textcolor{black}{(d)}.
       
       Assim, a fun\c{c}\~{a}o geradora para $2n+3$ \'{e}: $2x/(1-x)^2+3/(1-x)$.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Fun\c{c}\~{a}o geradora para $a_n=n^2$:
 
       \vspace*{3mm}
       Fun\c{c}\~{a}o geradora para $n$: $x/(1-x)^2$, pelo exemplo acima.
       
       Fun\c{c}\~{a}o geradora para $n^2$: $x[x/(1-x)^2]'=(x+x^2)/(1-x)^3$, por \textcolor{black}{(d)}.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Avalia\c{c}\~{a}o de $1^2+2^2+\cdots+n^2$:
 
       \vspace*{3mm}
       Fun\c{c}\~{a}o geradora para $n^2$: $(x+x^2)/(1-x)^3$, pelo exemplo acima.
       
       Fun\c{c}\~{a}o geradora para $\sum_{k=1}^{n}k^2$: $(x+x^2)/(1-x)^4$, por \textcolor{black}{(a)}.
       
       $(x+x^2)/(1-x)^4$
       
       \hspace*{10mm} $= (x+x^2)(1+x+x^2+\cdots)^4$, por \textcolor{black}{(6)}
       
       \hspace*{10mm} $= (x+x^2)(1+C(4-1+1,1)x+C(4-1+2,2)x^2+\cdots)$,
       \newline
       \hspace*{20mm} por \textcolor{black}{(3)}
       
%--------------------------------------------------------------------------------------------

%\newslide{EXTRAÇÃO DE COEFICIENTES DE FUNÇÕES GERADORAS ORDINÁRIAS SIMPLES (19)}
%\hypertarget{coeficientes-19}{}         
       
       Coeficiente de $x^n$: \[C(4-1+(n-1),(n-1))+C(4-1+(n-2),(n-2))\mbox{.}\]
       
       Portanto,
       
       \vspace*{3mm}
         \[\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}\mbox{.}\]

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Avalia\c{c}\~{a}o de $\sum_{k=0}^{n}k2^k$:\\
 \\
       Fun\c{c}\~{a}o geradora para $2^n$: $1/(1-2x)$, por \textcolor{black}{(6)}, $x/2x$.
       
       Fun\c{c}\~{a}o geradora para $n2^n$: $x[1/(1-2x)]'=2x/(1-2x)^2$, por \textcolor{black}{(d)}.
       
       Fun\c{c}\~{a}o geradora para $\sum_{k=0}^nk2^k$: $2x/(1-2x)^2(1-x)$, por \textcolor{black}{(a)}.
       
       $2x/(1-2x)^2(1-x)$
       
       \hspace*{10mm} $= 2/(1-x)-4/(1-2x)+2/(1-2x)^2$, pelo m\'{e}todo das
       \newline
       \hspace*{20mm} fra\c{c}\~{o}es parciais
       
%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item Avalia\c{c}\~{a}o de $\sum_{k=0}^{n}k2^k$: \\
 \\
       Como
       \hspace*{10mm} \begin{itemize}
                       \item $2/(1-x)=2(1+x+x^2+\cdots)$, por \textcolor{black}{(6)}
                       \item $4/(1-2x)=4(1+2x+4x^2+\cdots+(2x)^n+\cdots)$,
                              por \textcolor{black}{(6)}
                       \item $2/(1-2x)^2=2(1+C(2-1+1,1)2x+\cdots
                              +C(2-1+n,n)(2x)^n+\cdots)$, por \textcolor{black}{(6)} e \textcolor{black}{(3)}
                      \end{itemize}
       o coeficiente de $x^n$ \'{e}:
        \[2-4\times 2^n+2C(2-1+n,n)\times 2^n\mbox{.}\]
       
       Portanto,
       
       \vspace*{3mm}
         \[\sum_{k=0}^{n}k2^k=2+(2n-2)2^n\mbox{.}\]
\end{itemize}

%--------------------------------------------------------------------------------------------

\section{EXEMPLOS DE USO DE FUNÇÕES GERADORAS}
\hypertarget{exemplos-1}{}

\newslide{Exemplo de uso de Fun\c{c}\~{o}es Geradoras Ordin\'{a}rias}

\begin{itemize}
 \item O problema dos dados de Galileu:
 
       \vspace*{3mm}
       Soma 10: coeficiente de $x^{10}$ na fun\c{c}\~{a}o geradora
        \[ (x^1+x^2+x^3+x^4+x^5+x^6)^3\mbox{.} \]   
        
        $(x^1+x^2+x^3+x^4+x^5+x^6)^3$
        
        \hspace*{10mm} $= x^3(1+x+x^2+x^3+x^4+x^5)^3$
        
        \hspace*{10mm} $= x^3(1-x^6)^3(1+x+x^2+\cdots)^3$, por \textcolor{black}{(4)}
        
        \hspace*{10mm} $= x^3(C(3,0)-C(3,1)x^6+C(3,2)x^{12}-C(3,3)x^{18})$
        \newline
        \hspace*{10mm} \ \ \ \ $(C(3-1+0,0)+C(3-1+1,1)x+\cdots)$, por \textcolor{black}{(5)} e \textcolor{black}{(3)}

        \vspace*{3mm}
        O coeficiente de $x^{10}$ \'{e}, portanto,
        \[C(3,0)C(3-1+7,7)-C(3,1)C(3-1+1,1)=36-9=27\mbox{.}\]

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item N\'{u}mero de maneiras de distribuir $r$ bolas id\^{e}nticas em $n$ caixas
       distintas com, no m\'{a}ximo, 3 bolas em cada caixa:
 
       \vspace*{3mm}
       Reformula\c{c}\~{a}o: n\'{u}mero de solu\c{c}\~{o}es inteiras para
       \[ x_1+x_2+\cdots+x_n=r, \mbox{ com } 0\leq x_i\leq 3 \]
               
       Fun\c{c}\~{a}o geradora: \[(1+x+x^2+x^3)^n\]
        
       $(1+x+x^2+x^3)^n$
        
        \hspace*{10mm} $= (1-x^4)^n(1+x+x^2+\cdots)^n$, por (4)
        
        \hspace*{10mm} $= (C(n,0)-C(n,1)x^4+\cdots+(-1)^nC(n,n)x^{4n})$
        \newline
        \hspace*{10mm} \ \ \ \ $(C(n-1+0,0)+C(n-1+1,1)x+\cdots)$, por (5) e (3)

        \vspace*{3mm}
        O coeficiente de $x^{r}$ \'{e}, portanto,
        \[C(n,0)C(n-1+r,r)-C(n,1)C(n-1+r-4,r-4)+\cdots\mbox{.}\]

\end{itemize}
%--------------------------------------------------------------------------------------------

%\newslide{Exemplo}

% \item Fun\c{c}\~{a}o geradora para o n\'{u}mero de solu\c{c}\~{o}es inteiras de
%       \[ x_1+x_2+x_3+x_4=r,
%          \mbox{ com } 1\leq x_1\leq x_2\leq x_3\leq x_4\mbox{:} \]
          
%       \vspace*{3mm}
%       Sejam $y_1=x_1$, $y_2=x_2-x_1$, $y_3=x_3-x_2$, e $y_4=x_4-x_3$.
  
%       O n\'{u}mero de solu\c{c}\~{o}es da equa\c{c}\~{a}o \'{e} o mesmo que o n\'{u}mero de
%       solu\c{c}\~{o}es de   
%       \[ 4y_1+3y_2+2y_3+y_4=r,
%          \mbox{ com } y_1\geq 1 \mbox{ e } y_2,y_3,y_4\geq 0\mbox{.} \]
          
%--------------------------------------------------------------------------------------------

%\newslide{Exemplo (continua\c{c}\~ao)}

%       Sejam $z_1=4y_1$, $z_2=3y_2$, $z_3=2y_3$, e $z_4=y_4$.
  
%       O n\'{u}mero de solu\c{c}\~{o}es da equa\c{c}\~{a}o \'{e} o mesmo que o n\'{u}mero de
%       solu\c{c}\~{o}es de   
       
%       $z_1+z_2+z_3+z_4=r$,
%       \newline
%       com $z_1=4,8,12,\ldots$, $z_2= 0,3,6,\ldots$, $z_3=0,2,4,\ldots$,
%       \newline
%       e $z_4=0,1,2,\ldots$.
       
%       \vspace*{3mm}
%       Logo, a fun\c{c}\~{a}o geradora \'{e}:
%       \[(1+x+x^2+\ldots)(1+x^2+x^4+\ldots)(1+x^3+x^6+\ldots)(x^4+x^8+x^{12}+
%         \ldots)\] 

%--------------------------------------------------------------------------------------------

%\newslide{EXEMPLOS DE USO DE FUNÇÕES GERADORAS (6)}
%\hypertarget{exemplos-6}{}

% \item Fun\c{c}\~{a}o geradora para o n\'{u}mero de maneiras de conseguir uma soma de r,
%       com qualquer n\'{u}mero de lan\c{c}amentos de um dado:
          
%       \vspace*{3mm}
%       A fun\c{c}\~{a}o geradora para o n\'{u}mero de maneiras de conseguir uma soma de r,
%       com $n$ lan\c{c}amentos de um dado \'{e}:
       
%       \[(x+x^2+x^3+x^4+x^5+x^6)^n\]

%       Logo, a fun\c{c}\~{a}o geradora para o problema original \'{e}:
       
%       \[1+(x+x^2+x^3+x^4+x^5+x^6)+(x+x^2+x^3+x^4+x^5+x^6)^2+\cdots\]
       
%       \vspace*{3mm}
%       Como $1/(1-y)=1+y+y^2+\cdots$, a fun\c{c}\~{a}o pode ser expressa assim:
       
%       \vspace*{3mm}
%       \[\frac{1}{1-x-x^2-x^3-x^4-x^5-x^6}\mbox{.}\]
%\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo de uso de func\~{a}o geradora para mostrar identidade
combinat\'{o}ria}

\begin{itemize}
% \item $C(n,1)+2C(n,2)+3C(n,3)+\cdots+nC(n,n)=$?
 
%       \vspace*{3mm}
%       Pelo Teorema Binominal:
%             \[(1+x)^n=C(n,0)+C(n,1)x+C(n,2)x^2+\cdots+C(n,n)x^n\]

%       Derivando-se ambos os lados, obt\'{e}m-se:       
%             \[n(1+x)^{n-1}=C(n,1)+2C(n,2)x+\cdots+nC(n,n)x^{n-1}\]
             
%       Fazendo-se $x=1$ tem-se, finalmente:       
%             \[n2^{n-1}=C(n,1)+2C(n,2)+3C(n,3)+\cdots+nC(n,n)\]
     
%--------------------------------------------------------------------------------------------

 \item $\sum_{k=0}^nC(n,k)^2=$?
 
       \vspace*{3mm}
       Lembrando que:
       \[h(x)g(x) \mbox{ \'{e} a fun\c{c}\~{a}o geradora para }
        a_0b_n+\cdots+a_nb_0\mbox{,}\]

       o coeficiente de $x^n$ em $(1+x)^n(1+x)^n$ \'{e}:
         \[\sum_{k=0}^nC(n,k)C(n,n-k)=\sum_{k=0}^nC(n,k)^2\mbox{.}\]
             
       Mas, pelo Teorema Binomial, o coeficiente de $x^n$ em $(1+x)^{2n}$ \'{e}:
       $C(2n,n)$.
     
      \vspace*{3mm}
      Logo, 
      
     \vspace*{3mm}
      \[\sum_{k=0}^nC(n,k)^2=C(2n,n)\mbox{.}\]
\end{itemize}

%--------------------------------------------------------------------------------------------

\defskiptarget{capitulo3}

\lastpage 

\end{document}

\newslide{EXEMPLOS DE USO DE FUNÇÕES GERADORAS (9)}
\hypertarget{exemplos-9}{}

\noindent \underline{O problema das permuta\c{c}\~{o}es ca\'{o}ticas} 

\vspace*{5mm}
\noindent Determinar o n\'{u}mero de permuta\c{c}\~{o}es do conjunto
$\{x_1,x_2,\ldots,x_n\}$ nas quais nenhum $x_i$ ocupe a $i$-\'{e}sima posi\c{c}\~{a}o.

\vspace*{3mm}
\noindent Seja $p_1=x_1+x_2+\cdots+x_n$ representando as escolhas poss\'{\i}veis
para uma posi\c{c}\~{a}o ($x_1$ ou $x_2$ ou \ldots ou $x_n$).

\noindent Como $p_k-x_k$ representa as escolhas poss\'{\i}veis para a posi\c{c}\~{a}o $k$,
o n\'{u}mero procurado \'{e} o coeficiente de $x_1x_2\ldots x_n$ (cada $x_k$ deve ser
escolhido exatamente 1 vez) em:
\[ (p_1-x_1)(p_1-x_2)\cdots(p_1-x_n)\mbox{.} \ \ \ \ \ (*)\]

%--------------------------------------------------------------------------------------------

\newslide{EXEMPLOS DE USO DE FUNÇÕES GERADORAS (10)}
\hypertarget{exemplos-10}{}

\begin{description}
 \item[Nota\c{c}\~{a}o:] $p_k$: soma de todos os produtos de $k$ $x_i$'s diferentes.
 
        \begin{tabular}{ll}
         $p_1=x_1+x_2+\cdots+x_n$ & $\Longrightarrow C(n,1)$ termos \\
         $p_2=x_1x_2+x_1x_3+\cdots+x_{n-1}x_n$ & $\Longrightarrow C(n,2)$
          termos \\
         $\vdots$ & \\
         $p_n=x_1x_2\ldots x_n$ & $\Longrightarrow C(n,n)$ termos
        \end{tabular}
 \item[Um resultado:]\ 
 
        $(z-x_1)(z-x_2)\cdots(z-x_n)$
        \newline
        \ \ \ $=z^n-z^{n-1}p_1+z^{n-2}p_2+\cdots+(-1)^kz^{n-k}p_k+\cdots
              +(-1)^np_n$
\end{description}


%--------------------------------------------------------------------------------------------

\newslide{EXEMPLOS DE USO DE FUNÇÕES GERADORAS (11)}
\hypertarget{exemplos-11}{}

\noindent Deste \'{u}ltimo resultado e $(*)$, tem-se que o n\'{u}mero de permuta\c{c}\~{o}es
procurado \'{e} o coeficiente de $x_1x_2\ldots x_n$ em:

\[p_1^n-p_1^{n-1}p_1+p_1^{n-2}p_2+\cdots+(-1)^kp_1^{n-k}p_k+\cdots+(-1)^np_n\]

\noindent Como o coeficiente de $x_1x_2\ldots x_n$ em $(-1)^kp_1^{n-k}p_k$ \'{e}
\[C(n,k)(n-k)!=n!/k!\mbox{,}\] a resposta \'{e}:
\[ \frac{n!}{2!}-\frac{n!}{3!}+\cdots+(-1)^n\frac{n!}{n!}\mbox{.} \]

%--------------------------------------------------------------------------------------------

\defskiptarget{capitulo3}

\lastpage 

\end{document}