\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}

\pagestyle{empty}
\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 \\
\underline{Segunda Prova} \hfill 30/9/2013

\vspace*{2mm}
\noindent \textit{A questão 0 vale 1 ponto e as restantes valem 3 pontos cada uma.}
\vspace*{2mm}
\begin{enumerate}
 \item[0.] Um torneio de natação vai ser disputado por 8 atletas. Quantas possibilidades de premiação existem,
       considerando que só recebem prêmios o primeiro (medalha de ouro), o segundo (medalha de prata) e o terceiro
			 (medalha de bronze) colocados?
\end{enumerate}
\begin{enumerate}
 \item De quantas maneiras se pode arranjar as letras AAAAOOOOXX (4 As, 4 Os, 2 Xs):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item No total?
        \item Sem As consecutivos?
       \end{list}

 \item Suponha que $n$ bolinhas brancas idênticas são distribuídas (aleatoriamente) em $n$ caixas
       numeradas de 1 a n. Qual é a probabilidade que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Nenhuma caixa fique vazia?
        \item Exatamente uma caixa fique vazia?
       \end{list}

 \item Escreva problemas do tipo ``soluções em inteiros de uma equação'' equivalentes aos abaixo. Em seguida,
       para cada um, determine a função geradora correspondente.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O número de maneiras de distribuir $r$ bolas idênticas em $n$ caixas distintas com pelo menos $i$ bolas
				      na $i$-ésima caixa.
        \item O número de multiconjuntos de 6 elementos tirados do conjunto $\{1,2,3,4,5\}$ tais que:
				      \begin{itemize}
							 \item o número 1 pode aparecer no máximo duas vezes;
							 \item o número 5 deve aparecer no mínimo duas vezes.
							\end{itemize}
							Para este problema, determine também a solução: o coeficiente de $x^6$ na função geradora.
       \end{list}

% \item Encontre o coeficiente de  $x^{5}$ em $(1-x^2)^{12}/(1-x)^3$.

 \item Determine o número de maneiras de pintar 10 bolas idênticas, dadas as seguintes restrições:
			 \begin{itemize}
			 \item há 4 cores disponíveis: branca, amarela, azul e verde;
       \item as tintas azul e verde são suficientes para pintar no máximo 3 bolas (para cada uma das cores);
			 \item existem tintas branca e amarela à vontade.
			\end{itemize}
			\textit{Dica}: Use função geradora.

 \item Encontre funções geradoras para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item $n$.
				\item $2^n$.
				\item $2^n-n$.
				\item $\sum_{k=0}^{n}(2^k-k)$.
       \end{list}
\end{enumerate}

\hrule
\vspace*{.5mm}
\hrule

\vspace*{3mm}
No verso estão reproduzidas algumas identidades úteis para manipulação de funções geradoras e extração de coeficientes.

\pagebreak
\begin{flushleft}\it
 Identidades úteis para manipulação de funções geradoras e extração de coeficientes:
\end{flushleft}


\begin{itemize}
 \item $(1+x)^n=C(n,0)+C(n,1)x+C(n,2)x^2+\cdots+C(n,n)x^n$
 \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/(1-x)=1+x+x^2+x^3+\cdots$
 \item $(1+x+x^2+\cdots+x^m)^n=(1-x^{m+1})^n(1+x+x^2+\cdots)^n$
 \item $(1-x^k)^n=C(n,0)-C(n,1)x^k+C(n,2)x^{2k}-\cdots+(-1)^nC(n,n)x^{nk}$
 \item Dados que $g(x)$ e $h(x)$ sejam as funções geradoras para $a_n$ e $b_n$, respectivamente, então:
       \begin{itemize}
			  \item $c_1g(x)+c_2h(x)$ é a função geradora para $c_1a_n+c_2b_n$, se $c_1$ e $c_2$ são constantes.
			  \item $g(x)h(x)$ é a função geradora para $\sum_{k=0}^{n}a_kb_{n-k}$.
			  \item $(1-x)g(x)$ é a função geradora para $a_n-a_{n-1}$.
			  \item $xg'(x)$ é a função geradora para $na_n$.
			  \item $g(x)/(1-x)$ é a função geradora para $\sum_{k=0}^{n}a_k$.
			 \end{itemize}
\end{itemize}
\end{document}

