\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Matem\'{a}tica Discreta}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2000
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Quarta Lista de Exerc\'{\i}cios}: {\bf Combinat\'{o}ria Elementar}

\vspace*{2mm}
\noindent {\bf Data de Entrega:} 07/12/00.

\vspace*{2mm}
\noindent {\bf Importante:} Em todas as quest\~oes deve-se indicar o {\em processo\/} usado para
determinar cada solu\c c\~ao. {\em O processo \'e mais importante do que a solu\c c\~ao.\/}
``Continhas'' s\~ao desnecess\'arias.

\begin{enumerate}
 \item Duas cartas de baralho s\~ao distribu\'{\i}das para uma pessoa. Para cada $k= 0, 1, 2$
       determine o n\'umero de distribui\c c\~oes com exatamente $k$ ases.

 \item Quantas vezes ocorre a subsequ\^encia 13 quando se lista os inteiros de 1 a 1000?

 \item Quantas maneiras existem de distribuir um \'as, depois uma carta vermelha e, em seguida,
       uma carta preta? E se, adicionalmente, n\~ao aparece nenhum par (duas cartas de
       mesmo n\'umero)?

 \item De quantas maneiras se pode arranjar as letras em EMPILHAR:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item no total?
        \item com todas as vogais consecutivas?
        \item com M antes de (n\~ao necessariamente encostado em) P? 
        \item com exatamente duas letras entre M e P? 
       \end{list}

 \item Quantas regi\~oes quadradas existem em um tabuleiro de xadrez? (Uma regi\~ao quadrada
       pode ter lados de tamanho 1 a 8.)

 \item Uma moeda \'e lan\c cada 50 vezes e produz 20 caras. De quantas maneiras isto pode
       ocorrer?

 \item De quantas maneiras se pode colocar 5 homens e 5 mulheres sentados lado a lado, de
       forma que homens n\~ao fiquem juntos?

 \item Um aluno tem 25 livros, mas s\'o h\'a espa\c co para 10 deles em certa prateleira.
       De quantas formas ele pode encher a prateleira com 10 dos 25 livros?

 \item Dez pessoas s\~ao selecionadas para compor um time de {\em softball\/}, a partir de
       um grupo de 15 homens e 8 mulheres. Quantos times s\~ao poss\'{\i}veis com
       exatamente 4 mulheres? E com no m\'{\i}nimo 4 mulheres? E com no m\'{\i}nimo tantas
       mulheres quantos homens?

 \item Seis s\'{\i}mbolos distintos devem ser transmitidos atrav\'{e}s de um
       canal de comunica\c{c}\~{a}o. Um total de 12 brancos devem ser inseridos
       entre os s\'{\i}mbolos, com pelo menos 2 brancos entre cada par de
       s\'{\i}mbolos. De quantas maneiras os s\'{\i}mbolos e brancos podem ser
       arranjados?

 \item De quantas maneiras se pode distribuir $n$ objetos distintos em $n$
       caixas distintas, de forma que nenhuma caixa fique vazia? E de forma que
       exatamente uma caixa fique vazia?

 \item Quantas maneiras existem de distribuir $r$ bolas id\^{e}nticas em $n$
       caixas distintas, ficando exatamente $v$ caixas vazias?

 \item Um {\it closet\/} cont\'{e}m 6 pares de sapatos. Quantas sele\c c\~oes e
       quantos arranjos existem de 4 destes sapatos, caso:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item nenhum par completo seja escolhido?
        \item 2 pares completos sejam escolhidos?
       \end{list}

 \item Qual a probabilidade de que 20 pessoas escolhidas aleatoriamente fa\c cam anivers\'ario
       em meses diferentes? E que fa\c cam anivers\'ario no mesmo m\^es? Assuma 365 dias no ano.

 \item $n$ pauzinhos, cada um de uma cor, s\~ao quebrados em duas partes, uma menor e outra
       menor. Quantas maneiras h\'a de combinar os $2n$ peda\c cos em $n$ pares de forma que
       cada par consista de um peda\c co menor e um maior?

 \item Quantas sequ\^{e}ncias tern\'{a}rias de 30 d\'{\i}gitos t\^{e}m exatamente dez 1's?

 \item Cartas s\~ao colocadas uma a uma sobre uma mesa. De quantas maneiras pode acontecer
       do $k$-\'esimo \'as ser a $r$-\'esima carta a ser colocada sobre a mesa?

 \item Quantos arranjos das letras de EMPERRAMENTO n\~{a}o t\^em vogais consecutivas?

 \item Escreva problemas equivalentes de solu\c c\~ao de equa\c c\~oes inteiras para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item N\'umero de maneiras de distribuir $r$ bolas id\^enticas em $n$ caixas distintas,
              de forma que nenhuma caixa contenha mais de 2 bolas.
        \item N\'umero de subconjuntos de 3 elementos tomados de $\{a,b,c,d\}$.
        \item N\'umero de maneiras de distribuir $r$ bolas id\^enticas em $n$ caixas distintas,
              de forma que as duas primeiras caixas contenham um total de $p$ bolas.
       \end{list}

 \item Encontrar o n\'{u}mero de solu\c{c}\~{o}es em inteiros n\~{a}o-negativos
       de
       \[x_1+x_2+x_3+x_4+x_5=18\]
       nas quais exatamente 2 inc\'{o}gnitas s\~{a}o nulas.

 \item Encontrar o n\'{u}mero de solu\c{c}\~{o}es em inteiros n\~{a}o-negativos
       para o sistema de equa\c{c}\~{o}es:
       
       \[\left. \begin{array}{l}
                 x_1+x_2+x_3+x_4+x_5\leq 20 \\
                 x_1+x_2+x_3=10
                \end{array} \right\} \mbox{ com } x_k\geq k \]

 \item Qual \'{e} o coeficiente de $x^9y^3w^6$ em $(x+y+z+w)^{11}$?

 \item Prove que \[\sum_{k=0}^{n}\left(\begin{array}{c} n \\
                                        k
                                       \end{array} \right) 2^k=3^n\mbox{.}\]
       {\em Dica\/}: use o Teorema Binomial.

 \item Derive a identidade $C(2n,n)=\sum_{k=0}^{n}C(n,k)^2$ a partir do
       Teorema Binomial.

 \item Prove, usando racioc\'{\i}nio combinat\'{o}rio:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(2n,n)=\sum_{k=0}^{n}C(n,k)^2$
        \item $C(m+n,r)=\sum_{k=0}^{r}C(m,k)C(n,r-k)$
       \end{list}
\end{enumerate}
 
\end{document}
