\documentclass[11pt, a4paper]{article}

\usepackage[portuguese]{babel}

\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\begin{document}

\selectlanguage{portuguese}

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

\begin{enumerate}
 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(7,3)\times C(4,2)=35\times 6=210$.
        \item N\'umero de comit\^es sem ambos: $C(6,2)\times C(3,2)$. N\'umero
              de comit\^es com a Sra. B.: $C(6,1)\times C(3,2)$. N\'umero de
              comit\^es com o Sr. B.: $C(6,2)\times C(3,1)$.
              Total: $C(6,2)\times C(3,2)+C(6,1)\times C(3,2)+C(6,2)\times C(3,1)=45+18+45=108$.

              Outra solu\c c\~ao: $C(7,2)\times C(4,2)-C(6,1)C(3,1)=126-18=108$.
       \end{list}

% 183: Example 4. Tucker

 \item Se apenas uma das 4 letras aparece 4 vezes, o n\'umero de seq\"u\^encias
       \'e $C(4,1)\times P(10;4,2,2,2)$. E se duas das 4 letras aparece 3
       vezes, o n\'umero \'e $C(4,2)\times P(10;3,3,2,2)$. O total de possibilidades
       \'e ent\~ao: $C(4,1)\times P(10;4,2,2,2)+C(4,2)\times P(10;3,3,2,2)=
        4\times 18,900+6\times 25.200=226.800$.
% 199: Example 5.

 \item $C(5-1+20,20)\times C(5-1+15,15)$.

 \item Colocando-se 4 Xs entre as 5 vogais, sobram 4 Xs para distribuir nas 6
       posi\c c\~oes correspondentes a antes, entre e ap\'os as vogais, o que
       pode ser feito de $C(6-1+4,4)$ maneiras. As vogais podem ser permutadas
       de $5!$ formas. Assim a resposta \'e $C(6-1+4,4)\times 5!=126\times 120=15.120$.
% 207: Example 9.

 \item Pelo teorema binomial, $\sum_{r=0}^n {n \choose r}=(1+1)^n=2^n$.
       Pelo mesmo teorema, ${n \choose 1}+{n \choose 3}+\cdots=2^{n-1}$,
       pois ${n \choose 0}-{n \choose 1}+{n \choose 2}-{n \choose 3}+\cdots=(1-1)^n=0$.
       Logo, a soma \'e $2^n+2^{n-1}=1,5\times 2^n$.

% 221: Exercise 13b.

 \item Sejam dois conjuntos $A$ e $B$ tais que $|A|=|B|=n$ e $A\cap B=\emptyset$.
       Ent\~ao $C(2n,2)$ \'e o n\'umero de subconjuntos de 2 elementos tomados
       de $A\cup B$. E como:
       \begin{itemize}
        \item $C(n,2)$ \'e o n\'umero de subconjuntos de 2 elementos tomados de $A$,
        \item $C(n,2)$ \'e o n\'umero de subconjuntos de 2 elementos tomados de $B$, e
        \item $n^2$ \'e o n\'umero de subconjuntos de $A\cup B$, sendo um elemento de
              $A$ e o outro de $B$,
       \end{itemize}
       $2C(n,2)+n^2$ \'e o n\'umero de subconjuntos de 2 elementos tomados
       de $A\cup B$. Logo, $C(2n,2)=2C(n,2)+n^2$.
       
% 221: Exercise 9a.

 \item $(1+x^2+x^4+x^6+x^8+x^{10})^2(x^3+x^4+x^5)^3$.

% 246: Example 3.

 \item Fun\c c\~ao geradora: $(1+x)^{19}(1+x+x^5)=(1+x+x^5)[C(19,0)+C(19,1)x+
       C(19,2)x^2+\cdots+C(19,19)x^{19}]$.

       Coeficiente de $x^{15}: C(19,15)+C(19,14)+C(19,10)$.

% 253: Example 2.

 \item Fun\c c\~ao geradora: $(x^2+x^3+x^4+x^5+x^6)^7=x^{14}(1+x+x^2+x^3+x^4)^7=
       x^{14}(1-x^5)^7(1+x+x^2+\cdots)^7=x^{14}[C(7,0)-C(7,1)x^5+C(7,2)x^{10}-C(7,3)x^{15}
       +C(7,4)x^{20}-C(7,5)x^{25}+C(7,6)x^{30}-C(7,7)x^{35}][C(7-1+0)+C(7-1+1,1)x+C(7-1+2,2)x^2+\cdots]$.

       Coeficiente de $x^{25}$: $C(7,0)\times C(7-1+11,11)-C(7,1)\times C(7-1+6,6)+C(7,2)\times C(7-1+1,1)$.

% 254: Example 4.

 \item Sabendo que a fun\c c\~ao geradora para $\sum_{k=2}^n [(k+1)\times k\times (k-1)]$:
       $6x^2/(1-x)^5=6x^2(C(5-1+0)+C(5-1+1,1)x+C(5-1+2,2)x^2+\cdots$.

        Coeficiente de $x^n$: $6C(5-1+n-2,n-2)=6C(n+2,4)=(n+2)(n+1)n(n-1)/4$. 

% 275: Example 2.
\end{enumerate}

\end{document}
\begin{flushright}
\underline{\em Veja algumas f\'ormulas no verso.}
\end{flushright}

\begin{itemize}
 \item Teorema binomial: $(1+x)^n=\sum_{r=0}^nC(n,r)x^r$.
 \item Teorema multinomial: $(x_1+x_2+\cdots+x_m)^n$ \'e a soma de todos os termos
       da forma $C(n;r_1,r_2,\ldots,r_m)x_1^{r_1}x_2^{r_2}\ldots x_m^{r_m}$ tais que
       $r_1+r_2+\cdots+r_m=n$.

\vspace*{2mm}
\hrule

 \item $(1+x+x^2+\cdots)^n=C(n-1+0,0)+C(n-1+1,1)x+C(n-1+2,2)x^2+\cdots$
 \item $(1+x+x^2+\cdots+x^{m-1})^n=(1-x^m)^n(1+x+x^2+\cdots)^n$.
 \item $(1-x^m)^n=C(n,0)-C(n,1)x^m+C(n,2)x^{2m}+\cdots+(-1)^nC(n,n)x^{nm}$.
 \item $1/(1-x)=1+x+x^2+\cdots$

\vspace*{2mm}
\hrule

       Sejam $g(x)$ a fun\c c\~ao geradora para $a_n$, e $h(x)$ a fun\c c\~ao geradora
       para $b_n$. Ent\~ao:

\vspace*{2mm}
 \item $g(x)/(1-x)$ \'e a fun\c c\~ao geradora para $\sum_{k=0}^na_k$.
 \item $c_1g(x)+c_2h(x)$ \'e a fun\c c\~ao geradora para $c_1a_n+c_2b_n$.
 \item $(1-x)g(x)$ \'e a fun\c c\~ao geradora para $a_n-a_{n-1}$.
 \item $xg'(x)$ \'e a fun\c c\~ao geradora para $na_n$.
 \item $g(x)h(x)$ \'e a fun\c c\~ao geradora para $a_0b_n+a_1b_{n-1}+\cdots+a_nb_0$.
\end{itemize}
\end{document}
