\documentclass[11pt,a4paper]{article}

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

\usepackage{fullpage}

\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/Solução do professor}

\vspace*{2mm}
\begin{enumerate}
 \item[0.] {\footnotesize 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?}

       \textit{Solução}: $P(8,3)=8.7.6=336$.
\end{enumerate}
\begin{enumerate}
 \item {\footnotesize 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}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P(10;4,4,2)=10!/(4!4!2!)=10.9.8.7.6.5/(24.2)=10.9.7.5=3150$.
        \item $P(6;4,2)\times C(7,4)=[6!/(4!2!)]\times[(7.6.5)/6]=15\times 35=525$.
       \end{list}

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

       \textit{Solução}:
			
			 O número de distribuições possíveis de $n$ bolinhas idênticas em $n$ caixas distintas é
			 $C(n-1+n,n)=C(2n-1,n)=(2n-1)!/n!(n-1)!$. Segue-se que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Como o número de distribuições em que nenhuma caixa fique vazia é 1, a probabilidade é
				      $1/C(2n-1,n)=n!(n-1)!/(2n-1)!$.
        \item As caixas a ficar vazia e a conter duas bolinhas podem ser escolhidas de $n(n-1)$ maneiras. As
				      outras $n-2$ caixas vão conter as bolinhas restantes. Logo, a probabilidade é
							$n(n-1)/C(2n-1,n)=n(n-1)n!(n-1)!/(2n-1)!=(n-1)(n!)^2/(2n-1)!$.
       \end{list}


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

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+\cdots+x_n=r$, com $x_i\geq i$. \\
				      FG: $(x+x^2+x^3+\cdots)(x^2+x^3+x^4+\cdots)\cdots(x^n+x^{n+1}+x^{n+2}+\cdots)$.
        \item $x_1+x_2+x_3+x_4+x_5=6$, com $x_1\leq 2$, $x_2,x_3,x_4\geq 0$, $x_5\geq 2$. \\
				      FG: $(1+x+x^2)(1+x+x^2+\cdots)^3(x^2+x^3+x^4+\cdots)$.
							
							
							Como $(1+x+x^2)(1+x+x^2+\cdots)^3(x^2+x^3+x^4+\cdots)=(1-x^3)x^2(1+x+x^2+\cdots)^5=
							(x^2-x^5)(1+x+x^2+\cdots)^5$, o coeficiente de $x^6$ é $C(5-1+4,4)-C(5-1+1,1)=C(8,4)-C(5,1)=70-5=65$.
       \end{list}

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

%       \textit{Solução}:
%       \begin{eqnarray*}
%                \lefteqn{(1-x^2)^{12}/(1-x)^3 = (1-x^2)^{12}(1+x+x^2\cdots)^3}
%                    \\
%                  & & =(C(12,0)-C(12,1)x^{2}+C(12,2)x^{4}-\cdots+C(12,12)x^{24})
%                        \\
%                  & & \;\;\;\; (C(3-1+0)+C(3-1+1,1)x+C(3-1+2,2)x^2+\cdots)
%              \end{eqnarray*}
              
%              Coeficiente de $x^5$: $C(12,0)C(3-1+5,5)-C(12,1)C(3-1+3,3)+C(12,2)C(3-1+1,1)=21-120+198=99$.

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

       \textit{Solução}: O número pedido é o número de soluções para a equação:
			  \[x_1+x_2+x_3+x_4=10 \mbox{ para } x_1,x_2\leq 3 \mbox{ e } x_3,x_4\geq 0.\]
			 A função geradora é, portanto, $(1+x+x^2+x^3)^2(1+x+x^2+\cdots)^2=(1-x^4)^2(1+x+x^2+\cdots)^4$, que é igual a
			 $[C(2,0)-C(2,1)x^4+C(2,2)x^8][C(4-1+0,0)+C(4-1+1,1)x+C(4-1+2,2)x^2+\cdots]$. O coeficiente de $x^{10}$ é
			 $C(2,0)C(4-1+10,10)-C(2,1)C(4-1+6,6)+C(2,2)C(4-1+2,2)=C(13,10)-2C(9,6)+C(5,2)=286-168+10=128$.

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

       \textit{Solução}:
            \begin{list}{(\alph{conta})}{\usecounter{conta}}
						 \item FG para $n$: $x[1/(1-x)]'=x/(1-x)^2$.
						 \item FG para $2^n$: $1/(1-2x)$.
						 \item FG para $2^n-2n$: $[1/(1-2x)]-x/(1-x)^2$.
						 \item FG para $\sum_{k=0}^{n}(2^k-2k)$: $[1/(1-2x)(1-x)]-x/(1-x)^3$.
            \end{list}
\end{enumerate}

\end{document}

