\documentclass[11pt,a4paper]{article}

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

\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton Jos\'{e} Vieira \hfill www.dcc.ufmg.br/\verb+~+nvieira\\
\underline{Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: 25/09/2013

\vspace*{4mm}
\noindent {\bf Combinat\'{o}ria Elementar}

\vspace*{2mm}
\begin{enumerate}
 \item De quantas maneiras se pode arranjar as letras da palavra GUARATINGUETA:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item No total?
        \item Com todos os As consecutivos?
        \item Com todas as vogais consecutivas?
        \item De forma que n\~{a}o existam (dois) A's consecutivos?
       \end{list}

 \item Determine o n\'{u}mero de sele\c{c}\~{o}es de 6 bolas de sorvete a partir
       de bolas de 20 sabores diferentes, de forma que n\~ao sejam selecionadas mais de
       duas bolas com o mesmo sabor.

 \item Em uma transfer\^encia (simult\^anea) de 12 bandidos de uma penitenci\'aria para outra eles
       devem ser acompanhados cada um por um policial.  Quantos grupos de 12 pares podem ser
       constitu\'{\i}dos a partir dos 12 bandidos e 12 policiais?

 \item Um batalh\~ao de 50 soldados deve fazer 5 filas de 10 elementos. A \'unica restri\c{c}\~ao
       \'e que os 5 maiores soldados devem encabe\c{c}ar as 5 filas. Quantas possibilidades
       existem para isso?

 \item De quantas maneiras 5 homens e 5 mulheres podem ser dispostos lado a lado de forma
       que homens n\~ao fiquem juntos?

 \item Uma fazendeiro produz laranjas de 5 diferentes qualidades. Supondo que ele v\'a
       selecionar 10 laranjas para presentear o vizinho, quantas sele\c{c}\~oes
       s\~ao poss\'{\i}veis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se uma sele\c{c}\~ao pode ser constitu\'{\i}da de quaisquer qualidades de
              laranjas?
        \item Se uma sele\c{c}\~ao deve ter pelo menos uma laranja de cada tipo?
       \end{list}

 \item Um grupo de estudos de 10 pessoas deve ser formado a partir de
       uma turma de 12 alunos e 6 alunas. De quantas maneiras \'{e}
       poss\'{\i}vel fazer essa forma\c{c}\~{a}o, supondo que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Deva haver exatamente 5 alunas no grupo?
        \item Deva haver, no m\'{\i}nimo, 4 alunas no grupo?
       \end{list}

 \item Um grupo de 18 pol\'{\i}ticos deve formar um ``trem da alegria'', de forma que 3
       deles viajem para Nova Iorque, 4 para Los Angeles, 5 para Orlando e 6 para Las Vegas.
       De quantas formas tal grupo pode ser assim particionado?

 \item Se $n$ objetos distintos s\~ao distribu\'{\i}dos em $n$ caixas distintas, qual \'e
       a probabilidade que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Nenhuma caixa fique vazia?
        \item Exatamente uma caixa fique vazia?
       \end{list}

% Townsend 2.3, pag. 68, ex. 24

 \item As 52 cartas do baralho s\~ao distribu\'{\i}das em n\'umero igual para 4 pessoas distintas.
       Qual \'e a probabilidade que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada pessoa receba um dos ases?
        \item Uma pessoa receba todos os ases?
       \end{list}

% Townsend 2.4, pag. 75, ex. 12

 \item Quantas sequ\^encias tern\'arias de 30 d\'{\i}gitos t\^em exatamente dez 1s?

 \item Escreva problemas equivalentes do tipo ``solu\c{c}\~oes em inteiros de uma equa\c{c}\~ao''
       para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O n\'umero de maneiras de distribuir $r$ bolas id\^enticas em $n$ caixas
              distintas com pelo menos $k$ bolas na primeira caixa.
        \item O n\'umero de maneiras de distribuir $r$ bolas id\^enticas em $n$ caixas
              distintas de forma que nenhuma caixa contenha mais de duas bolas.
        \item O n\'umero de subconjuntos de tr\^es elementos de $\{A,B,C,D,E\}$.
        \item O n\'umero de maneiras de distribuir $r$ bolas id\^enticas em $n$ caixas
              distintas de forma que as primeiras duas caixas contenham um total de $p$ bolas.
       \end{list}

% Townsend 2.5, pag. 81, ex. 1

 \item 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=20 \\
                 x_1+x_2+x_3=8
                \end{array} \right\} \mbox{ com } x_k\geq 0 \]

 \item Qual \'{e} o coeficiente de $x^{10}$ em $(1-2x-3y)^{20}$?
 \item Prove, por indu\c{c}\~{a}o, que $C(n+1,r+1)=\sum_{k=r}^{n}C(k,r)$.
 \item Prove, usando racioc\'{\i}nio combinat\'{o}rio:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^{n}C(n,k)^2=C(2n,n)$.
        \item $\sum_{k=0}^{r}C(m,k)C(n,r-k)=C(m+n,r)$.
       \end{list}

 \item Avalie, usando o teorema binomial:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^{n}2^kC(n,k)$.
        \item $\sum_{k=0}^{n}k3^kC(n,k)$.
       \end{list}
