\documentclass[12pt, a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\pagestyle{empty}

\newcounter{conta}
\begin{document}

\noindent Departamento de Ci\^encia da Computa\c c\~ao
\hfill UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
Professor: Newton Jos\'{e} Vieira  \\
{\bf Segunda Prova/Solu\c c\~ao do professor} \hfill 27/04/2005

\begin{enumerate}
 \item {\footnotesize Quantas maneiras existem de distribuir 8 bombons e 3 balas entre 5 crian\c cas,
       nos seguintes casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Os bombons s\~ao todos id\^enticos e as balas s\~ao todas id\^enticas.
        \item Como (a), mas nenhuma crian\c ca pode receber mais de uma bala.
        \item Os bombons s\~ao id\^enticos, mas as balas s\~ao distintas.
        \item Como (c), mas nenhuma crian\c ca pode receber mais de uma bala.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(5-1+8,8)\times C(5-1+3,3)$.
        \item $C(5-1+8,8)\times C(5,3)$.
        \item $C(5-1+8,8)\times 5^3$.
        \item $C(5-1+8,8)\times P(5,3)$.
       \end{list}     

 \item {\footnotesize Considere as letras da palavra MATEMATICA.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantos arranjos existem de suas letras?
        \item Em quantos arranjos n\~ao existem vogais consecutivas?
        \item Em quantos arranjos as consoantes est\~ao todas consecutivas?
        \item Em quantos arranjos as vogais est\~ao em ordem alfab\'etica?
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P(10;3,2,2,1,1,1)=10!/(3!2!2!)$.
        \item O n\'umero de arranjos das consoantes \'e $P(5;2,2,1)=5!/(2!2!)$.
              Ap\'os dispostas as 5 consoantes, existem 6 posi\c c\~oes para
              coloca\c c\~ao das vogais; como existem $C(6,5)=6$ escolhas para
              as 5 posi\c c\~oes das vogais, estas podem ser dispostas de
              $6\times P(5;3,1,1)=6!/3!$ formas. Pela regra do
              produto, a resposta \'e: $[5!/(2!2!)]\times(6!/3!)$.
        \item N\'umero de arranjos considerando-se uma ``supervogal'' constitu\'{\i}da
              de todas as consoantes: $P(6;3,1,1,1)=6!/3!$. Como o n\'umero de
              arranjos das consoantes \'e $P(5;2,2,1)=5!/(2!2!)$, pela regra do
              produto a reposta \'e: $(6!/3!)\times[5!/(2!2!)]$.
        \item Basta considerar as vogais como ``letras id\^enticas''. Com isto,
              obt\'em-se a resposta: $P(10;5,2,2,1)=10!/(5!2!2!)$.
       \end{list}

 \item {\footnotesize Sobre os teoremas binomial e multinomial:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Use o teorema binomial para expandir $(x-2)^4$.
        \item Qual \'e o coeficiente de $x^{11}$ em  $(5-3x)^{40}$?
        \item Qual \'e o coeficiente de $x^{11}yw^8$ em  $(x+y+z+w)^{20}$?
        \item Usando o teorema binomial mostre que:
              \[\sum_{k=0}^{n}(-2)^k\times C(n,k) \mbox{ \'e $1$ se $n$ \'e par,
                e \'e $-1$ se $n$ \'e \'{\i}mpar.}\]
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(4,0)x^4(-2)^0+C(4,1)x^3(-2)^1+C(4,2)x^2(-2)^2+C(4,3)x^1(-2)^3+C(4,4)x^0(-2)^4=
              x^4-8x^3+24x^2-32x+16$.
        \item $C(40,11)\times 5^{29}\times (-3)^{11}$.
        \item $C(20;11,1,0,8)=20!/(11!8!)$.
        \item $(-1)^n=(1-2)^n=C(n,0)(-2)^0+C(n,1)(-2)^1+C(n,2)(-2)^2+\cdots+C(n,n)(-2)^n$.
              Esta \'ultima soma \'e justamente $\sum_{k=0}^{n}(-2)^k\times C(n,k)$. Assim,
              como $(-1)^n$ \'e $1$ se $n$ \'e par, e \'e $-1$ se $n$ \'e \'{\i}mpar, segue-se
              o resultado.
       \end{list}

 \item {\footnotesize Seja o problema: {\em encontrar o n\'umero de lan\c camentos de 3 dados
       distintos que produz uma soma de \underline{no m\'aximo} 10}. Fa\c ca em
       seq\"u\^encia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Modele tal problema de tal forma que a solu\c c\~ao seja o
              n\'umero de solu\c c\~oes em inteiros n\~ao negativos de uma
              equa\c c\~ao.
        \item Encontre uma fun\c c\~ao geradora para o problema.
        \item Determine a solu\c c\~ao a partir da fun\c c\~ao geradora.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+x_3\leq 10$, com $x_i\in\{1,2,3,4,5,6\}$ para $i\in\{1,2,3\}$.

              O n\'umero de solu\c c\~oes desta \'e igual ao da equa\c c\~ao:

              $x_1+x_2+x_3+x_4=10$, com $x_i\in\{1,2,3,4,5,6\}$ para $i\in\{1,2,3\}$ e $x_4\geq 0$.
        \item $(x+x^2+x^3+x^4+x^5+x^6)^3(1+x+x^2+\cdots)$.

        \item A solu\c c\~ao \'e o coeficiente de $x^{10}$ em $(x+x^2+x^3+x^4+x^5+x^6)^3(1+x+x^2+\cdots)$.
              Esta \'ultima \'e igual a $x^3(1-x^6)^3(1+x+x^2+\cdots)^4$. Assim, a solu\c c\~ao \'e o
              coeficiente de $x^7$ em $(1-x^6)^3(1+x+x^2+\cdots)^4$. Isto \'e o mesmo que
              $[C(3,0)-C(3,1)x^6+C(3,2)x^{12}-C(3,3)x^{18}]\times[C(4-1+0,0)+C(4-1+1,1)x+C(4-1+2,2)x^2+
              \cdots]$. Portanto, a solu\c c\~ao \'e: $C(3,0)C(4-1+7,7)-C(3,1)C(4-1+1,1)=
              C(10,7)-3C(4,1)=(10\times 9\times 8)/3!-12=108$.
       \end{list}


 \item {\footnotesize Determine, usando fun\c c\~ao geradora,  uma f\'ormula fechada para a soma:
       \[\sum_{k=0}^n(2k+1)\mbox{.}\]}

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

       A fun\c c\~ao geradora para $n$ \'e $x[1/(1-x)]'=x/(1-x)^2$. A fun\c c\~ao geradora para
       $2n+1$: $[2x/(1-x)^2]+[1/(1-x)]=(1+x)/(1-x)^2$. Finalmente, obt\'em-se a
       fun\c c\~ao geradora para $\sum_{k=0}^n(2k+1)$: $(1+x)/(1-x)^3$. Esta \'ultima \'e
       igual a: $(1+x)[C(3-1+0,0)+C(3-1+1,1)x+C(3-1+2,2)x^2+\cdots]$. A resposta \'e ent\~ao
       o coeficiente de $x^n$: $C(3-1+n,n)+C(3-1+n-1,n-1)=C(n+2,n)+C(n+1,n-1)=(n+2)(n+1)/2+
       (n+1)n/2=(n+1)(n+2+n)/2=(n+1)^2$.

\end{enumerate}
\end{document}
