\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{23 de setembro de 2007}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{epsfig,graphicx,color,latexsym,alltt,calc,ifthen,slides,hyperref} 
 
\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{Combinat\'oria Elementar \\ Baseado em Townsend (1987), Cap. 2}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 2}
\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{combinatoria-1}{Problemas Básicos de Combinatória}
\item \hyperlink{regras-soma-produto-1}{As Regras da Soma e do Produto}
\item \hyperlink{modelo-amostragem-1}{O Modelo de Amostragem}
\item \hyperlink{modelo-distribuicao-1}{O Modelo de Distribuição}
\item \hyperlink{exemplos-aplicacoes-1}{Exemplos e Aplicações}
\item \hyperlink{solucoes-inteiras-equacao-exemplos-1}{O Problema das Soluções Inteiras de uma Equação}
\item \hyperlink{identidades-combinatorias-1}{Uma Breve Visita \`as Identidades Combinatórias}
\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

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

\section{Problemas B\'asicos de Combinat\'oria}
\hypertarget{combinatoria-1}{}
\setskiplink{capitulo2}

\newslide{O QUE \'E COMBINAT\'ORIA}

\begin{itemize}
 \item \textcolor{black}{Combinat\'{o}ria:} ``a arte de contar sem contar''.
 \item \underline{Id\'{e}ia b\'{a}sica}: correspond\^{e}ncia um-para-um (fun\c{c}\~ao bijetora).
 \item Exemplo 1:
       \begin{quote}
        Seja um conjunto $A$ de $n$ elementos. Existe uma correspond\^{e}ncia
        um-para-um de ${\cal P}(A)$ para o conjunto das sequ\^{e}ncias
        bin\'{a}rias de $n$ d\'{\i}gitos. Como o n\'{u}mero destas sequ\^{e}ncias \'{e} $2^n$,
        \textcolor{red}{${\cal P}(A)$ tem $2^n$ elementos}.
       \end{quote}
\end{itemize}

\newslide{O QUE \'E COMBINAT\'ORIA}

\begin{itemize}
 \item \textcolor{black}{Combinat\'{o}ria:} ``a arte de contar sem contar''.
 \item \underline{Id\'{e}ia b\'{a}sica}: correspond\^{e}ncia um-para-um (fun\c{c}\~ao bijetora).
 \item Exemplo 2:
       \begin{quote}
        Seja o conjunto de caminhos da raiz \`{a}s folhas, para uma \'{a}rvore
        estritamente bin\'{a}ria e completa de altura $n$. Existe uma
        correspond\^{e}ncia um-para-um de tal conjunto para o conjunto das
        sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos:
              
        \begin{picture}(400,115)
         \put(200,100){\circle*{5}}
         \put(200,100){\line(-2,-1){80}}
         \put(155,85){\makebox(0,0){0}}
         \put(200,100){\line(2,-1){80}}
         \put(245,85){\makebox(0,0){1}}
               
         \put(120,60){\circle*{5}}
         \put(120,60){\line(-1,-1){40}}
         \put(95,45){\makebox(0,0){0}}
         \put(120,60){\line(1,-1){40}}
         \put(145,45){\makebox(0,0){1}}
         \put(80,20){\circle*{5}}
%         \put(80,10){\makebox(0,0){\ldots}}
         \put(160,20){\circle*{5}}
%         \put(160,10){\makebox(0,0){\ldots}}
               
         \put(280,60){\circle*{5}}
         \put(280,60){\line(-1,-1){40}}
         \put(255,45){\makebox(0,0){0}}
         \put(280,60){\line(1,-1){40}}
         \put(305,45){\makebox(0,0){1}}
         \put(240,20){\circle*{5}}
%         \put(240,10){\makebox(0,0){\ldots}}
         \put(320,20){\circle*{5}}
%         \put(320,10){\makebox(0,0){\ldots}}
        \end{picture}
               
        Logo, \textcolor{red}{o n\'{u}mero de folhas da \'{a}rvore \'{e} $2^n$}.
       \end{quote}
\end{itemize}

\newslide{O QUE \'E COMBINAT\'ORIA}

\begin{itemize}
 \item \textcolor{black}{Combinat\'{o}ria:} ``a arte de contar sem contar''.
 \item \underline{Id\'{e}ia b\'{a}sica}: correspond\^{e}ncia um-para-um (fun\c{c}\~ao bijetora).
 \item Exemplo 3:
       \begin{quote}
        Existe uma
        correspond\^{e}ncia um-para-um das linhas da tabela da verdade para o conjunto das
        sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos. Logo, \textcolor{red}{o
        n\'{u}mero de linhas de uma tabela da verdade para $n$ vari\'{a}veis
        proposicionais \'{e} $2^n$}.
       \end{quote}
\end{itemize}

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

\newslide{O QUE \'E COMBINAT\'ORIA}

\begin{itemize}
 \item Outra formula\c{c}\~{a}o do problema do n\'{u}mero de sequ\^{e}ncias bin\'{a}rias de $r$
       d\'{\i}gitos:
       \begin{quote}
        Quantas \textcolor{black}{amostras} de $r$ objetos podem ser extra\'{\i}das do conjunto
        $\{0,1\}$, se \textcolor{red}{ordem \'{e} importante} e \textcolor{red}{repeti\c{c}\~{a}o \'{e}
        permitida}?
       \end{quote}
\end{itemize}

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

\newslide{O QUE \'E COMBINAT\'ORIA}

\begin{itemize}
 \item Outra formula\c{c}\~{a}o do problema do n\'{u}mero de sequ\^{e}ncias bin\'{a}rias de $r$
       d\'{\i}gitos:
       \begin{quote}
        Quantas \textcolor{black}{amostras} de $r$ objetos podem ser extra\'{\i}das do conjunto
        $\{0,1\}$, se \textcolor{red}{ordem \'{e} importante} e \textcolor{red}{repeti\c{c}\~{a}o \'{e}
        permitida}?
       \end{quote}
 \item \textcolor{black}{Generaliza\c{c}\~{a}o do problema:}
       \begin{quote}
        Quantas \textcolor{black}{amostras} de $r$ objetos podem ser extra\'{\i}das do conjunto
        $\{x_1,x_2,\ldots,x_n\}$, se \textcolor{red}{ordem \'{e} importante} e
        \textcolor{red}{repeti\c{c}\~{a}o \'{e} permitida}?
       \end{quote}
\end{itemize}

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

\newslide{OBJETIVOS}

\noindent {Os dois objetivos:}

\begin{itemize}
 \item Identificar \textcolor{black}{problemas gerais} aos quais muitos outros possam ser
       reduzidos.
 \item Praticar a ``arte de contar sem contar''.
\end{itemize}

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

\newslide{Abstra\c{c}\~{a}o de mais 3 problemas b\'{a}sicos}

\begin{itemize}
 \item \textcolor{black}{Problema}:
       \begin{quote}
        Um torneio de nata\c{c}\~{a}o vai ser disputado por 8
        atletas. Quantas possibilidades de premia\c{c}\~{a}o existem, considerando que
        s\'{o} recebem pr\^{e}mios o primeiro (medalha de ouro), o segundo (medalha de
        prata) e o terceiro (medalha de bronze) lugares?
       \end{quote}
\end{itemize}

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

\newslide{Abstra\c{c}\~{a}o do segundo problema b\'{a}sico}

\begin{itemize}
 \item \textcolor{black}{Problema}:
       \begin{quote}
        Um torneio de nata\c{c}\~{a}o vai ser disputado por 8
        atletas. Quantas possibilidades de premia\c{c}\~{a}o existem, considerando que
        s\'{o} recebem pr\^{e}mios o primeiro (medalha de ouro), o segundo (medalha de
        prata) e o terceiro (medalha de bronze) lugares?
       \end{quote}
 \item \textcolor{black}{Problema geral:}
       \begin{quote}
        Quantas \textcolor{black}{amostras} de $r$ objetos podem ser
        extra\'{\i}das do conjunto $\{x_1,x_2,\ldots,x_n\}$, se \textcolor{red}{ordem \'{e}
        importante} e \textcolor{red}{repeti\c{c}\~{a}o n\~{a}o \'{e} permitida}?
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------
\newslide{Abstra\c{c}\~{a}o do terceiro problema b\'{a}sico}

\begin{itemize}
 \item \textcolor{black}{Problema}:
       \begin{quote}
        Quantos caminhos existem do ponto no canto
        superior esquerdo ao ponto no canto inferior direito?
       \begin{center}       
       \begin{picture}(240,90)
        \put(25,80){\makebox(0,0){1}}
        \put(55,80){\makebox(0,0){2}}
        \put(85,80){\makebox(0,0){3}}
        \put(115,80){\makebox(0,0){4}}
        \put(145,80){\makebox(0,0){5}}
        \put(175,80){\makebox(0,0){6}}
        \put(205,80){\makebox(0,0){7}}
        \put(10,70){\circle*{5}}
        \put(10,70){\line(1,0){210}}
        \put(10,50){\line(1,0){210}}
        \put(10,30){\line(1,0){210}}
        \put(10,10){\line(1,0){210}}
        \put(220,10){\circle*{5}}
        
        \put(10,10){\line(0,1){60}}
        \put(40,10){\line(0,1){60}}
        \put(70,10){\line(0,1){60}}
        \put(100,10){\line(0,1){60}}
        \put(130,10){\line(0,1){60}}
        \put(160,10){\line(0,1){60}}
        \put(190,10){\line(0,1){60}}
        \put(220,10){\line(0,1){60}}
        
        \put(230,65){\makebox(0,0){1}}
        \put(230,45){\makebox(0,0){2}}
        \put(230,25){\makebox(0,0){3}}
       \end{picture}
       \end{center}
       \end{quote}
\end{itemize}

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


\newslide{Abstra\c{c}\~{a}o do terceiro problema b\'{a}sico}

\begin{itemize}
 \item \textcolor{black}{Problema}:
       \begin{quote}
        Quantos caminhos existem do ponto no canto
        superior esquerdo ao ponto no canto inferior direito?
       \begin{center}       
       \begin{picture}(240,90)
        \put(25,80){\makebox(0,0){1}}
        \put(55,80){\makebox(0,0){2}}
        \put(85,80){\makebox(0,0){3}}
        \put(115,80){\makebox(0,0){4}}
        \put(145,80){\makebox(0,0){5}}
        \put(175,80){\makebox(0,0){6}}
        \put(205,80){\makebox(0,0){7}}
        \put(10,70){\circle*{5}}
        \put(10,70){\line(1,0){210}}
        \put(10,50){\line(1,0){210}}
        \put(10,30){\line(1,0){210}}
        \put(10,10){\line(1,0){210}}
        \put(220,10){\circle*{5}}
        
        \put(10,10){\line(0,1){60}}
        \put(40,10){\line(0,1){60}}
        \put(70,10){\line(0,1){60}}
        \put(100,10){\line(0,1){60}}
        \put(130,10){\line(0,1){60}}
        \put(160,10){\line(0,1){60}}
        \put(190,10){\line(0,1){60}}
        \put(220,10){\line(0,1){60}}
        
        \put(230,65){\makebox(0,0){1}}
        \put(230,45){\makebox(0,0){2}}
        \put(230,25){\makebox(0,0){3}}
       \end{picture}
       \end{center}
       \end{quote}
 \item \textcolor{black}{Problema geral:}
       \begin{quote}
        Quantas \textcolor{black}{amostras} de $r$ objetos podem ser
        extra\'{\i}das do conjunto $\{x_1,x_2,\ldots,x_n\}$, se \textcolor{red}{ordem n\~{a}o
        \'{e} importante} e \textcolor{red}{repeti\c{c}\~{a}o n\~{a}o \'{e} permitida}?
       \end{quote}
\end{itemize}

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


\newslide{Abstra\c{c}\~{a}o do quarto problema b\'{a}sico}

\begin{itemize}
 \item \textcolor{black}{Problema}:
       \begin{quote}
        Quantos domin\'{o}s existem?
       \end{quote}
\end{itemize}

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


\newslide{Abstra\c{c}\~{a}o do quarto problema b\'{a}sico}

\begin{itemize}
 \item \textcolor{black}{Problema}:
       \begin{quote}
        Quantos domin\'{o}s existem?
       \end{quote}
 \item \textcolor{black}{Problema geral:}
       \begin{quote}
        Quantas \textcolor{red}{amostras} de $r$ objetos podem ser
        extra\'{\i}das do conjunto $\{x_1,x_2,\ldots,x_n\}$, se \textcolor{red}{ordem n\~{a}o \'{e}
        importante} e \textcolor{red}{repeti\c{c}\~{a}o \'{e} permitida}?
       \end{quote}
\end{itemize}

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

\section{As Regras da Soma e do Produto}
\hypertarget{regras-soma-produto-1}{}

\newslide{A REGRA DA SOMA}
\begin{itemize}
 \item \textcolor{black}{Regra da soma:}
       \begin{quote}
        Sejam $A$ e $B$ dois eventos disjuntos (isto \'{e}, que n\~{a}o
        ocorrem ao mesmo tempo), tais que $A$ ocorre de $m$ maneiras e $B$ ocorre
        de $n$ maneiras. Ent\~{a}o o evento $A$ \underline{ou} $B$ ocorre de $m+n$
        maneiras.
       \end{quote}
\end{itemize}

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

\newslide{A REGRA DA SOMA}
\begin{itemize}
 \item \textcolor{black}{Regra da soma:}
       \begin{quote}
        Sejam $A$ e $B$ dois eventos disjuntos (isto \'{e}, que n\~{a}o
        ocorrem ao mesmo tempo), tais que $A$ ocorre de $m$ maneiras e $B$ ocorre
        de $n$ maneiras. Ent\~{a}o o evento $A$ \underline{ou} $B$ ocorre de $m+n$
        maneiras.
       \end{quote}
 \item Exemplos:
       \begin{itemize}
        \item Quantas maneiras existem de retirar um \'{a}s ou uma dama de um baralho?
        \item Quantas maneiras existem de retirar um \'{a}s ou uma carta vermelha?
       \end{itemize}
\end{itemize}

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

\newslide{A REGRA DO PRODUTO}
\begin{itemize}
 \item \textcolor{black}{Regra do produto:}
       \begin{quote}
        Suponha que um evento $C$ possa ser decomposto em duas
        etapas $A$ e $B$, tais que $A$ ocorre de $m$ maneiras e $B$ ocorre
        de $n$ maneiras, independentemente de $A$. Ent\~{a}o o evento $C$ ocorre de
        $m\times n$ maneiras.
       \end{quote}
\end{itemize}

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

\newslide{A REGRA DO PRODUTO}
\begin{itemize}
 \item \textcolor{black}{Regra do produto:}
       \begin{quote}
        Suponha que um evento $C$ possa ser decomposto em duas
        etapas $A$ e $B$, tais que $A$ ocorre de $m$ maneiras e $B$ ocorre
        de $n$ maneiras, independentemente de $A$. Ent\~{a}o o evento $C$ ocorre de
        $m\times n$ maneiras.
       \end{quote}
 \item Exemplos:
       \begin{itemize}
        \item Quantas maneiras existem de distribuir um \'{a}s vermelho e, em seguida,
              outra carta vermelha?
        \item Quantas maneiras existem de distribuir um \'{a}s e, em seguida, uma carta
              vermelha?
        \item Quantas sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos existem?
       \end{itemize}
\end{itemize}

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

\newslide{O Problema do Anivers\'ario}
\begin{itemize}
 \item Qual \'e a probabilidade de que pelo menos duas dentre $n$ pessoas selecionadas
       ao acaso fa\c{c}am anivers\'ario no mesmo dia do ano?
 \item Espa\c{c}o amostral: $S=\{1/1, 1/2, \ldots, 12/12\}^n$; $N(S)=365^n$.
 \item N\'umero de maneiras de atribuir anivers\'arios de forma que pelo menos duas
       pessoas fa\c{c}am anivers\'ario no mesmo dia:
       $N(E)=N(S)-m$, onde $m$ \'e o n\'umero de maneiras de atribuir anivers\'arios
       sem que pessoas fa\c{c}am anivers\'ario no mesmo dia.
       
       $m=365\times 364\times\cdots\times (365-(n-1))$.
 \item Logo:
 
       \[\mbox{prob}(E)=\frac{365^n-365\times 364\times\cdots\times (365-(n-1))}{365^n}\]
\end{itemize}

%--------------------------------------------------------------------------------------------
\newslide{O Problema do Anivers\'ario}
\begin{itemize}
 \item Qual \'e a probabilidade de que pelo menos duas dentre $n$ pessoas selecionadas
       ao acaso fa\c{c}am anivers\'ario no mesmo dia do ano?
      \[\mbox{prob}(E)=\frac{365^n-365\times 364\times\cdots\times (365-(n-1))}{365^n}\]
 \item $n \geq 23 \Rightarrow \mbox{prob} > 0,5$. \\
 \\
       $n = 30 \Rightarrow \mbox{prob} > 0,7$.
\end{itemize}

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

\section{O Modelo de Amostragem}
\hypertarget{modelo-amostragem-1}{}

\newslide{O modelo de amostragem}

\begin{itemize}
 \item Quantas amostras de $r$ objetos podem ser extra\'{\i}das de um
       conjunto de $n$ objetos?

\vspace*{7mm}
       A resposta depende de:
       
       \begin{itemize}
        \item \textcolor{red}{Ordem} \'{e} importante?
        \item \textcolor{red}{Repeti\c{c}\~{a}o} \'{e} importante?
       \end{itemize}         
\end{itemize}

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

\newslide{O modelo de amostragem}

\noindent Exemplo: amostras de 2 objetos de $\{x_1,x_2,x_3\}$:

\vspace*{10mm}
{ \Large
	\begin{center}
 \begin{tabular}{|c|cc|cc|} \hline
  & \multicolumn{2}{c|}{\textcolor{black}{com reposi\c{c}\~{a}o}} &
              \multicolumn{2}{c|}{\textcolor{black}{sem reposi\c{c}\~{a}o}} \\
  & \multicolumn{2}{c|}{(com repeti\c{c}\~{a}o)} &
              \multicolumn{2}{c|}{(sem repeti\c{c}\~{a}o)} \\ \hline
  & $x_1 x_1$ & & $x_1 x_2$ &\\           
  & $x_1 x_2$ & & $x_1 x_3$ &\\           
  & $x_1 x_3$ & & $x_2 x_1$ &\\           
  \textcolor{black}{arranjo} & $x_2 x_1$ & \textcolor{red}{sequ\^{e}ncia} & $x_2 x_3$ &
    \textcolor{red}{permuta\c{c}\~{a}o}\\           
  {\bf (ordem importante)} & $x_2 x_2$ & & $x_3 x_1$ & \\
  & $x_2 x_3$ & & $x_3 x_2$ &\\           
  & $x_3 x_1$ & & & \\           
  & $x_3 x_2$ & & & \\           
  & $x_3 x_3$ & & & \\ \hline
  & $\{x_1,x_1\}$ & & $\{x_1,x_2\}$ & \\          
  & $\{x_1,x_2\}$ & & $\{x_1,x_3\}$ & \\          
  \textcolor{black}{sele\c{c}\~{a}o} & $\{x_1,x_3\}$ & \textcolor{red}{multiconjunto} & $\{x_2,x_3\}$ &
    \textcolor{red}{combina\c{c}\~{a}o}\\          
  {\bf (sem ordem)} & $\{x_2,x_2\}$ & & & \\ 
  & $\{x_2,x_3\}$ & & & \\  
  & $\{x_3,x_3\}$ & & & \\ \hline         
 \end{tabular}
 \end{center}
 }

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

\newslide{Solu\c{c}\~{o}es dos 4 Problemas}

\begin{itemize}
 \item N\'{u}mero de \textcolor{red}{sequ\^{e}ncias} de tamanho $r$:
       \begin{quote}
        $n^r$.
       \end{quote}
	\item N\'{u}mero de \textcolor{red}{permuta\c{c}\~{o}es} de tamanho $r$:
       \begin{quote}
        $P(n,r)=n(n-1)\cdots (n-r+1)=\frac{n!}{(n-r)!}$.
       \end{quote}
 \item N\'{u}mero de \textcolor{red}{combina\c{c}\~{o}es} de tamanho $r$:
       \begin{quote}
        $C(n,r)=\frac{P(n,r)}{r!}=\frac{n!}{r!(n-r)!}$.
       \end{quote}
 \item N\'{u}mero de \textcolor{red}{multiconjuntos} de tamanho $r$:
       \begin{quote}
        $C(n-1+r,r)=\frac{(n-1+r)!}{r!(n-1)!}$.
       \end{quote}
\end{itemize}

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

\newslide{Exemplos}

\begin{itemize}
 \item N\'{u}mero de arranjos das cartas de um baralho:
       \begin{quote}
        $P(52,52)=52!\approx 7,96 \times 10^{67}$.
       \end{quote}
 
 \item N\'{u}mero de resultados poss\'{\i}veis no lan\c{c}amento de 3 dados:
       \begin{quote}
        $6^3=216$.
       \end{quote}

 \item N\'{u}mero de domin\'{o}s:
       \begin{quote}
        $C(7-1+2,2)=C(8,2)=\frac{8\times 7}{2}=28$.
       \end{quote}

 \item N\'{u}mero de m\~{a}os de 5 cartas, no baralho:
       \begin{quote}
        $C(52,5)=2.598.960$.
       \end{quote}
\end{itemize}

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

\newslide{Exemplos}

\begin{itemize}
 \item Probabilidade de ocorrer um {\it flush\/} (5 cartas do mesmo naipe) no
       p\^{o}quer:
       \begin{quote}
        $\frac{\mbox{n\'{u}mero de {\it flushes}}}{\mbox{n\'{u}mero de m\~{a}os
                  de 5 cartas}}=\frac{4\times C(13,5)}{C(52,5)}=0,00198$.
       \end{quote}

 \item N\'{u}mero de arranjos com as letras da palavra ``banana'':
       \begin{quote}
        $C(6,3)\times C(3,2)\times 1=60$.
       \end{quote}
\end{itemize}

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

\section{O Modelo de Distribui\c{c}\~ao}
\hypertarget{modelo-distribuicao-1}{}

\newslide{O modelo de distribui\c{c}\~{a}o}

\begin{itemize}
 \item De quantas maneiras $r$ bolas podem ser distribu\'{\i}das em $n$
               caixas distintas?

\vspace*{7mm}
       A resposta depende de:
       
       \begin{itemize}
        \item As bolas s\~{a}o distintas ou id\^{e}nticas?
        \item Cada caixa comporta qualquer n\'{u}mero de bolas, ou apenas uma bola?
       \end{itemize}         
\end{itemize}

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

\newslide{O modelo de distribui\c{c}\~{a}o}

\noindent Exemplo: distribui\c{c}\~{a}o de 2 bolas em 3 caixas:

\vspace*{5mm}
{ \Large
\begin{center}
 \begin{tabular}{|c|ccc|ccc|} \hline
  & \multicolumn{3}{c|}{\textcolor{black}{ocupa\c{c}\~{a}o n\~{a}o exclusiva}} &
              \multicolumn{3}{c|}{\textcolor{black}{ocupa\c{c}\~{a}o exclusiva}} \\ \hline
  & \underline{caixa 1} & \underline{caixa 2} & \underline{caixa 3} &
    \underline{caixa 1} & \underline{caixa 2} & \underline{caixa 3}\\           
  & $B_1 B_2$ & & & $B_1$ & $B_2$ &\\           
  & $B_1$ & $B_2$ & & $B_1$ & & $B_2$\\           
  & $B_1$ & & $B_2$ & $B_2$ & $B_1$ &\\           
  \textcolor{black}{bolas} & $B_2$ & $B_1$ & & & $B_1$ & $B_2$ \\           
  \textcolor{black}{distintas} & & $B_1 B_2$ & & $B_2$ & & $B_1$ \\
  & & $B_1$ & $B_2$ & & $B_2$ & $B_1$\\           
  & $B_2$ & & $B_1$ & & & \\           
  & & $B_2$ & $B_1$ & & & \\           
  & & & $B_1 B_2$ & & & \\ \hline
  & $B B$ & & & $B$ & $B$ & \\          
  & $B$ & $B$ & & $B$ & & $B$\\          
  \textcolor{black}{bolas} & $B$ & & $B$ & & $B$ & $B$ \\          
  \textcolor{black}{id\^{e}nticas} & & $B B$ & & & & \\ 
  & & $B$ & $B$ & & & \\ 
  & & & $B B$ & & & \\ \hline         
 \end{tabular}
 \end{center}
 }

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

\newslide{Solu\c{c}\~{o}es dos 4 Problemas:}

\begin{itemize}
 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ bolas distintas em $n$ caixas:
       \begin{quote}
        $n^r$.
       \end{quote}
 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ bolas distintas em $n$ caixas, 1 bola por
       caixa:
       \begin{quote}
        $P(n,r)$.
       \end{quote}
 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ bolas id\^{e}nticas em $n$ caixas:
       \begin{quote}
        $C(n-1+r,r)$.
       \end{quote}
 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ bolas id\^{e}nticas em $n$ caixas, 1 bola por
       caixa:
       \begin{quote}
        $C(n,r)$.
       \end{quote}
\end{itemize}

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

\newslide{2 problemas de distribui\c{c}\~{a}o em caixas id\^{e}nticas}

\begin{itemize}
 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ \textcolor{red}{bolas distintas}
       em $n$ \textcolor{red}{caixas id\^{e}nticas}:
       \begin{quote}
        \'E o n\'{u}mero de parti\c{c}\~{o}es do conjunto $\{b_1,b_2,\ldots,b_r\}$ em,
        no m\'{a}ximo, $n$ subconjuntos. Exemplo para $r=4$ e $n=3$:

                  \[ 
                    \begin{array}{l|l}
                     \{b_1,b_2,b_3,b_4\}      & \{b_1\} \{b_2\} \{b_3,b_4\} \\
                     \{b_1\} \{b_2,b_3,b_4\}  & \{b_1\} \{b_3\} \{b_2,b_4\} \\
                     \{b_2\} \{b_1,b_3,b_4\}  & \{b_1\} \{b_4\} \{b_2,b_3\} \\
                     \{b_3\} \{b_1,b_2,b_4\}  & \{b_2\} \{b_3\} \{b_1,b_4\} \\
                     \{b_4\} \{b_1,b_2,b_3\}  & \{b_2\} \{b_4\} \{b_1,b_3\} \\
                     \{b_1,b_2\} \{b_3,b_4\}  & \{b_3\} \{b_4\} \{b_1,b_2\} \\
                     \{b_1,b_3\} \{b_2,b_4\} \\
                     \{b_1,b_4\} \{b_2,b_3\}
                    \end{array}
                  \]
       \end{quote}

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

\newslide{2 problemas de distribui\c{c}\~{a}o em caixas id\^{e}nticas}

 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ \textcolor{red}{bolas id\^{e}nticas}
       em $n$ \textcolor{red}{caixas id\^{e}nticas}:
       \begin{quote}
        \'E o n\'{u}mero de parti\c{c}\~{o}es do inteiro positivo $r$ em, no m\'{a}ximo,
        $n$ partes. (Uma parti\c{c}\~{a}o de um inteiro positivo $r$ \'{e} uma
        maneira de escrever $r$ como uma soma de inteiros positivos,
        chamados partes, em ordem decrescente.) Exemplo para $r=4$ e $n=3$:

                  \[
                    \begin{array}{ll}
                     \{b,b,b,b\}         & (4) \\
                     \{b\} \{b,b,b\}     & (3+1) \\
                     \{b,b\} \{b,b\}     & (2+2) \\
                     \{b\} \{b\} \{b,b\} & (2+1+1)
                    \end{array}
                  \]
       \end{quote}
\end{itemize} 

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

\section{Exemplos e Aplica\c{c}\~{o}es}
\hypertarget{exemplos-aplicacoes-1}{}

\newslide{Jogos de Azar}
\noindent Supondo apostas simples, no jogo da sena:
\begin{itemize}
 \item Probabilidade de acertar a sena:
%       \begin{quote}
       \[\frac{1}{C(60,6)}= \frac{1}{50.063.860}\]
%       \end{quote}
 \item Probabilidade de acertar a quina: 
       \[ \frac{C(6,5)\times C(54,1)}{C(60,6)}=\frac{1}{154.518}\]

 \item Probabilidade de acertar a quadra: 
       \[ \frac{C(6,4)\times C(54,2)}{C(60,6)}=\frac{1}{2.332}\]
\end{itemize}

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

\newslide{Jogos de Azar}

\noindent No jogo de p\^{o}quer:
\begin{itemize}
 \item Probabilidade de sair com um {\it full house\/} (um trio e um par):
       \[ \frac{(C(13,1)\times C(4,3))\times(C(12,1)\times C(4,2))}{C(52,5)}
       \approx 0.0014...\]
\end{itemize}

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

\newslide{Coeficientes Multinomiais}

\begin{itemize}
 \item N\'{u}mero de maneiras de arranjar as letras da palavra BANANA:
 
       \[C(6,1)\times C(5,2)\times C(3,3)=\frac{6!}
                      {1!\times 2!\times 3!}\]

 \item \textcolor{black}{Problema Geral}: N\'{u}mero de arranjos de $n$ objetos, $r_1$ do
       tipo 1, $r_2$ do tipo 2, \ldots, $r_k$ do tipo $k$, sendo
       $r_1+r_2+\cdots+r_k=n$:
       
       \[P(n;r_1,r_2,\ldots,r_k)=\frac{n!}{r_1! r_2! \ldots r_k!}\]

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

\newslide{Coeficientes Multinomiais}

 \item N\'{u}mero de maneiras de distribuir as 52 cartas do baralho entre 4
       jogadores, se cada um recebe 13 cartas:
 
       \[ C(52,13)\times C(39,13)\times C(26,13)\times C(13,13) \]

 \item \textcolor{black}{Problema Geral}: N\'{u}mero de sele\c{c}\~{o}es simult\^{a}neas de tamanhos
       $r_1$, $r_2$, \ldots, $r_k$ a partir de um conjunto de $n$ objetos, sendo
       $r_1+r_2+\cdots+r_k=n$:
       
       \[C(n;r_1,r_2,\ldots,r_k)=P(n;r_1,r_2,\ldots,r_k)=
         \frac{n!}{r_1! r_2! \ldots r_k!}\]
\end{itemize}

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

\newslide{Estrat\'{e}gias com Arranjos}

\noindent N\'{u}mero de arranjos das letras de ``JARDIM'',
\begin{itemize}
 \item com vogais em ordem alfab\'{e}tica.
 
       Estrat\'{e}gia:
       \begin{itemize}
        \item sele\c{c}\~{a}o das posi\c{c}\~{o}es das vogais $\Longrightarrow C(6,2)$
        \item restri\c{c}\~{a}o de ordem para A e I $\Longrightarrow 1$
        \item arranjo das consoantes $\Longrightarrow 4!$
       \end{itemize}
       
       Resposta: $C(6,2)\times 1\times 4! = 360$.
\end{itemize}

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

\newslide{Estrat\'{e}gias com Arranjos}

\noindent N\'{u}mero de arranjos das letras de ``JARDIM'',
\begin{itemize}
 \item com vogais consecutivas.
 
       Estrat\'{e}gia:
       \begin{itemize}
        \item constru\c{c}\~{a}o de ``supervogais'' AI e IA $\Longrightarrow 2$
        \item arranjo das consoantes e uma supervogal $\Longrightarrow 5!$
       \end{itemize}
       
       Resposta: $2\times 5! = 240$.
\end{itemize}

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

\newslide{Estrat\'{e}gias com Arranjos}

\noindent N\'{u}mero de arranjos das letras de ``JARDIM'',
\begin{itemize}
 \item sem vogais consecutivas.
 
       Estrat\'{e}gia:
       \begin{itemize}
        \item arranjo de 2 V's e 4 C's sem V's consecutivos:
              \begin{itemize}
               \item come\c{c}amos com $\diamond$V$\diamond$CV$\diamond$;
               \item os 3 C's restantes podem ser colocados em qualquer uma das
                     3 regi\~{o}es marcadas $\Longrightarrow C(3-1+3,3)=10$
              \end{itemize}
        \item substitui\c{c}\~{a}o de V's e C's por vogais e consoantes \linebreak
              $\Longrightarrow 2! \times 4!=48$
       \end{itemize}
       
       Resposta: $10\times 48 = 480$.
\end{itemize}

%--------------------------------------------------------------------------------------------
\section{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o}
\hypertarget{solucoes-inteiras-equacao-exemplos-1}{}

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o}

\begin{itemize}
 \item Quantas solu\c{c}\~{o}es inteiras existem para
       \[ x_1+x_2+x_3=10, \mbox{ com } x_i\geq 0\mbox{?} \]
 \item Problemas equivalentes:
       \begin{itemize}
        \item N\'{u}mero de maneiras de selecionar $r$ objetos dentre $n$ objetos,
              com repeti\c{c}\~{o}es permitidas.
        \item N\'{u}mero de maneiras de distribuir $r$ bolas id\^{e}nticas em $n$
              caixas distintas, com qualquer n\'{u}mero de bolas por caixa. 
        \item N\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+\cdots+x_n=r,
              \mbox{ com } x_i\geq 0\mbox{.}\]
       \end{itemize}
\end{itemize}

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

%\newslide{EXEMPLOS E APLICAÇÕES (13)}
%\hypertarget{exemplos-aplicacoes-13}{}

%\noindent \underline{Controle de Qualidade}

%\vspace*{5mm}
%\begin{itemize}
% \item Uma firma produz 10 mil componentes de computador. \'{E} tomada uma amostra
%       de 100 componentes, e verifica-se que 5 est\~{a}o defeituosos. Qual \'{e} a
%       probabilidade que isto ocorra se houver $k$ componentes defeituosos?
       
%       \[ \frac{C(k,5)\times C(10.000-k,95)}{C(10.000,100)} \]
%\end{itemize}

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

%\newslide{EXEMPLOS E APLICAÇÕES (14)}
%\hypertarget{exemplos-aplicacoes-14}{}

%\noindent \underline{Paradoxo de De M\'{e}r\'{e}}

%\vspace*{5mm}
%\noindent De M\'{e}r\'{e} (1607--1684) achava que as seguintes probabilidades deveriam
%ser iguais, pelo fato de que \[ \frac{2}{3}\times 6 = 4 \mbox{ e }
%\frac{2}{3}\times 36 = 24 \]
%sendo: 6 o n\'{u}mero de resultados do lan\c{c}amento de um dado (um deles, o 6); e
%36 o n\'{u}mero de resultados do lan\c{c}amento de um par de dados (um deles, o par 66).

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

%\newslide{EXEMPLOS E APLICAÇÕES (15)}
%\hypertarget{exemplos-aplicacoes-15}{}

%\begin{itemize}
% \item Probabilidade de que 4 lan\c{c}amentos de um dado produza pelo menos um 6:
 
%       \[ \frac{6^4 - 5^4}{6^4}=0,5177... \]

% \item Probabilidade de que 24 lan\c{c}amentos de um par de dados produza pelo menos
%       um par de 6:
 
%       \[ \frac{36^{24} - 35^{24}}{36^{24}}=0,4914... \]
%\end{itemize}

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

\begin{itemize}
 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+x_3+x_4
       \mbox{\boldmath{$\leq$}}99, \mbox{ com } x_i\geq 0\]
\end{itemize}

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

\begin{itemize}
 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+x_3+x_4
       \mbox{\boldmath{$\leq$}}99, \mbox{ com } x_i\geq 0\] \'{e} a soma dos n\'{u}meros
       de solu\c{c}\~{o}es para
       \[\begin{array}{c}
        x_1+x_2+x_3+x_4 = 0 \\
        x_1+x_2+x_3+x_4 = 1 \\
        \vdots \\
        x_1+x_2+x_3+x_4 = 99\mbox{.}
       \end{array} \]
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

\begin{itemize}
 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+x_3+x_4
       \mbox{\boldmath{$\leq$}}99, \mbox{ com } x_i\geq 0\] \'{e} a soma dos n\'{u}meros
       de solu\c{c}\~{o}es para
       \[\begin{array}{c}
        x_1+x_2+x_3+x_4 = 0 \\
        x_1+x_2+x_3+x_4 = 1 \\
        \vdots \\
        x_1+x_2+x_3+x_4 = 99\mbox{.}
       \end{array} \]
       \'{E} tamb\'{e}m o n\'{u}mero de solu\c{c}\~{o}es para
        \[x_1+x_2+x_3+x_4+\mbox{\boldmath{$x_5$}}=99\mbox{.}\]
%\end{itemize}

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[\mbox{\boldmath{$2$}}x_1+x_2+x_3=4,
       \mbox{ com } x_i\geq 0\]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[\mbox{\boldmath{$2$}}x_1+x_2+x_3=4,
       \mbox{ com } x_i\geq 0\] \'{e} o n\'{u}mero de solu\c{c}\~{o}es para \[y+x_2+x_3=4,
       \mbox{ com } y=0,2,4,\ldots \mbox{ e } x_2,x_3\geq 0\mbox{.}\]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+x_3=0, \mbox{ com }
       x_i\geq \mbox{\boldmath{$-5$}}\]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+x_3=0, \mbox{ com }
       x_i\geq \mbox{\boldmath{$-5$}}\] \'{e} o n\'{u}mero de solu\c{c}\~{o}es para
       \[(y_1-5)+(y_2-5)+(y_3-5)=0, \mbox{ com } y_i\geq 0\mbox{,}\]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de solu\c{c}\~{o}es inteiras para \[x_1+x_2+x_3=0, \mbox{ com }
       x_i\geq \mbox{\boldmath{$-5$}}\] \'{e} o n\'{u}mero de solu\c{c}\~{o}es para
       \[(y_1-5)+(y_2-5)+(y_3-5)=0, \mbox{ com } y_i\geq 0\mbox{,}\]
       ou seja, o n\'{u}mero de solu\c{c}\~{o}es para
       \[y_1+y_2+y_3=15, \mbox{ com } y_i\geq 0\mbox{,}\]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item \textcolor{black}{O Problema dos Dados de Galileu}(1564--1643): Por que uma soma de 10
       aparece t\~{a}o frequentemente no lan\c{c}amento de 3 dados?

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item \textcolor{black}{O Problema dos Dados de Galileu}(1564--1643): Por que uma soma de 10
       aparece t\~{a}o frequentemente no lan\c{c}amento de 3 dados?

\vspace*{6mm}
       Probabilidade de que o lan\c{c}amento de 3 dados produza uma soma de 10:
       
       \[ \frac{\mbox{n\'{u}mero de solu\c{c}\~{o}es para $x_1+x_2+x_3=10$, com $1\leq x_i
          \leq 6$}}{6^3} \]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de sele\c{c}\~{o}es de $r$ objetos dentre $n$, sem repeti\c{c}\~{o}es, \'{e} igual
       ao n\'{u}mero de distribui\c{c}\~{o}es de r bolas id\^{e}nticas em $n$ caixas, uma bola
       por caixa. Isto \'{e} igual tamb\'{e}m ao n\'{u}mero de solu\c{c}\~{o}es inteiras para:
       \[x_1+x_2+\cdots+x_n=r, \mbox{ com } x_i\in \{0,1\}\mbox{,}\]

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de maneiras de totalizar $r$ centavos utilizando moedas de 1, 5,
       10 e 25 centavos \'{e} o n\'{u}mero de solu\c{c}\~{o}es inteiras para:

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

\newslide{O Problema das Solu\c{c}\~{o}es Inteiras de uma Equa\c{c}\~{a}o/Exemplos}

 \item O n\'{u}mero de maneiras de totalizar $r$ centavos utilizando moedas de 1, 5,
       10 e 25 centavos \'{e} o n\'{u}mero de solu\c{c}\~{o}es inteiras para:
       \[x_1+x_2+x_3+x_4=r, \mbox{ com } \left\{ \begin{array}{l}
                                                  x_1=0,1,2,\ldots \\
                                                  x_2=0,5,10,\ldots \\
                                                  x_3=0,10,20,\ldots \\
                                                  x_4=0,25,50,\ldots
                                                 \end{array} 
                                         \right. \]
\end{itemize}

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

\section{UMA BREVE VISITA \`AS IDENTIDADES COMBINATÓRIAS}
\hypertarget{identidades-combinatorias-1}{}

\newslide{Identidades Combinat\'orias}
\noindent \textcolor{black}{Argumentos combinat\'{o}rios}:

\vspace*{6mm}
\begin{itemize}
 \item s\~{a}o usualmente \textcolor{red}{mais simples} que indu\c{c}\~{a}o ou \'{a}lgebra;
 \item ajuda-nos a lembrar do \textcolor{red}{conte\'{u}do} da identidade.
\end{itemize}


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

\newslide{Exemplos de Identidades Combinat\'orias}

\begin{itemize}
 \item Identidade de Pascal: \[C(n,r)=C(n-1,r-1)+C(n-1,r)\]
\end{itemize}

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

\newslide{Exemplos de Identidades Combinat\'orias}

\begin{itemize}
 \item Identidade de Pascal: \[C(n,r)=C(n-1,r-1)+C(n-1,r)\]
 
       \textcolor{black}{Prova:} 2 maneiras de contar os mesmos subconjuntos do conjunto
       $\{x_1,x_2,\ldots,x_n\}$:
       
       \begin{enumerate}
        \item $C(n,r)$: n\'{u}mero de subconjuntos de $r$ elementos.
        \item $C(n-1,r-1)$: \parbox[t]{16cm}{n\'{u}mero de subconjuntos de $r$ elementos que
              cont\^{e}m $x_n$.}
              
              $C(n-1,r)$: \parbox[t]{16cm}{n\'{u}mero de subconjuntos de $r$ elementos que n\~{a}o
              cont\^{e}m $x_n$.}
       \end{enumerate}

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

\newslide{Exemplos de Identidades Combinat\'orias}

 \item N\'{u}mero de subconjuntos: \[\sum_{k=0}^{n}C(n,k)=2^n\]
 
       \textcolor{black}{Prova:} 2 maneiras de contar todos os subconjuntos do conjunto
       $\{x_1,x_2,\ldots,x_n\}$:
       
%--------------------------------------------------------------------------------------------

\newslide{Exemplos de Identidades Combinat\'orias}

 \item N\'{u}mero de subconjuntos: \[\sum_{k=0}^{n}C(n,k)=2^n\]
 
       \textcolor{black}{Prova:} 2 maneiras de contar todos os subconjuntos do conjunto
       $\{x_1,x_2,\ldots,x_n\}$:
       
       \begin{enumerate}
        \item $2^n$: n\'{u}mero total de subconjuntos (como j\'{a} vimos).
        \item $C(n,0)$: n\'{u}mero de subconjuntos de $0$ elementos.
        
              $C(n,1)$: n\'{u}mero de subconjuntos de $1$ elemento.
              
              $\vdots$
              
              $C(n,n)$: n\'{u}mero de subconjuntos de $n$ elementos.
       \end{enumerate}


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

\newslide{Exemplos de Identidades Combinat\'orias}

 \item Grupos e l\'{\i}deres:  \[C(n,k)C(k,r)=C(n,r)C(n-r,k-r)\]
 
       \textcolor{black}{Prova:} 2 maneiras de contar todas as maneiras de se selecionar, a partir
       de um universo de $n$ pessoas, um grupo de k pessoas e $r$ l\'{\i}deres dentre
       estas $k$ pessoas:
       \begin{enumerate}
        \item $C(n,k)$: n\'{u}mero de grupos de $k$ pessoas.
        
              $C(k,r)$: n\'{u}mero de l\'{\i}deres dentre $k$ pessoas.
              
        \item $C(n,r)$: n\'{u}mero de grupos de $r$ l\'{\i}deres.
        
              $C(n-r,k-r)$: \parbox[t]{16cm}{n\'{u}mero de n\~ao l\'{\i}deres para completar o grupo.}
       \end{enumerate}

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

\newslide{Exemplos de Identidades Combinat\'orias}

\item Multiconjuntos: \[\sum_{i=0}^{r}C(n+i,i)=C(n+r+1,r)\]
 
       \textcolor{black}{Prova:} 2 maneiras de contar todos os multiconjuntos de tamanho $r$, com
       elementos do conjunto $\{x_1,x_2,\ldots,x_{n+2}\}$:
       \begin{enumerate}
        \item $C(n+2-1+r,r)=C(n+r+1,r)$:

              \begin{enumerate}
               \item[\ \ \ ] n\'{u}mero total de multiconjuntos de tamanho $r$
                             (como j\'{a} vimos).
              \end{enumerate}

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

\newslide{Exemplos de Identidades Combinat\'orias}
\item $C(n+1-1+r,r)=C(n+r,r)$:

              \begin{enumerate}
               \item[\ \ \ ] n\'{u}mero de multiconjuntos de tamanho $r$ sem
                             ocorr\^{e}ncias de $x_{n+2}$.
              \end{enumerate}

              $C(n+1-1+r-1,r-1)=C(n+r-1,r-1)$:
              
              \begin{enumerate}
               \item[\ \ \ ] n\'{u}mero de multiconjuntos de tamanho $r$ com
                             1 ocorr\^{e}ncia de $x_{n+2}$.
              \end{enumerate}
              
              $\vdots$
              
              $C(n+1-1+r-r,r-r)=C(n,0)$:

              \begin{enumerate}
               \item[\ \ \ ] n\'{u}mero de multiconjuntos de tamanho $r$ com
                             $r$ ocorr\^{e}ncias de $x_{n+2}$.
              \end{enumerate}
       \end{enumerate}

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

\newslide{Exemplos de Identidades Combinat\'orias}

 \item \textcolor{black}{Teorema Binomial}: \[(x+y)^n=\sum_{r=0}^{n}C(n,r)x^{n-r}y^r\]
 
       \textcolor{black}{Prova:} Dado que \[ (x+y)^n=\underbrace{(x+y)(x+y)\cdots(x+y)}_{n}\]
       cada termo do resultado \'{e} da forma $x^{n-r}y^r$, $0\leq r\leq n$.
       O n\'{u}mero de termos desta forma \'{e} o n\'{u}mero de maneiras de selecionar $n-r$
       $x$'s (ou $r$ $y$'s), ou seja, $C(n,n-r)=C(n,r)$.
        %--------------------------------------------------------------------------------------------

\newslide{Exemplos de Identidades Combinat\'orias}
       
       Exemplos de uso do Teorema Binomial:
       
       \begin{itemize}
        \item $\sum_{k=0}^{n}C(n,k)=2^n$.
        
              Prova: basta fazer $x=y=1$.
        \item $C(n,0)+C(n,2)+\cdots=C(n,1)+C(n,3)+\cdots=2^{n-1}$
        
              Prova: fazendo-se $x=1$ e $y=-1$, tem-se:
              \[C(n,0)-C(n,1)+C(n,2)-C(n,3)+\cdots+(-1)^nC(n,n)=0\]
       \end{itemize}

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

\newslide{Exemplos de Identidades Combinat\'orias}

 \item \textcolor{black}{Teorema Multinomial}: \[(x_1+\cdots+x_k)^n=
       \sum_{r_1+\cdots+r_k=n}C(n;r_1,\ldots,r_k)x_1^{r_1}\ldots x_k^{r_k}\]
 
       \textcolor{black}{Prova:} Dado que \[ (x_1+\cdots+x_k)^n=
       \underbrace{(x_1+\cdots+x_k)\cdots(x_1+\cdots+x_k)}_{n}\]
       cada termo do resultado \'{e} da forma $x_1^{r_1}\ldots x_k^{r_k}$, sendo
       $r_1+\cdots+r_k=n$. O n\'{u}mero de termos desta forma \'{e} o n\'{u}mero de maneiras
       de selecionar $r_1$ $x_1$'s, \ldots, $r_k$ $x_k$'s, totalizando um total
       de $n$ destes objetos, ou seja, $C(n;r_1,r_2,\ldots,r_k)$.
\end{itemize}

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

\defskiptarget{capitulo2}

\lastpage 

\end{document}