\end{enumerate}

\vspace*{4mm}
\noindent{\bf Fun\c{c}\~{o}es Geradoras}
 
\vspace*{2mm}
\begin{enumerate}
 \item[18.] Apresente fun\c{c}\~{o}es geradoras para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O n\'umero de seq\"u\^encias bin\'arias de $r$ d\'{\i}gitos.
        \item O n\'umero de multiconjuntos de $r$ elementos tomados de
              $\{x_1,x_2,\ldots,x_n\}$.
        \item O n\'umero de multiconjuntos de $r$ elementos tomados de
              $\{x_1,x_2,\ldots,x_n\}$,
              nos quais cada elemento aparece pelo menos uma vez.
       \end{list}

 \item[19.] Apresente fun\c{c}\~{o}es geradoras para os seguintes problemas de 
       equa\c{c}\~{o}es inteiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+x_3+x_4+x_5=r$, com $x_1+x_2=6$ e $x_k\geq 0$.
        \item $x_1+x_2+x_3<r$, com $k\leq x_k<2k$.
        \item $2x_1+3x_2+5x_3=r$, com $x_k>k$.
       \end{list}

 \item[20.] Encontre a fun\c{c}\~{a}o geradora para o n\'{u}mero de maneiras em que o
       lan\c{c}amento de 3 dados distintos pode produzir um soma de, no m\'{a}ximo,
       $r$.

 \item[21.] Encontre os coeficientes dos seguintes termos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x^{24}$ em $(x^3+x^4+\cdots+x^{12})^4$.
        \item $x^{6}$ em $(x+x^2+\cdots)^2(1-x^{3})^3$.
        \item $x^{5}$ em $(1-x^2)^{12}/(1-x)^3$.
       \end{list}

 \item[22.] Encontre fun\c{c}\~{o}es geradoras para os seguintes $a_n$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_n=3n-4$.
        \item $a_n=n(n-1)$.
        \item $a_n=n^4$.
        \item $a_n=n^23^n$.
       \end{list}

 \item[23.] Use as fun\c{c}\~{o}es geradoras do exerc\'{\i}cio anterior
       para avaliar as seguintes somas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^n(3k-4)$.
        \item $2\times 1+3\times 2+\cdots+n(n-1)$.
        \item $\sum_{k=1}^n n^4$.
        \item $3+2^23^2\cdots+n^23^n$.
       \end{list}

 \item[24.] Utilizando fun\c{c}\~{o}es geradoras, determine o n\'{u}mero de solu\c{c}\~{o}es
       inteiras para as seguintes equa\c{c}\~{o}es:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x_1+x_2+x_3+x_4=10$, com $1\leq x_i\leq 6$.
        \item $x_1+x_2+x_3=6$, com $1\leq x_1\leq 5$, $x_2\geq 2$ e $x_3\geq 3$.
        \item $x_1+x_2+x_3+x_4\leq 10$, com $1\leq x_i\leq 10$.
       \end{list}

 \item[25.] De quantas maneiras se pode distribuir $13$ reais a 30 crian\c{c}as, se cada
       crian\c{c}a recebe no m\'aximo 2 reais?

% Townsend 3.4, pag. 116, ex. 7

 \item[26.] Quantas maneiras existem de distribuir 20 c\'{e}dulas de 1 real a 10 meninas
       e $r$ meninos, se cada menina recebe no m\'{\i}nimo 1 real e cada menino
       recebe no m\'{a}ximo 3 reais?

 \item[27.] Use fun\c{c}\~{a}o geradora para encontrar o n\'{u}mero de maneiras de pintar
       20 quartos id\^{e}nticos de um hotel com 5 cores, se existe tintas das
       cores azul, cor-de-rosa e verde suficientes para pintar no m\'{a}ximo
       3 quartos (para cada uma das cores).

 \item[28.] Quantas maneiras existem de selecionar $4r$ bolas a partir de $2r$ bolas
       vermelhas id\^enticas, $2r$ bolas verdes id\^enticas e 
       $2r$ bolas brancas id\^enticas?

\end{enumerate}

\end{document}
\end{document}
