\documentclass[11pt,a4paper]{article}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\usepackage{comment}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
{\it Matemática Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \hfill www.dcc.ufmg.br/\verb+~+nvieira\\
\underline{Terceira Lista de Exercícios}/Soluções

\vspace*{2mm}
\noindent {\bf Relações de Recorrência}
 
\vspace*{2mm}

\begin{enumerate}
 \item {\footnotesize Um banco paga 4,5\% de juros por ano. Além disso, ele paga um bônus de \$100 reais no final de
       cada ano (após pagos os juros). Encontre uma relação de recorrência para o total pago após $n$ anos, se o
			 investimento inicial for de \$200 reais.}
       %Townsend 4.1/9

       \textit{Solução}:
       
       $a_0=200$; \\
       $a_n=1,045a_{n-1}+100$ para $n\geq 1$.

 \item {\footnotesize Encontre uma relação de recorrência para o número de sequências quaternárias de $n$ dígitos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item sem 1's consecutivos.
        \item com número par de 0's.
       \end{list}}
       %Townsend 4.1/10

       \textit{Solução}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_1=4$; \\
              $a_n=3a_{n-1}+3a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$; \\
              $a_n=3a_{n-1}+(4^{n-1}-a_{n-1})=2a_{n-1}+4^{n-1}$ para $n\geq 1$.
       \end{list}

 \item {\footnotesize Encontre uma relação de recorrência para o número de maneiras de colocar idênticos Toyotas,
       Cadillacs e Mercedes em um espaço cujo tamanho é $n$ ``unidades'', sabendo que Mercedes e Cadillacs ocupam
       2 unidades cada um, e que Toyotas ocupam uma unidade cada um.}
       %Townsend 4.1/11

       \textit{Solução}:

       $a_1=1$, $a_2=3$; \\
       $a_n=a_{n-1}+2a_{n-2}$ para $n\geq 2$.
       
 \item {\footnotesize Considere $n$ quadrados dispostos lado a lado, como mostra a figura:
       \begin{center} 
       \begin{picture}(175,25)
        \put(50,0){\line(1,0){30}}
        \put(50,15){\line(1,0){30}}
        \put(50,0){\line(0,1){15}}
        \put(65,0){\line(0,1){15}}
        \put(80,0){\line(0,1){15}}
        \put(95,8){\makebox(0,0){$\cdots$}}
        \put(110,0){\line(1,0){15}}
        \put(110,15){\line(1,0){15}}
        \put(110,0){\line(0,1){15}}
        \put(125,0){\line(0,1){15}}
        \put(57,17){\makebox(0,0)[b]{$1$}}
        \put(72,17){\makebox(0,0)[b]{$2$}}
        \put(117,17){\makebox(0,0)[b]{$n$}}
       \end{picture}
       \end{center}
       Seja $a_n = $ {\it número de maneiras de colorir os quadrados, de forma que não fiquem dois quadrados vermelhos
			 adjacentes\/}. Encontre uma relação de recorrência para $a_n$, para cada um dos seguintes casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada quadrado pode ser colorido de vermelho ou de verde.
        \item Cada quadrado pode ser colorido de vermelho, de verde, ou de amarelo.
        \item Generalize para $k$ cores (incluindo vermelho).
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_1=2$; \\
              $a_n=a_{n-1}+a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, $a_1=3$; \\
              $a_n=2a_{n-1}+2a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, $a_1=k$; \\
              $a_n=(k-1)a_{n-1}+(k-1)a_{n-2}$ para $n\geq 2$.
       \end{list}

 \item {\footnotesize Encontre uma relação de recorrência para o número de maneiras de subir $n$ degraus, se em
       cada estágio pudermos avançar 1, 3 ou 5 degraus de uma vez.}
       %Townsend 4.1/12

       \textit{Solução}:

       $a_0=1$, $a_1=1$, $a_2=1$, $a_3=2$, $a_4=3$; \\
       $a_n=a_{n-1}+a_{n-3}+a_{n-5}$ para $n\geq 5$.

 \item {\footnotesize Seja o conjunto de dígitos e letras $X=\{1,2,3,4,a,b,c,d,e,f,g\}$. Encontre uma relação de
       recorrência para o número de sequências de $n$ símbolos de $X$, para cada uma das seguintes
			 situações:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item não há letras consecutivas (idênticas ou não).
        \item não há dígito seguido de letra.
        \item o número de letras é par.
       \end{list}}

       \textit{Solução\/}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item não há letras consecutivas (idênticas ou não).
        
              $a_0=1$, $a_1=11$, $a_n=4a_{n-1}+28a_{n-2} \; (n\geq 2)$
        
        \item não há dígito seguido de letra.
        
              $a_0=1$, $a_1=11$, $a_n=4a_{n-1}+49a_{n-2} \; (n\geq 2)$
        
        \item o número de letras é par.
        
              $a_0=1$, $a_n=4a_{n-1}+7(11^{n-1}-a_{n-1}) \; (n\geq 1)$, ou seja,
              
              $a_0=1$, $a_n=7.11^{n-1}-3a_{n-1} \; (n\geq 1)$
        
       \end{list}

 \item {\footnotesize Encontre uma relação de recorrência para o número de sequências ternárias de $n$ dígitos sem a
       subsequência 012.}
%      EX. 7, pag. 283. Tucker

       \textit{Solução}:

       $a_0=1$, $a_1=3$, $a_2=9$;\\
       $a_n=2a_{n-1}+(a_{n-1}-a_{n-3})=3a_{n-1}-a_{n-3}$ para $n\geq 3$.

       Obs: supondo que $a_{n-1}$ seqs de $n-1$ dígitos não têm 012: $a_{n-1}$ seqs de $n$ dígitos terminam em 2 e podem ter
       012 apenas como \underline{sufixo}; logo, $a_{n-1}-a_{n-3}$ seqs de $n$ dígitos não têm 012 ($a_{n-3}$ é o número de
			 seqs de $n-1$ dígitos sem 012, terminadas em 01).

 \item {\footnotesize Encontre uma relação de recorrência para o número de regiões criadas por $n$ linhas sobre uma folha
       de papel se $k$ das linhas são paralelas e cada uma das outras $n-k$ intersepta todas as linhas (e não mais de 2
			 linhas se interseptam em um único ponto).}
%      Ex. 13(a), pag. 289. Tucker

       \textit{Solução}:

       $a_k=k+1$; \\
       $a_n=a_{n-1}+n$ para $n\geq k+1$.

\begin{comment}
 \item {\footnotesize Encontre uma relação de recorrência para o número de sequências de $r$ elementos tomados de um
       conjunto de $n$ elementos.}
       %Townsend 4.1/20

       \textit{Solução}:

       $S_{n,0}=1$; \\
       $S_{n,r}=nS_{n,r-1}$ para $n\geq 1$.

 \item {\footnotesize Encontre uma relação de recorrência para o número de multiconjuntos de $r$ elementos tomados de um
       conjunto de $n$ elementos.}
       %Townsend 4.1/20

       \textit{Solução}:

       $M_{n,1}=n$, $M_{1,r}=1$; \\
       $M_{n,r}=M_{n-1,r}+M_{n,r-1}$ para $r>1$, $n>1$.

 \item {\footnotesize Encontre uma relação de recorrência para o número de decomposições de um conjunto de $n$
       elementos em exatamente $k$ partes (conjuntos não vazios disjuntos).}
       %Townsend 4.1/23

       \textit{Solução}:

       $P_{n,1}=P_{n,n}=1$; \\
       $P_{n,k}=P_{n-1,k-1}+ kP_{n-1,k}$ para $1<k<n$.

 \item {\footnotesize Sejam $n$ caixas distintas dispostas em uma fila. Encontre uma relação de recorrência para o
       número de maneiras de distribuir $k$ bolas idênticas de forma que cada caixa receba no máximo 1 bola, e que não
       haja caixas consecutivas com bolas.}
       %Townsend 4.1/24

       \textit{Solução}:

       $D_{n,0}=D_{1,1}=1$, $D_{n,n}=0$ para $n>1$; \\
       $D_{n,k}=D_{n-1,k}+ D_{n-2,k-1}$ para $0<k<n$.

\end{comment}

 \item {\footnotesize Mostre que $C_1(1+\sqrt{5})^n+C_2(1-\sqrt{5})^n$ é a solução geral para $a_n-2a_{n-1}-4a_{n-2}=0$.}

       {\it Solução\/}:

       \begin{tabbing}\small
        xxx\= \kill
        $C_1(1+\sqrt{5})^n+C_2(1-\sqrt{5})^n-2[C_1(1+\sqrt{5})^{n-1}+C_2(1-\sqrt{5})^{n-1}]$ \\
           \>\hspace*{1cm}$-4[C_1(1+\sqrt{5})^{n-2}+C_2(1-\sqrt{5})^{n-2}]$ \\
           \>$=[C_1(1+\sqrt{5})^n-2C_1(1+\sqrt{5})^{n-1}-4C_1(1+\sqrt{5})^{n-2}]$ \\
           \>\hspace*{1cm}$+[C_2(1-\sqrt{5})^n-2C_2(1-\sqrt{5})^{n-1}-4C_2(1-\sqrt{5})^{n-2}]$ \\
           \>$=C_1(1+\sqrt{5})^{n-2}[(1+\sqrt{5})^2-2(1+\sqrt{5})-4]$ \\
           \>\hspace*{1cm}$+C_2(1-\sqrt{5})^{n-2}[(1-\sqrt{5})^2-2(1-\sqrt{5})-4]$ \\
           \>$=C_1(1+\sqrt{5})^{n-2}[1+2\sqrt{5}+5-2-2\sqrt{5}-4]$ \\
           \>\hspace*{1cm}$+C_2(1-\sqrt{5})^{n-2}[1-2\sqrt{5}+5-2+2\sqrt{5}-4]$ \\
           \>$=C_1(1+\sqrt{5})^{n-2}.0+C_2(1-\sqrt{5})^{n-2}.0$ \\
           \>$=0$.
       \end{tabbing}
 \item {\footnotesize Resolva as seguintes relações de recorrência:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=0$, $a_2=2$, $a_n+5a_{n-1}+6a_{n-2}=0$ para $n\geq 3$.
        \item $a_0=1$, $a_1=2$, $a_n-2a_{n-1}-a_{n-2}=0$ para $n\geq 2$.
        \item $a_1=2$, $a_2=6$, $a_n-4a_{n-1}+4a_{n-2}=0$ para $n\geq 3$.
        \item $a_1=5$, $a_2=-5$, $a_n+6a_{n-1}+9a_{n-2}=0$ para $n\geq 3$.
       \end{list}}

       {\it Solução\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Equação característica: $x^2+5x+6=0$. As raízes são $x_1=-2$, $x_2=-3$. Logo a solução geral é
				      $C_1(-2)^n+C_2(-3)^n$. Para satisfazer as condições iniciais deve-se ter $C_1(-2)^1+C_2(-3)^1=0$
							e $C_1(-2)^2+C_2(-3)^2=2$, ou seja:
              \begin{enumerate}
               \item[\ ] $-2C_1-3C_2=0$
               \item[\ ] $4C_1+9C_2=2$
              \end{enumerate}
              Resolvendo esse sistema, obtém-se $C_1=-1$ e $C_2=2/3$. Logo, a solução da RR é $a_n=(-1)(-2)^n+(2/3)(-3)^n$.
        \item Equação característica: $x^2-2x-1=0$. Raízes: $x_1=1+\sqrt{2}$ e $x_2=1-\sqrt{2}$. Logo a solução geral é
				      $C_1(1+\sqrt{2})^n+C_2(1-\sqrt{2})^n$. Para satisfazer as condições iniciais deve-se ter
							$C_1(1+\sqrt{2})^0+C_2(1-\sqrt{2})^0=1$ e $C_1(1+\sqrt{2})^1+C_2(1-\sqrt{2})^1=2$, ou seja:
              \begin{enumerate}
               \item[\ ] $C_1+C_2=1$
               \item[\ ] $(1+\sqrt{2})C_1+(1-\sqrt{2})C_2=2$
              \end{enumerate}
              Assim, obtém-se $C_1=(1+\sqrt{2})/2\sqrt{2}$ e $C_2=-(1-\sqrt{2})/2\sqrt{2}$. Logo, a solução da RR
              é $[(1+\sqrt{2})^{n+1}-(1-\sqrt{2})^{n+1}]/2\sqrt{2}$.
        \item Solução da parte recorrente: $C_12^n+C_2n2^n$.
        \item Solução da parte recorrente: $C_1(-3)^n+C_2n(-3)^n$.
       \end{list}

 \item {\footnotesize Resolva as seguintes relações de recorrência:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_n-2a_{n-1}=n^2$ para $n\geq 1$.
        \item $a_0=1$, $a_1=-1$, $a_n-3a_{n-1}+2a_{n-2}=n$ para $n\geq 2$.
        \item $a_0=1$, $a_1=0$, $a_n-2a_{n-1}+a_{n-2}=2$ para $n\geq 2$.
        \item $a_0=0$, $a_n+3a_{n-1}=2^n$ para $n\geq 1$.
        \item $a_1=0$, $a_2=0$, $a_n-4a_{n-1}+4a_{n-2}=(-2)^n$ para $n\geq 3$.
        \item $a_0=1$, $a_n+2a_{n-1}=2^n-n^2$ para $n\geq 1$.
        \item $a_0=2$, $a_n-2a_{n-1}=2^{n-1}$ para $n\geq 1$.
       \end{list}}

       {\it Solução\/}:
       
       Soluções das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $g(n)=C_12^n$; $p(n)=-(n^2+4n+6)$.
        \item $g(n)=C_1+C_22^n$; $p(n)=-(n^2+5n)/2$.
        \item $g(n)=C_1+C_2n$; $p(n)=n^2$.
        \item $g(n)=C_1(-3)^n$; $p(n)=2^{n+1}/5$.
        \item $g(n)=C_12^n+C_2n2^n$; $p(n)=(-2)^{n-2}$.
        \item $g(n)=C_1(-2)^n$; $p_1(n)=-(9n^2+12n+2)/27$, $p_2(n)=2^{n-1}$.
        \item $g(n)=C_12^n$; $p(n)=n2^{n-1}$.
       \end{list}

 \item {\footnotesize Resolva as seguintes relações de recorrência:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=1$, $a_n^3=2a_{n-1}^3+1$ para $n\geq 2$. (Sugestão: faça $b_n=a_n^3$.)
        \item $a_0=2$, $a_n=na_{n-1}+n!$ para $n\geq 1$.
       \end{list}}

       {\it Solução\/}:
       
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sqrt[3]{2^n-1}$.
        \item $(n+2)n!$.
       \end{list}

 \item {\footnotesize Usando relações de recorrência, avalie as seguintes somas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $1+2+4+\cdots+2^n$.
        \item $1^2+2^2+\cdots+n^2$.
        \item $1\times 2+2\times 3+\cdots+n(n+1)$.
       \end{list}}

       {\it Solução\/}:
       
       Basta resolver as relações de recorrência:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$; \\
              $a_n=a_{n-1}+2^n$.
        \item $a_0=0$; \\
              $a_n=a_{n-1}+n^2$.
        \item $a_0=0$; \\
              $a_n=a_{n-1}+n^2+n$.
       \end{list}
\end{enumerate}

\vspace*{2mm}
\noindent {\bf Princípio de inclusão e exclusão}
 
\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Numa cidade em que são publicados os jornais A, B e C, foram obtidos os seguintes resultados
       numa pesquisa: 20\% da população lê o jornal A, 16\% o jornal B, 14\% o jornal C; 8\% lê A e B, 5\% A e C e 4\% B
       e C. Somente 2\% lê os três jornais. Qual a porcentagem da população que não lê nenhum destes três jornais?}

       \textit{Solução}:

       Sejam, considerando um universo, $U$, de 100 leitores:
       \begin{itemize}
        \item $A$: conjunto dos leitores do jornal $A$;
        \item $B$: conjunto dos leitores do jornal $B$; e
        \item $C$: conjunto dos leitores do jornal $C$.
       \end{itemize}
       São dados: $N(A)=20$, $N(B)=16$, $N(C)=14$, $N(A\cap B)=8$, $N(A\cap C)=5$, $N(B\cap C)=4$ e $N(A\cap B\cap C)=2$.

       $N(\overline{A}\cap\overline{B}\cap\overline{C})=N(U)-N(A\cup B\cup C)=100-(20+16+14-8-5-4+2)=100-35=65$.
       Logo, 65\% da população não lê nenhum dos três jornais.
         
 \item {\footnotesize Dentre os números de 1 a 1000, inclusive, quantos são divisíveis por 2, 5 ou 12? Quantos não
       são divisíveis por 5, nem por 6, nem por 8?}

       \textit{Solução}:

       Seja, considerando o universo $U$ dos números de 1 a 1000, $D_i$ o conjunto dos números divisíveis por $i$. Então:
       \begin{itemize}
        \item $N(D_2\cup D_5\cup D_{12})=N(D_2\cup D_5)$, pois $D_{12}\subseteq D_2$. E
              $N(D_2\cup D_5)=(1000/2+1000/5-1000/10=500+200-100=600$.
         \item $N(\overline{D_5}\cap\overline{D_6}\cap\overline{D_8})=N(U)-N(D_5\cup D_6\cup D_8)=
               1000-[(1000/5+1000/6+1000/8)-(1000/30+1000/40+1000/24)+1000/120]=
               1000-[(200+166+125)-(33+25+41)+8]=1000-(491-99+8)=1000-406=594$.
       \end{itemize}

 \item {\footnotesize Encontre o número de sequências de tamanho $k$, tomadas do conjunto $\{a_1, a_2, \ldots, a_n\}$,
       em que cada $a_i$ aparece pelo menos uma vez em cada sequência.}

       \textit{Solução}:

       Seja $U$ o conjunto de todas as sequências de $k$ elementos do conjunto $\{a_1, a_2, \ldots, a_n\}$.
       Seja $S_i$ o conjunto das sequências de $k$ elementos em que $a_i$ aparece pelo menos uma
       vez. Pede-se $N(S_1\cap S_2\cap \ldots\cap S_n)$, que é igual a $N(U)-N(\overline{S_1}\cup 
       \overline{S_2}\cup \ldots\cup \overline{S_n})$. Como:
       \begin{itemize}
        \item $N(U)=n^k$;
        \item $N(\overline{S_i})=(n-1)^k$;
        \item $N(\overline{S_i}\cap\overline{S_j})=(n-2)^k$ para $j\not=i$;
        \item etc.
       \end{itemize}
       tem-se:
       \[N(S_1\cap S_2\cap \ldots\cap S_n)=n^k-[{n\choose 1}(n-1)^k-{n\choose 2}(n-2)^k+\cdots+
        (-1)^n{n\choose n}(n-n)^k]\mbox{.}\]
       Logo, $N(S_1\cap S_2\cap \ldots\cap S_n)=\sum_{i=0}^{n}(-1)^iC(n,i)(n-i)^k$.

 \item {\footnotesize Quantos arranjos existem das letras A,A,A,B,B,B,C,C,C, nos quais não
       apareçam 3 letras consecutivas idênticas?}

       \textit{Solução}:

       Sejam $A$ o conjunto dos arranjos em que aparecem 3 As consecutivos, $B$ o conjunto dos arranjos
       em que aparecem 3 Bs consecutivos e $C$ o conjunto dos arranjos em que aparecem 3 Cs consecutivos. 

       Então, $N(\overline{A}\cap\overline{B}\cap\overline{C})=N(U)-N(A\cup B\cup C)$. Logo,
       \[N(\overline{A}\cap\overline{B}\cap\overline{C})=P(9;3,3,3)-({3 \choose 1}P(7;3,3,1)-
         {3 \choose 2}P(5;3,1,1)+{3 \choose 3}P(3;1,1,1))\mbox{.}\]
       Portanto,
       \[N(\overline{A}\cap\overline{B}\cap\overline{C})=\frac{9!}{3!^3}-(3\frac{7!}{3!^2}-
         3\frac{5!}{3!}+3!)\mbox{.}\]

 \item {\footnotesize Usando o princípio da inclusão e exclusão, determine o número de
       soluções inteiras para $x_1+x_2+x_3+x_4=20$, se $-2\leq x_k\leq 10$.}

       \textit{Solução}:

       O número de soluções é o mesmo que o de $y_1+y_2+y_3+y_4=28$ com $0\leq y_i\leq 12$.
       Seja $Y_i$ o conjunto das ``soluções'' desta última em que $y_i\leq 12$, mas $y_j$, para
       $i\not=j$, podendo tomar qualquer valor a partir de 0 (inclusive maior que 12). Então, o
       número de soluções procurado é $N(Y_1\cap Y_2\cap Y_3\cap Y_4)$. Tem-se:
       \[N(Y_1\cap Y_2\cap Y_3\cap Y_4)={4-1+28\choose 28}-[{4\choose 1}{4-1+15\choose 15}-
         {4\choose 2}{4-1+2\choose 2}+0-0]\mbox{.}\]

 \item {\footnotesize Uma companhia de sabão em p\'{o} oferece 3 tipos diferentes de cupons em suas caixas de sabão.
       Cada caixa contém um cupom; se você colecionar pelo menos um de cada tipo, voce ganha um brinde. Qual é a
			 probabilidade de você ganhar um brinde, se você comprar 10 caixas? (A probabilidade é o número de distribuições
			 possíveis em que aparece pelos um cupom de cada tipo, dividido pelo número total de distribuições possíveis.)}

       \textit{Solução}:

       Seja $U$ o conjunto de todas as sequências dos números 1, 2 e 3. Seja $C_i$ o conjunto das sequências dos números
			 1, 2 e 3 em que o número $i$ ocorre pelo menos uma vez. Então a probabilidade pedida é $N(C_1\cap C_2\cap C_3)/N(U)$.
       Como $N(U)=3^{10}$ e
       \[N(C_1\cap C_2\cap C_3)=N(U)-N(\overline{C_1}\cap \overline{C_2}\cap \overline{C_3}=
         3^{10}-[{3\choose 1}2^{10}-{3\choose 2}1^{10}+{3\choose 3}0]=3^{10}-3.2^{10}+3\]
       segue-se que a probabilidade será:
       \[\frac{3^{10}-3.2^{10}+3}{3^{10}}=1-\frac{2^{10}-1}{3^{9}}\mbox{.}\]

 \item {\footnotesize Oito pessoas entram em um elevador, no primeiro andar. O elevador descarrega passageiros em cada
       um dos andares seguintes (no mínimo, um passageiro por andar), até ficar vazio no quinto andar (após descarregar, no
       mínimo, um passageiro). Determine, usando o princípio da inclusão e exclusão, de quantas maneiras diferentes isto
			 pode acontecer.}

       \textit{Solução}:

       Seja $D_i$ o conjunto de distribuições das 8 pessoas em que o $i$-ésimo andar recebe pelo menos uma delas. Pede-se
			 $N(D_2\cap D_3\cap D_4\cap D_5)$. Tem-se:

       \[N(D_2\cap D_3\cap D_4\cap D_5)=4^8-[{4\choose 1}3^8-{4\choose 2}2^8+{4\choose 3}1^8
         -{4\choose 4}0]=4^8-[4.3^8-6.2^8+4]\mbox{.}\]

 \item {\footnotesize Em quantas permutações de 1,2,\ldots, $n$, um número $k$ nunca é imediatamente seguido de $k+1$?}

       \textit{Solução}:

       Seja $P_i$ o conjunto de permutações em que $k$ não é seguido de $k+1$. Pede-se
			 $N(P_1\cap P_2\cap \ldots\cap P_{n-1})$. Tem-se:
       \[N(P_1\cap P_2\cap \ldots\cap P_{n-1})=n!-[{n-1\choose 1}(n-1)!-{n-1\choose 2}(n-2)!+\cdots
         +(-1)^{n}{n-1\choose n-1}0!]\mbox{,}\]
       ou seja,
       \[N(P_1\cap P_2\cap \ldots\cap P_{n-1})=\sum_{k=0}^{n-1}(-1)^k{n-1\choose k}(n-k)!\mbox{.}\]

% \item {\footnotesize De quantos modos 6 casais podem sentar-se ao redor de uma mesa circular
%       de tal forma que marido e mulher não fiquem juntos?}

%       \textit{Solução}:

%       Seja $C_i$ o conjunto de disposições da mesa em que o casal $i$ fique separado.
%       Pede-se $N(C_1\cap C_2\cap \ldots\cap C_6)$. Tem-se:
%       \[N(C_1\cap \ldots\cap C_6)=11!-[{6\choose 1}.2.10!-{6\choose 2}.2^2.9!+{6\choose 3}.2^3.8!
%         -{6\choose 4}.2^4.7!+{6\choose 5}.2^5.6!-{6\choose 6}.2^6.5!]\mbox{.}\]

 \item {\footnotesize Quantas maneiras existem de arranjar as letras em REDIVIDERS de forma que apareça pelo menos
       um par de letras consecutivas idênticas?}

       \textit{Solução}:

       Apenas R, E, D e I podem ser repetidas. Seja R o conjunto dos arranjos em que aparece RR,
       E o conjunto dos arranjos em que aparece EE etc. Pede-se, então, $N(R\cup E\cup D\cup I)$.
       Tem-se:
       \[N(R\cup E\cup D\cup I)={4\choose 1}\frac{9!}{2!^3}-{4\choose 2}\frac{8!}{2!^2}
         +{4\choose 3}\frac{7!}{2!}-{4\choose 4}6!\mbox{.}\]

 \item {\footnotesize De quantas maneiras podemos permutar os dígitos 1, 2, 3, 4, 5, 6, 7, 8, 9
       de forma que nenhum dígito par fique em sua posição natural?}

       \textit{Solução}:

       Seja $A_p$ o conjunto dos arranjos em que o dígito par $p$ aparece em sua posição natural.
       Pede-se, então, $N(\overline{A_2}\cap\overline{A_4}\cap\overline{A_6}\cap\overline{A_8})$
       Tem-se:

       \[N(\overline{A_2}\cap\overline{A_4}\cap\overline{A_6}\cap\overline{A_8})=9!-
         [{4\choose 1}8!-{4\choose 2}7!+{4\choose 3}6!-{4\choose 4}5!]\mbox{.}\]
\end{enumerate}

\end{document}