\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{19 de novembro 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

\title{Princípio da Inclusão e Exclusão \\ Baseado em Townsend (1987), Cap. 5}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 5}
\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{principio-inclusao-exclusao-1}{Princípio da Inclusão e Exclusão}
\item \hyperlink{exemplos-1}{Alguns Exemplos de Uso do Princípio da Inclusão e Exclusão}
\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

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

\section{PRINCÍPIO DA INCLUSÃO E EXCLUSÃO}
\hypertarget{principio-inclusao-exclusao-1}{}
\setskiplink{capitulo5}

\newslide{Princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o para 2 conjuntos}

\begin{itemize}
 \item Nota\c{c}\~{a}o:
       \begin{quote} 
        $N(A)$: n\'{u}mero de elementos do conjunto $A$.
       \end{quote}
 \item \textcolor{black}{Princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o}:
       \begin{quote}
       \[N(A\cup B) = N(A) + N(B) - N(A\cap B)\mbox{.}\]
       \end{quote}
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Um exemplo}

\begin{itemize}
 \item N\'{u}mero de maneiras de selecionar um \'{a}s ou uma carta vermelha de um
       baralho convencional:

       \begin{itemize}       
        \item Sendo
              \begin{itemize}
               \item $A$: conjunto dos ases;
               \item $V$: conjunto das cartas vermelhas;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(A\cup V)$.
        \item Pelo princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o, tem-se:
              \begin{quote}
               $N(A\cup V)$\parbox[t]{12.7cm}{$=N(A)+N(V)-N(A\cap V)$ \\
                       $=4+26-2=28$.}
              \end{quote}
       \end{itemize} 
\end{itemize}

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

\newslide{Princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o para 3 conjuntos}

\[\begin{array}{ll}
  N(A\cup B\cup C) = &N(A) + N(B) + N(C) \\
                     &- N(A\cap B) - N(A\cap C) - N(B\cap C) \\
                     &+ N(A\cap B\cap C)\mbox{.}
  \end{array}\]

\begin{itemize}
\item Uma identidade importante:

\[N(\overline{A_1}\cap\cdots\cap\overline{A_n})=N(U)-N(A_1\cup\cdots\cup A_n)\mbox{.}\]

$U$ \'{e} o \textcolor{black}{conjunto universo}.   
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Um exemplo}

\begin{itemize}
 \item N\'{u}mero de sequ\^{e}ncias tern\'{a}rias de $n$ d\'{\i}gitos com no m\'{\i}nimo um 0, um 1 e
       um 2:

       \begin{itemize}       
        \item Sendo (para $i= 0, 1, 2$)
              \begin{itemize}
               \item $S_i$: conjunto das sequ\^{e}ncias sem o d\'{\i}gito $i$;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(\overline{S_0}\cap \overline{S_1}\cap \overline{S_2})=
              N(U)-N(S_0\cup S_1\cup S_2)$.
        \item Como
              \[\begin{array}{l}
               N(U)=3^n\mbox{,} \\
               N(S_i)=2^n \mbox{ para } i=0,1,2, \\
               N(S_i\cap S_j)=1 \mbox{ para } i\not= j, \\
               N(S_0\cap S_1\cap S_2)=0,
              \end{array}\]
              tem-se:
              \[\begin{array}{ll}
                N(U)-N(S_0\cup S_1\cup S_2)&=3^n-(3.2^n-3.1+0) \\
                                           &=3^n-3.2^n+3\mbox{.}
              \end{array}\]
       \end{itemize} 
\end{itemize}

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

\newslide{Notação}


\[\begin{array}{ll}
 \mbox{\underline{Sejam}:} \ & S_1=\sum_{i=1}^{n}N(A_i) \\
          & S_2=\sum_{i\not=j}N(A_i\cap A_j) \\
          & \vdots \\
          & S_k=\sum_{i_1\not=i_2\not=\cdots\not= i_k}N(A_{i_1}\cap A_{i_2}\cap
                 \ldots\cap A_{i_k}) \\
          & \vdots \\
          & S_n=N(A_1\cap A_2\cap\ldots\cap A_n)
\end{array}\]

\vspace*{12mm}
\hspace*{8cm} \framebox{ $S_k$ tem $C(n,k)$ termos}

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

