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

\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} \footnotesize

 \item {\em 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.}

       \underline{\em Resposta\/}: $C(4,k)\times C(48,2-k)$

 \item {\em Quantas vezes ocorre a subsequ\^encia 13 quando se lista os inteiros de 1 a 10000?}

       \underline{\em Solu\c c\~ao\/}: As sequ\^encias t\^em uma das formas: $13xy$, $x13y$ ou $xy13$.
       O n\'umero total de sequ\^encias de cada tipo \'e $10\times 10=100$. Assim, pela regra da soma,
       a resposta \'e: $3\times 100=300$. (Observe que 13 ocorre duas vezes em 1313 e, como deve ser,
       \'e contado duas vezes.)

 \item {\em 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)?}

       \underline{\em Solu\c c\~ao\/}:

       (a.1) Se o \'as \'e preto, tem-se:
           \begin{itemize}
            \item n\'umero de ases: 2;
            \item n\'umero de cartas vermelhas: 26;
            \item n\'umero de cartas pretas (exclu\'{\i}do o \'as preto): 25.
           \end{itemize}
       (a.2) Se o \'as \'e vermelho, tem-se:
           \begin{itemize}
            \item n\'umero de ases: 2;
            \item n\'umero de cartas vermelhas (exclu\'{\i}do o \'as vermelho): 25;
            \item n\'umero de cartas pretas: 26.
           \end{itemize}
       Logo, pelas regras do produto e da soma, o n\'umero total de distribui\c c\~oes poss\'{\i}veis
       \'e $2\times 26\times 25 +2\times 25\times 26=4\times 25\times 26=2600$.

       (b.1) Se o \'as \'e preto, tem-se:
           \begin{itemize}
            \item n\'umero de ases: 2;
            \item n\'umero de cartas vermelhas (exclu\'{\i}dos os 2 ases vermelhos): 24;
            \item n\'umero de cartas pretas (exclu\'{\i}dos os 2 ases pretos e as 2 cartas pretas de
                  mesmo n\'umero que a anterior): 22.
           \end{itemize}
       (b.2) Se o \'as \'e vermelho, tem-se:
           \begin{itemize}
            \item n\'umero de ases: 2;
            \item n\'umero de cartas vermelhas (exclu\'{\i}do os 2 ases vermelhos): 24;
            \item n\'umero de cartas pretas: (exclu\'{\i}dos os 2 ases pretos e as 2 cartas pretas de
                  mesmo n\'umero que a anterior): 22.
           \end{itemize}
       Logo, pelas regras do produto e da soma, o n\'umero total de distribui\c c\~oes poss\'{\i}veis
       \'e $2(2\times 24\times 22)=2112$.

 \item {\em 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}}

       \underline{\em Resposta\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item No total: $8!$.
        \item Com todas as vogais consecutivas: $6!\times 3!$.
        \item Com M antes de (n\~ao necessariamente encostado em) P: $C(8,2)\times 6!$.
        \item Com exatamente duas letras entre M e P: $5\times 2\times 6!$.
              (ou $5!\times 2\times P(6,2)$).
       \end{list}

 \item Uma lanchonete fornece sandu\'{\i}ches com quaisquer dentre 9 ingredientes adicionais,
       al\'em da carne (um sandu\'{\i}che pode ter de zero a todos os 9 ingredientes).
       Quantos pedidos dife\-ren\-tes s\~ao poss\'{\i}veis?

        \underline{\em Resposta\/}: $\sum_{k=0}^9C(9,k)=2^9=512$.

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

       \underline{\em Resposta\/}: $C(50,20)$.

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

       \underline{\em Solu\c c\~ao\/}: Existem $5!$ arranjos das mulheres. Cada homem s\'o pode
       ser colocado antes das 5, entre duas, ou ap\'os as 5 mulheres; assim, tem-se 6 posi\c c\~oes
       para arranjar 5 homens, o que pode ser feito de $P(6,5)$ maneiras (ou ainda, tem-se 6
       escolhas para a posi\c c\~ao que n\~ao ter\'a homem e $5!$ arranjos de homens para as
       5 posi\c c\~oes restantes). Pela regra do produto,
       a resposta \'e ent\~ao $5!\times P(6,5)$.

 \item {\em Um aluno de Computa\c c\~ao tem 7 livros dife\-ren\-tes de linguagens em uma prateleira,
       3 de C e 4 de Java. De quantas formas ele pode dispor os livros na prateleira, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item n\~ao h\'a restri\c c\~oes?
        \item as linguagens devem alternar?
        \item Os livros de C devem ficar todos juntos?
        \item Os livros de C devem ficar todos juntos e os de Java tamb\'em?
       \end{list}}

       \underline{\em Resposta\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sem restri\c c\~oes: $7!=5040$.
        \item As linguagens se alternam: $3!\times 4!=144$.
        \item Os livros de C ficam juntos: $5!\times 3!=720$.
        \item Os livros de C ficam juntos e os de Java tamb\'em: $2!\times 3!\times 4!=288$.
       \end{list}

 \item {\em 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?}

       \underline{\em Resposta\/}: Times poss\'{\i}veis com:
       \begin{itemize}
        \item 4 mulheres: $C(8,4)\times C(15,6)$.
        \item no m\'{\i}nimo 4 mulheres: $\sum_{k=4}^8C(8,k)\times C(15,10-k)$.
        \item no m\'{\i}nimo tantas mulheres quantos homens: $\sum_{k=5}^8C(8,k)\times C(15,10-k)$.
       \end{itemize}

 \item {\em Doze pratos est\~ao pendurados em 4 colunas, como mostra a
       seguinte figura:}
       
       \begin{picture}(200,126)(-80,0) \footnotesize
        \put(0,106){\line(1,0){200}}
        \put(0,116){\line(1,0){200}}
        \put(0,106){\line(0,1){10}}
        \put(200,106){\line(0,1){10}}
       
        \put(37,17){\circle{14}}
        \put(37,17){\makebox(0,0){V}}
        \put(37,24){\line(0,1){10}}
        \put(37,41){\circle{14}}
        \put(37,41){\makebox(0,0){V}}
        \put(37,48){\line(0,1){10}}
        \put(37,65){\circle{14}}
        \put(37,65){\makebox(0,0){V}}
        \put(37,72){\line(0,1){10}}
        \put(37,89){\circle{14}}
        \put(37,89){\makebox(0,0){V}}
        \put(37,96){\line(0,1){10}}
        \put(37,106){\circle*{4}}
       
        \put(79,41){\circle{14}}
        \put(79,41){\makebox(0,0){B}}
        \put(79,48){\line(0,1){10}}
        \put(79,65){\circle{14}}
        \put(79,65){\makebox(0,0){B}}
        \put(79,72){\line(0,1){10}}
        \put(79,89){\circle{14}}
        \put(79,89){\makebox(0,0){B}}
        \put(79,96){\line(0,1){10}}
        \put(79,106){\circle*{4}}
       
        \put(121,65){\circle{14}}
        \put(121,65){\makebox(0,0){P}}
        \put(121,72){\line(0,1){10}}
        \put(121,89){\circle{14}}
        \put(121,89){\makebox(0,0){P}}
        \put(121,96){\line(0,1){10}}
        \put(121,106){\circle*{4}}
       
        \put(163,41){\circle{14}}
        \put(163,41){\makebox(0,0){A}}
        \put(163,48){\line(0,1){10}}
        \put(163,65){\circle{14}}
        \put(163,65){\makebox(0,0){A}}
        \put(163,72){\line(0,1){10}}
        \put(163,89){\circle{14}}
        \put(163,89){\makebox(0,0){A}}
        \put(163,96){\line(0,1){10}}
        \put(163,106){\circle*{4}}
       \end{picture}
       
       {\em Como se pode ver, existem 4 pratos vermelhos na primeira coluna, 3
       brancos na segunda, 2 pretos na terceira e 3 azuis na quarta. Para ser
       admitida na equipe de tiro da sua Escola, Matilde tem que quebrar os 12
       pratos usando um rev\'olver e apenas 12 balas. Em certo instante, ela
       s\'o pode quebrar o prato mais baixo de alguma coluna (ou seja, apenas 1
       prato pode ser quebrado de cada vez). Sob estas condi\c c\~oes,
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item de quantas maneiras pode Matilde quebrar os 12 pratos?
        \item de quantas maneiras Matilde poderia quebrar os 12 pratos,
              quebrando inicialmente todos os vermelhos e pretos, antes de
              quebrar algum prato das outras cores?
        \item de quantas maneiras Matilde poderia quebrar os 12 pratos sem
              quebrar 2 brancos consecutivamente?
       \end{list}}

       \underline{\em Resposta\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Matilde pode quebrar os 12 pratos de $12!/(4!3!2!3!)$ maneiras.
        \item Vermelhos e pretos antes de pratos das outras cores: $[6!/(4!2!)]\times [6!/(3!3!)]$ maneiras.
        \item Sem quebrar 2 brancos consecutivamente: $[9!/(4!2!3!)]\times C(10,3)$ maneiras.
       \end{list}

 \item {\em No sistema Braille, um s\'{\i}mbolo \'e representado por {\it
       pelo menos uma\/} sali\^encia no arranjo de 6 pontos mostrados na parte
       (a) da seguinte figura:}
       
       \begin{picture}(200,90)(-50,0)
        \put(30,15){\makebox(0,0){(a)}}
        \put(5,24){\line(1,0){50}}
        \put(5,80){\line(1,0){50}}
        \put(5,24){\line(0,1){56}}
        \put(55,24){\line(0,1){56}}
        \put(12,37){\makebox(0,0){\footnotesize 3}}
        \put(20,37){\makebox(0,0){\circle*{1}}}
        \put(48,37){\makebox(0,0){\footnotesize 6}}
        \put(40,37){\makebox(0,0){\circle*{1}}}
        \put(12,52){\makebox(0,0){\footnotesize 2}}
        \put(20,52){\makebox(0,0){\circle*{1}}}
        \put(48,52){\makebox(0,0){\footnotesize 5}}
        \put(40,52){\makebox(0,0){\circle*{1}}}
        \put(12,67){\makebox(0,0){\footnotesize 1}}
        \put(20,67){\makebox(0,0){\circle*{1}}}
        \put(48,67){\makebox(0,0){\footnotesize 4}}
        \put(40,67){\makebox(0,0){\circle*{1}}}

        \put(120,15){\makebox(0,0){(b)}}
        \put(120,30){\makebox(0,0){``c''}}
        \put(95,24){\line(1,0){50}}
        \put(95,80){\line(1,0){50}}
        \put(95,24){\line(0,1){56}}
        \put(145,24){\line(0,1){56}}
        \put(102,37){\makebox(0,0){\footnotesize 3}}
        \put(110,37){\circle*{1}}
        \put(138,37){\makebox(0,0){\footnotesize 6}}
        \put(130,37){\circle*{1}}
        \put(102,52){\makebox(0,0){\footnotesize 2}}
        \put(110,52){\circle*{1}}
        \put(138,52){\makebox(0,0){\footnotesize 5}}
        \put(130,52){\circle*{1}}
        \put(102,67){\makebox(0,0){\footnotesize 1}}
        \put(110,67){\circle*{4}}
        \put(138,67){\makebox(0,0){\footnotesize 4}}
        \put(130,67){\circle*{4}}


        \put(210,15){\makebox(0,0){(c)}}
        \put(210,30){\makebox(0,0){``t''}}
        \put(185,24){\line(1,0){50}}
        \put(185,80){\line(1,0){50}}
        \put(185,24){\line(0,1){56}}
        \put(235,24){\line(0,1){56}}
        \put(192,37){\makebox(0,0){\footnotesize 3}}
        \put(200,37){\circle*{4}}
        \put(228,37){\makebox(0,0){\footnotesize 6}}
        \put(220,37){\circle*{1}}
        \put(192,52){\makebox(0,0){\footnotesize 2}}
        \put(200,52){\circle*{4}}
        \put(228,52){\makebox(0,0){\footnotesize 5}}
        \put(220,52){\circle*{4}}
        \put(192,67){\makebox(0,0){\footnotesize 1}}
        \put(200,67){\circle*{1}}
        \put(228,67){\makebox(0,0){\footnotesize 4}}
        \put(220,67){\circle*{4}}


        \put(300,15){\makebox(0,0){(d)}}
        \put(300,30){\makebox(0,0){``;''}}
        \put(275,24){\line(1,0){50}}
        \put(275,80){\line(1,0){50}}
        \put(275,24){\line(0,1){56}}
        \put(325,24){\line(0,1){56}}
        \put(282,37){\makebox(0,0){\footnotesize 3}}
        \put(290,37){\circle*{4}}
        \put(318,37){\makebox(0,0){\footnotesize 6}}
        \put(310,37){\circle*{1}}
        \put(282,52){\makebox(0,0){\footnotesize 2}}
        \put(290,52){\circle*{4}}
        \put(318,52){\makebox(0,0){\footnotesize 5}}
        \put(310,52){\circle*{1}}
        \put(282,67){\makebox(0,0){\footnotesize 1}}
        \put(290,67){\circle*{1}}
        \put(318,67){\makebox(0,0){\footnotesize 4}}
        \put(310,67){\circle*{1}}

       \end{picture}
       
       {\em Assim, por exemplo, a letra ``c'' \'e representada por sali\^encias nos
       pontos 1 e 4, como mostra a parte (b) da figura; a letra ``t'' \'e
       representada por sali\^encias nos pontos 2, 3, 4, e 5, como mostra a
       parte (c); e o ``;'' \'e representado por sali\^encias nos pontos 2 e 3,
       como mostra a parte (d).
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantos s\'{\i}mbolos t\^em exatamente 3 sali\^encias?
        \item Quantos s\'{\i}mbolos t\^em um n\'umero par de sali\^encias?
        \item Quantos s\'{\i}mbolos podem ser representados no sistema Braille?
       \end{list}}

       \underline{\em Resposta\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item T\^em exatamente 3 sali\^encias: $C(6,3)$ s\'{\i}mbolos.
        \item T\^em um n\'umero par de sali\^encias: $C(6,2)+C(6,4)+C(6,6)=2^5-1=31$ s\'{\i}mbolos.
        \item Podem ser representados no sistema Braille: $\sum_{r=1}^{6}C(6,k)=2^6-1=63$ s\'{\i}mbolos.
       \end{list}

 \item {\em Quantos {\em bytes\/} cont\^em (a) exatamente dois 1's; (b) exatamente seis
       1's; (c) pelo menos seis 1's?}

       \underline{\em Resposta\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cont\^em exatamente dois 1's: $C(8,2)=28$ {\em bytes\/}.
        \item Cont\^em exatamente seis 1's: $C(8,6)=28$ {\em bytes\/}.
        \item Cont\^em pelo menos seis 1's: $C(8,6)+C(8,7)+C(8,8)=28+8+1=37$ {\em bytes\/}.
       \end{list}

 \item {\em Quatro n\'umeros devem ser selecionados do conjunto $\{-5,-4,-3,
       -2,-1,1,2,3,4\}$. De quantas maneiras podem ser feitas as sele\c c\~oes
       de forma que o produto dos 4 n\'umeros seja positivo e
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item os n\'umeros selecionados sejam distintos?
        \item cada n\'umero possa ser selecionado at\'e 4 vezes?
        \item cada n\'umero possa ser selecionado at\'e 3 vezes?
       \end{list}}

       \underline{\em Resposta\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item N\'umeros selecionados distintos: $C(5,4)+C(4,4)+C(5,2)C(4,2)$.
        \item Cada n\'umero pode ser selecionado at\'e 4 vezes:
                                                $C(5-1+4,4)+C(4-1+4,4)+C(5-1+2,2)C(4-1+2,2)$.
        \item Cada n\'umero pode ser selecionado at\'e 3 vezes:
                                                $[C(5-1+4,4)-5]+[C(4-1+4,4)-4]+C(5-1+2,2)C(4-1+2,2)$.
       \end{list}

 \item {\em O sargento Garcia deve distribuir 40 balas, 20 para rifles e
       20 para rev\'olveres, entre 4 oficiais, de forma que cada oficial receba
       no m\'{\i}nimo 2 e no m\'aximo 7 balas de cada tipo. De quantas maneiras
       ele pode fazer a distribui\c c\~ao?}

       \underline{\em Solu\c c\~ao\/}: O n\'umero de distribui\c c\~oes de 20 balas de rifles \'e o
       n\'umero de solu\c c\~oes em inteiros para a equa\c c\~ao $x_1+x_2+x_3+x_4=20$ com $2\leq x_i \leq 7$.
       Isto \'e o mesmo que o n\'umero de solu\c c\~oes para a equa\c c\~ao $x_1+x_2+x_3+x_4=12$ com
       $0\leq x_i \leq 5$. Seja $A_i$ o conjunto das solu\c c\~oes para a equa\c c\~ao $x_1+x_2+x_3+x_4=12$
       com $x_i\geq 6$ e $x_j\geq 0$ para $j\not=i$. Seja $U$ o conjunto das solu\c c\~oes para a
       equa\c c\~ao $x_1+x_2+x_3+x_4=12$ com $x_i\geq 0$ para todo $i$. Ent\~ao o n\'umero procurado \'e
       $|U|-|A_1\cup A_2\cup A_3\cup A_4|$, que d\'a:
       \[C(4-1+12,12)-[C(4,1)C(4-1+6,6)-C(4,2).1+C(4,3).0-C(4,4).0]\mbox{.}\]
       Isto d\'a $C(15,12)-4C(9,6)+6=125$.
       Pela regra do produto, a resposta \'e: $125^2=15625$.

 \item {\em 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?}

       \underline{\em Solu\c c\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $n!$
        \item Tem-se, sucessivamente:
              \begin{itemize}
               \item $n$ escolhas para a caixa vazia;
               \item $n-1$ escolhas para a caixa com dois objetos;
               \item $C(n,2)$ escolhas para os objetos da caixa com dois;
               \item $(n-2)!$ distribui\c c\~oes dos objetos restantes.
              \end{itemize}
              Pela regra do produto, a resposta \'e: $n(n-1)C(n,2)(n-2)!=n!C(n,2)$.
       \end{list}

 \item {\em Quantas maneiras existem de distribuir $r$ bolas id\^{e}nticas em $n$
       caixas distintas, ficando exatamente $v$ caixas vazias?}
              
       {\it Solu\c{c}\~{a}o:}
       O n\'umero de escolhas das $v$ caixas vazias \'e $C(n,v)$. Descontando-se
       $n-v$ bolas obrigatoriamente colocadas nas $n-v$ caixas n\~ao vazias,
       resta ent\~ao distribuir $r-(n-v)$ bolas id\^enticas em $n-v$ caixas, o
       que pode ser feito de $C((n-v)-1+(r-n+v),r-n+v)$ maneiras. Aplicando-se
       a regra do produto, tem-se a resposta: $C(n,v)C(r-1,r-n+v)$.

 \item {\em 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}}

       {\it Solu\c{c}\~{a}o:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O n\'umero de arranjos de 4 sapatos sem nenhum par \'e
              $12\times 10\times 8\times 6$.
        \item O n\'umero de arranjos de 4 sapatos com dois pares \'e
              $12\times 3\times 10$ (3 \'e o n\'umero de posi\c c\~oes para o
              par do sapato que aparece na primeira posi\c c\~ao).
       \end{list}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O n\'umero de sele\c c\~oes de 4 sapatos sem nenhum par \'e igual
              \`a divis\~ao do n\'umero de arranjos, calculado acima, por $4!$
              (que \'e o n\'umero de arranjos de 4 sapatos espec\'{\i}ficos),
              ou seja, $(12\times 10\times 8\times 6)/4!$.
        \item O n\'umero de sele\c c\~oes de 4 sapatos com dois pares \'e
              $C(6,2)$ (sele\c c\~ao de 2 dentre os 6 pares).
       \end{list}

 \item {\em Qual a probabilidade de que 12 pessoas escolhidas aleatoriamente fa\c cam anivers\'ario
       em meses di\-fe\-ren\-tes? E que fa\c cam anivers\'ario no mesmo m\^es? Assuma 365 dias no ano.}

       {\it Solu\c{c}\~{a}o:}
       Para cada pessoa existem 365 dias poss\'{\i}veis de anivers\'ario. Assim, para 12 pessoas
       o n\'umero de arranjos poss\'{\i}veis de anivers\'arios \'e $365^{12}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O n\'umero de arranjos tais que 12 pessoas fazem anivers\'ario em meses dife\-ren\-tes
              \'e $12!\times 31^7\times 30^4\times 28^1$. Assim a probabilidade \'e
              \[\frac{12!\times 31^7\times 30^4\times 28}{365^{12}}\mbox{.}\]
        \item O n\'umero de arranjos tais que 12 pessoas fazem anivers\'ario no mesmo m\^es
              \'e $7\times 31^{12}+4\times 30^{12}+1\times 28^{12}$. Assim a probabilidade \'e
              \[\frac{7\times 31^{12}+4\times 30^{12}+28^{12}}{365^{12}}\mbox{.}\]
       \end{list}

 \item {\em $n$ pauzinhos, cada um de uma cor, s\~ao quebrados em duas partes, uma maior 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?}

       {\it Resposta:} $n!$.

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

       {\it Resposta:} $C(30,10)\times 2^{20}$.

 \item {\em 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?}

       {\it Solu\c c\~ao:} Antes do $k$-\'esimo \'as na $r$-\'esima carta, pode-se colocar
       $k-1$ ases de $C(r-1,k-1)$ maneiras. Existem $P(4,k)$ arranjos para os $k$ primeiros
       ases, e $P(48,r-k)$ arranjos para cartas dife\-ren\-tes de ases antes do $k$-\'esimo \'as
       ($r$-\'esima carta). Finalmente, h\'a $(52-r)!$ arranjos das cartas restantes.
       Pela regra do produto, a resposta \'e: $C(r-1,k-1)\times P(4,k)\times P(48,r-k)\times (52-r)!$.
       
 \item {\em Quantos arranjos das letras de EMPERRAMENTO n\~{a}o t\^em vogais consecutivas?}

       {\it Solu\c c\~ao:} Arranjos para as 7 consoantes: $7!/(2!2!)$. N\'umero de posicionamentos
       para as vogais (antes, entre e/ou depois das consoantes): $C(8,5)$ (isto garante que as
       vogais n\~ao ficam consecutivas). Arranjos para as 5 vogais: $5!/3!$. Pela regra do
       produto, a resposta \'e: $[7!/(2!2!)]\times C(8,5)\times 5!/3!$.

  \item {\em 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 \]}

       {\it Solu\c c\~ao:}
       O n\'umero de solu\c c\~oes para $x_1+x_2+x_3=10$ com $x_k\geq k$ \'e o n\'umero de
       solu\c c\~oes para $y_1+y_2+y_3=4$ com $y_k\geq 0$ que, por sua vez, \'e $C(3-1+4,4)$.

       O n\'umero de solu\c c\~oes para $10+x_4+x_5\leq 20$ com $x_k\geq k$ \'e o n\'umero de
       solu\c c\~oes para $x_4+x_5+z=10$ com $x_4,x_5\geq k$ e $z\geq 0$ que, por sua vez,
       \'e o n\'umero de solu\c c\~oes para $x_4+x_5+z=1$ com $x_4,x_5,z\geq 0$; este
       \'ultimo \'e $C(3-1+1,1)$. Resposta: $C(3-1+4,4)\times C(3-1+1,1)=15\times 3=45$.

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

       {\it Resposta:} $18!/(9!3!0!6!)$.

 \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.

       {\it Solu\c c\~ao:} Pelo Teorema Binomial: \[(2+1)^n=\sum_{k=0}^{n}\left(\begin{array}{c} n \\
                                        k
                                       \end{array} \right) 2^k1^{n-k}=\sum_{k=0}^{n}\left(\begin{array}{c} n \\
                                        k
                                       \end{array} \right) 2^k\mbox{.}\]

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

       {\it Solu\c c\~ao:} O coeficiente de $x^n$ em $(x+1)^n(x+1)^n$, aplicando-se o Teorema Binomial,
       \'e $\sum_{k=0}^nC(n,k)C(n,n-k)$. Como $C(n,n-k)=C(n,k)$, segue-se que tal coeficiente \'e
       $\sum_{k=0}^nC(n,k)^2$. Por outro lado, o coeficiente de $x^n$ em $(x+1)^{2n}$, aplicando-se
       de novo o Teorema Binomial, \'e $C(2n,n)$. Assim, $C(2n,n)=\sum_{k=0}^{n}C(n,k)^2$.

 \item {\em 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}}
      
       {\it Solu\c{c}\~{a}o:}       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(2n,n)=\sum_{k=0}^{n}C(n,k)^2$.
        
              Sejam $A$ e $B$ dois conjuntos disjuntos de tamanho $n$. $C(2n,n)$
              \'e o n\'umero de subconjuntos de tamanho $n$ de $A\cup B$. E:
              \begin{itemize}
               \item $C(n,0)^2=C(n,0)C(n,n)$ \'e o n\'umero de subconjuntos de
                     tamanho $n$ de $A\cup B$, com $0$ elementos de $A$ e $n$
                     elementos de $B$;
               \item $C(n,1)^2=C(n,1)C(n,n-1)$ \'e o n\'umero de subconjuntos de
                     tamanho $n$ de $A\cup B$, com $1$ elemento de $A$ e $n-1$
                     elementos de $B$;
               \item $\vdots$
               \item $C(n,n)^2=C(n,n)C(n,0)$ \'e o n\'umero de subconjuntos de
                     tamanho $n$ de $A\cup B$, com $n$ elementos de $A$ e $0$
                     elementos de $B$.
              \end{itemize}

        \item $C(m+n,r)=\sum_{k=0}^{r}C(m,k)C(n,r-k)$
      
              Sejam $A$ e $B$ dois conjuntos disjuntos, $A$ de tamanho $m$ e $B$
              de tamanho $n$. $C(m+n,r)$ \'e o n\'umero de subconjuntos de
              tamanho $r$ de $A\cup B$. E:
              \begin{itemize}
               \item $C(m,0)C(n,r)$ \'e o n\'umero de subconjuntos de tamanho
                     $r$ de $A\cup B$, com $0$ elementos de $A$ e $r$ elementos
                     de $B$;
               \item $C(m,1)C(n,r-1)$ \'e o n\'umero de subconjuntos de tamanho
                     $r$ de $A\cup B$, com $1$ elemento de $A$ e $r-1$ elementos
                     de $B$;
               \item $\vdots$
               \item $C(m,r)C(n,0)$ \'e o n\'umero de subconjuntos de
                     tamanho $r$ de $A\cup B$, com $r$ elementos de $A$ e $0$
                     elementos de $B$.
              \end{itemize}

       \end{list}
      
\end{enumerate}
 
\end{document}