\newslide{Princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o/geral}
\hypertarget{principio-inclusao-exclusao-8}{}

\begin{description}
 \item[Princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o:] \ 
 
       \vspace*{3mm}
       $N(\bigcup_{i=1}^nA_i)=S_1-S_2+\cdots+(-1)^{i+1}S_i+\cdots+(-1)^{n+1}S_n$

\vspace*{3mm}
 \item[Prova:] \
 
       Se um elemento ocorre em exatamente $r$ dos $A_i$'s, ent\~{a}o ele \'{e} contado
       $C(r,1)-C(r,2)+C(r,3)-\cdots+(-1)^{r+1}C(r,r)$ vezes. Isto \'{e} o mesmo que
       $1-\sum_{k=0}^rC(r,k)(-1)^k$. Pelo Teorema Binomial, isto d\'{a}
       $1-(1-1)^r=1$.
\end{description}

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

\section{ALGUNS EXEMPLOS DE USO DO PRINCÍPIO DA INCLUSÃO E EXCLUSÃO}
\hypertarget{exemplos-1}{}

\newslide{Exemplo de Uso do Princ\'{\i}pio da Inclus\~{a}o e Exclus\~{a}o}

\begin{itemize}
 \item N\'{u}mero de m\~{a}os de 13 cartas que n\~{a}o cont\^{e}m nenhuma carta de algum naipe:
       
       \begin{itemize}       
        \item Sendo
              \begin{itemize}
               \item $A_o$: conjunto das m\~{a}os sem ouros;
               \item $A_c$: conjunto das m\~{a}os sem copas;
               \item $A_e$: conjunto das m\~{a}os sem espadas;
               \item $A_p$: conjunto das m\~{a}os sem paus;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(A_o\cup A_c\cup A_e\cup A_p)$.
              
%--------------------------------------------------------------------------------------------

\newslide{Exemplo (continuação)}
              
        \item Pelo princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o, tem-se:
              \[N(A_o\cup A_c\cup A_e\cup A_p)=S_1-S_2+S_3-S_4\mbox{.}\]
              Como
              \[\begin{array}{l}
               S_1=C(4,1)C(39,13)\mbox{,} \\
               S_2=C(4,2)C(26,13)\mbox{,} \\
               S_3=C(4,3)C(13,13)\mbox{,} \\
               S_4=C(4,4)0\mbox{,} \\
              \end{array}\]
              tem-se:
              \[N(A_o\cup A_c\cup A_e\cup A_p)=4C(39,13)-6C(26,13)+4\mbox{.}\]
       \end{itemize} 

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

\newslide{Exemplo de Uso do Princ\'{\i}pio da Inclus\~{a}o e Exclus\~{a}o}

 \item N\'{u}mero de arranjos dos d\'{\i}gitos 0 a 9 que cont\^{e}m pelo menos uma das
       sequ\^{e}ncias 289, 234 ou 487:
       
       \begin{itemize}       
        \item Sendo
              \begin{itemize}
               \item $A_{289}$: conjunto dos arranjos com 289, etc.;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(A_{289}\cup A_{234}\cup A_{487})$.
        \item Como
              \[\begin{array}{l}
               N(A_{289})=N(A_{234})=N(A_{487})=8!\mbox{,} \\
               N(A_{289}\cap A_{234})=0\mbox{,} \\
               N(A_{289}\cap A_{487})=0\mbox{,} \\
               N(A_{234}\cap A_{487})=6!\mbox{,} \\
               N(A_{289}\cap A_{234}\cap A_{487})=0\mbox{,} \\
              \end{array}\]
              tem-se: \[N(A_{289}\cup A_{234}\cup A_{487})=3.8!-6!\]
       \end{itemize}

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

\newslide{Exemplo de Uso do Princ\'{\i}pio da Inclus\~{a}o e Exclus\~{a}o}

 \item N\'{u}mero de distribui\c{c}\~{o}es de $r$ bolas distintas em $n$ caixas distintas,
       sem que nenhuma caixa fique vazia ($r\geq n$).
       
       \begin{itemize}
        \item Sendo (para $i=1, 2, \ldots, n$)
              \begin{itemize}
               \item $V_i$: conjunto de distribui\c{c}\~{o}es com a caixa $i$ vazia;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(\bar{V_1}\cap \bar{V_2}\cap \cdots\cap\bar{V_n})$,
              ou seja, \[N(U)-N(V_1\cup V_2\cup \cdots\cup V_n)\mbox{.}\]
        \item Como
              \[\begin{array}{l}
               N(U)=n^r\mbox{,} \\
               N(S_k)=C(n,k)(n-k)^r \mbox{ para } k=1,2,\ldots, n, \\
              \end{array}\]
              tem-se:
              \[\begin{array}{ll}
                N(U)-N(\bigcup_{i=1}^{n}V_i)&=n^r-
                                          \sum_{k=1}^n(-1)^{k+1}C(n,k)(n-k)^r \\
                                   &=\sum_{k=0}^n(-1)^kC(n,k)(n-k)^r\mbox{.}
              \end{array}\]
       \end{itemize}

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

\newslide{Exemplo de Uso do Princ\'{\i}pio da Inclus\~{a}o e Exclus\~{a}o}

 \item (O problema dos dados de Galileu) N\'{u}mero de solu\c{c}\~{o}es para
       $x_1+x_2+x_3=10$, com $1\leq x_i\leq 6$: o mesmo que o n\'{u}mero de
       solu\c{c}\~{o}es para $x_1+x_2+x_3=7$, com $0\leq x_i\leq 5$.
       
       \begin{itemize}
        \item Sendo 
              \begin{itemize}
               \item $A_1$: conjunto de solu\c{c}\~{o}es com $x_1\geq 6$, $x_2\geq 0$,
                            $x_3\geq 0$;
                            
                            (ou seja, conjunto de solu\c{c}\~{o}es para $x_1+x_2+x_3=1$,
                            com $x_i\geq 0$)
               \item $A_2$: conjunto de solu\c{c}\~{o}es com $x_1\geq 0$, $x_2\geq 6$,
                            $x_3\geq 0$;
               \item $A_3$: conjunto de solu\c{c}\~{o}es com $x_1\geq 0$, $x_2\geq 0$,
                            $x_3\geq 6$;
               \item $U$: conjunto de solu\c{c}\~{o}es com $x_1\geq 0$, $x_2\geq 0$,
                            $x_3\geq 0$;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(\bar{A_1}\cap \bar{A_2}\cap \bar{A_3})$,
              ou seja, \[N(U)-N(A_1\cup A_2\cup A_3)\mbox{.}\]

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

\newslide{Exemplo (continuação)}
\hypertarget{exemplos-6}{}              
              
        \item Como
              \[\begin{array}{l}
               N(U)=C(3-1+7,7)\mbox{,} \\
               N(A_i)=C(3-1+1,1) \mbox{ para } i=1,2,3, \\
               N(A_1\cap A_2)=N(A_1\cap A_3)=N(A_2\cap A_3)=0\mbox{,}
              \end{array}\]
              tem-se:
              \[\begin{array}{ll}
                N(U)-N(A_1\cup A_2\cup A_3)&=C(9,7)-3C(3,1) \\
                                   &=36-9=27\mbox{.}
              \end{array}\]
       \end{itemize}

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

%\newslide{Exemplo de Uso do Princ\'{\i}pio da Inclus\~{a}o e Exclus\~{a}o}

% \item N\'{u}mero de sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos com um n\'{u}mero par de 0's e
%       um n\'{u}mero par de 1's:
       
%       Se $n$ \'{e} \'{\i}mpar: 0 sequ\^{e}ncias. Seja $n$ par.
       
%       \begin{itemize}
%        \item Sendo 
%              \begin{itemize}
%               \item $A_i$: conjunto das sequ\^{e}ncias com $2i$ 0's e $n-2i$ 1's;
%              \end{itemize}
%              a solu\c{c}\~{a}o \'{e} \[N(A_1\cup A_2\cup \cdots \cup A_{n/2})\mbox{.}\]
%        \item Como
%              \[\begin{array}{l}
%               N(A_i)=C(n,2i) \mbox{ para } i=1,2,\dots,n/2, \\
%               A_1, A_2, \ldots A_{n/2} \mbox{ s\~{a}o disjuntos,}
%              \end{array}\]

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

%\newslide{Exemplo (continuação)}

%              tem-se:
%              \[\begin{array}{ll}
%                N(\bigcup_{k=1}^{n/2}A_k)&=\sum_{k=1}^{n/2}C(n,2k) \\
%                                   &=C(n,0)+C(n,2)+\cdots+C(n,n) \\
%                                   &= \left\{ \begin{array}{ll}
%                                              1 & \mbox{ se $n=0$} \\
%                                              2^{n-1} & \mbox{ se $n>0$.}
%                                             \end{array} \right.
%              \end{array}\]
%       \end{itemize}

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

\newslide{Exemplo de Uso do Princ\'{\i}pio da Inclus\~{a}o e Exclus\~{a}o}

 \item (O problema das permuta\c{c}\~{o}es ca\'{o}ticas) N\'{u}mero de permuta\c{c}\~{o}es do conjunto
       $\{x_1,x_2,\ldots,x_n\}$, em que nenhum $x_i$ fique na $i$-\'{e}sima posi\c{c}\~{a}o:
       
       \begin{itemize}
        \item Sendo 
              \begin{itemize}
               \item $A_i$: conjunto das permuta\c{c}\~{o}es com $x_i$ na $i$-\'{e}sima
                            posi\c{c}\~{a}o, para $i=1,2,\ldots,n$;
               \item $U$: conjunto de todas as permuta\c{c}\~{o}es;
              \end{itemize}
              a solu\c{c}\~{a}o \'{e} $N(\bar{A_1}\cap \bar{A_2}\cap \cdots\cap\bar{A_n})$,
              ou seja, \[N(U)-N(A_1\cup A_2\cup \cdots\cup A_n)\mbox{.}\]
              
%--------------------------------------------------------------------------------------------

\newslide{Permuta\c{c}\~{o}es ca\'{o}ticas (continuação)}
              
        \item Como
              \[\begin{array}{l}
               N(U)=n!\mbox{,} \\
               S_k=C(n,k)N(A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_k})
                \mbox{ para } k=1,2,\ldots,n, \\
               \ \ \ \ \mbox{ e } N(A_{i_1}\cap A_{i_2}\cap \cdots\cap A_{i_k})=(n-k)! 
              \end{array}\]
              tem-se:
              \[\begin{array}{ll}
                D_n&=N(U)-N(\bigcup_{i=1}^{n}A_i) \\
                   &=n!-\sum_{k=1}^{n}(-1)^{k+1}C(n,k)(n-k)! \\
                   &=n!(\frac{1}{2!}-\frac{1}{3!}+\cdots+
                        \frac{(-1)^n}{n!})\mbox{.}
              \end{array}\]
              
%------------------------------------------------------------------------------------------

\newslide{Permutações caóticas (continuação)}

        \item {\it Observa\c{c}\~{o}es\/}:
              \begin{itemize}
               \item $e^x=1+x+x^2/2!+x^3/3!+\cdots$ (converg\^{e}ncia r\'{a}pida)
               
                     Logo, $D_n\approx e^{-1}n!$.
               \item Probabilidade de se encontrar uma permuta\c{c}\~{a}o ca\'{o}tica a
                     partir da gera\c{c}\~{a}o aleat\'{o}ria de uma permuta\c{c}\~{a}o:
                     \[D_n/n!\approx e^{-1}\approx 0,37\mbox{.}\]
              \end{itemize}
       \end{itemize}
\end{itemize}

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

\newslide{Permutações caóticas (continuação)}

        \begin{tabular}{rrrr}
         \hspace*{4cm} &    $n$ & $e^{-1}n!$\ \ \ \  & $D_n$ \  \\
          &    1  & 0.367\ldots      &       0 \\
          &   2  & 0.735\ldots       &       1 \\
          &   3  & 2.207\ldots       &       2 \\
          &  4  & 8.829\ldots        &       9 \\
          &    5  & 44.145\ldots     &      44 \\
          &   6  & 264.873\ldots     &     265 \\
          &  7  & 1854.112\ldots     &    1854 \\
          &   8  & 14832.899\ldots   &   14833 \\
          &  9  & 133496.091\ldots   &  133496 \\
          &  10  & \ \ \ 1334960.916\ldots & 1334961
        \end{tabular}

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

\defskiptarget{capitulo5}

\lastpage 

\end{document}